Wakatta!

Like Eureka!, only cooler

Concrete Mathematics Chapter 2 Homework Exercises

It has been a long time since I wrote about this book; I had worked the solutions more than a month ago, but then life happened, and I could not find the time (or, perhaps, more accurately the courage) to typeset my notes…

Anyway, I do have time now and am eager to go on with Chapter 3; but first let’s finish Chapter 2. Today the homework exercises, and very soon the exams and bonus (at least the ones I could do) exercises.

Homework

$2T_n = nT_{n-1}+3\cdot n!$

This exercise is not tricky in any way; just follow the method and the result is guaranteed.

The recurrence equations are

\begin{align} T_0 & = 5\\ 2T_n & = nT_{n-1}+3\cdot n!\\ \end{align}

The $a_n$, $b_n$ and $c_n$ series are:

\begin{align} a_n & = 2\\ b_n & = n\\ c_n & = 3\cdot n!\\ \end{align}

The summation factor

\begin{align} s_n & = \frac{a_{n-1}\dots a_1}{b_n\dots b_2}s_1\\ & = \frac{2^{n-1}}{n!}s_1\\ \end{align}

After experimenting a bit, I found that $s_1 = 2$ is slightly easier to work with, so the summation factor is $s_n = \frac{2^n}{n!}$.

With $S_n = \frac{2^n+1}{n!} T_n$, the recurrence equation becomes

\begin{align} S_n & = S_{n-1} + 3\cdot 2^n\\ & = S_0 + 3\sum_{k=1}^n 2^k\\ \end{align}

The sum is well-known, with $\sum_{k=0}^n 2^k = 2^{n+1}-1$, so $\sum_{k=1}^n 2^k = 2^{n+1}-2$.

Going back to $T_n$, we have

\begin{align} T_n & = \frac{n!(10+3(2^{n+1}-2))}{2^{n+1}}\\ & = \frac{n!(5+3(2^n-1))}{2^n}\\ & = \frac{n!(5 + 3\cdot 2^n - 3)}{2^n}\\ & = \frac{n!(3\cdot 2^n + 2)}{2^n}\\ & = 3\cdot n! + \frac{n!}{2^{n-1}}\\ \end{align}

$\sum_{k=0}^n kH_k$

Using the perturbation method:

\begin{align} S_{n+1} = S_n + (n+1) H_{n+1} & = 0 + \sum_{k=1}^{n+1} k H_k\\ & = \sum_{k+1=1}^{n+1}(k+1)H_{k+1}&&k\leftarrow k+1\\ & = \sum_{k=0}^n (k+1) (H_k + \frac{1}{k+1})\\ & = \sum_{k=0}^n k H_k + \sum_{k=0}^n \frac{k}{k+1} + \sum_{k=0}^n H_k + \sum_{k=0}^n \frac{1}{k+1}\\ & = S_n + \sum_{k=0}^n\frac{k+1}{k+1} + \sum_{k_0}^n H_k\\ & = S_n + n+1 + \sum_{k=0}^n H_k\\ \end{align}

so $\sum_{k=0}^n H_k$ is

\begin{align} \sum_{k=0}^n H_k & = (n+1)H_{n+1} - (n + 1)\\ & = (n+1)H_n + (n+1)\frac{1}{n+1} - n - 1\\ & = (n+1)H_n + 1 - n - 1\\ & = (n+1)H_n - n\\ \end{align}

More perturbation method

This exercise is just tricky in the very first step (working out the exact meaning of $S_{n+1}$), as the sign of the terms change depending of whether $n$ is odd or even.

This means that instead of the book equation (2.24) $S_{n+1} = S_n + a_{n+1}$, we find something like $S_{n+1} = a_{n+1} - S_n$.

$S_n = \sum_{k=0}^n (-1)^{n-k}$

First, the left hand part of the equation:

\begin{align} S_{n+1} & = \sum_{k=0}^n (-1)^{n+1-k} + (-1)^{n+1-n-1}\\ & = -\sum_{k=0}^n (-1)^{n-k} + 1\\ & = 1 - S_n\\ \end{align}

Then, the right hand part:

\begin{align} S_{n+1} & = (-1)^{n+1} + \sum_{k=1}^{n+1} (-1)^{n+1-k}\\ & = (-1)^{n+1}+\sum_{k+1=1}^{n+1}(-1)^{n+1-k-1}&&k\leftarrow k+1\\ & = (-1)^{n+1} + \sum_{k=0}^n(-1)^{n-k}\\ & = (-1)^{n+1} + S_n\\ \end{align}

Putting both together, $S_n = \frac{1-(-1)^{n+1}}{2}$, or, as the book states, $S_n = [\text{\(n\) is even}]$.

$T_n = \sum_{k=0}^n (-1)^{n-k}k$

Using the same approach as above:

\begin{align} T_{n+1} & = \sum_{k=0}^{n+1}(-1)^{n+1-k}k\\ & = -\sum_{k=0}^n(-1)^{n-k}k + (-1){n+1-n-1}(n+1)\\ & = n+1-T_n\\ \end{align}

and

\begin{align} T_{n+1} & = \sum_{k=0}^{n+1}(-1)^{n+1-k}k\\ & = (-1)^{n+1}0 + \sum_{k=1}^{n+1}(-1)^{n+1-k}k\\ & = 0 + \sum_{k+1=1}^{n+1}(-1)^{n+1-k-1}{k+1}&&k\leftarrow k+1\\ & = \sum_{k=0}^n(-1)^{n-k}k + \sum_{k=0}^n(-1)^{n-k}\\ & = T_n + S_n\\ \end{align}

Together:

\begin{align} T_n & = \frac{n+1-S_n}{2}\\ & = \frac{1}{2}\left(n+[\text{\(n\) is odd}] \right)\\ & = \left\lceil \frac{n}{2} \right\rceil\\ \end{align}

The last version uses the ceiling operator from Chapter 3.

$U_n = \sum_{k=0}^n (-1)^{n-k}k^2$

It will probably not be a surprised to find $U_n$ expressed in terms of $S_n$ and $T_n$.

\begin{align} U_{n+1} & = \sum_{k=0}^{n+1}(-1)^{n+1-k}k^2\\ & = \sum_{k=0}^n(-1)^{n+1-k}k^2 + (-1)^{n+1-n-1}(n+1)^2\\ & = -1\sum_{k=0}^n(-1)^{n-k}k^2 + (n+1)^2\\ & = (n+1)^2 - U_n\\ \end{align}

and

\begin{align} U_{n+1} & = \sum_{k=0}^{n+1}(-1)^{n+1-k}k^2\\ & = (-1)^{n+1}0 + \sum_{k=1}^{n+1}(-1)^{n+1-k}k^2\\ & = 0 + \sum_{k+1=1}^{n+1}(-1)^{n+1-k-2}(k+1)^2&& k\leftarrow k+1\\ & = \sum_{k=0}^n(-1)^{n-k}(k^2+2k+1)\\ & = U_n + 2T_n + S_n\\ \end{align}

With $2T_n = n+1-S_n$, this produces $U_{n+1} = U_n + n + 1$, which gives the answer away, but let’s just continue with the current method.

Putting both side together:

\begin{align} U_n & = \frac{(n+1)^2 - (n+1)}{2}\\ & = \frac{(n+1)(n+1) - (n+1)}{2}\\ & = \frac{n(n+1)}{2}\\ \end{align}

Lagrange’s Identity

First, I look for a usable double sum. I use the fact that for any $j, k$, $j < k$, $(a_jb_k - a_kb_j) = -(a_kb_j - a_jb_k)$ and $(A_jB_k - A_kB_j)= - (A_kB_j - A_jB_k)$. This means that, with $s_{j,k} = (a_jb_k - a_kb_j)(A_jB_k - A_kB_j)$, $s_{j,k} = s_{k,j}$.

There is also the fact that $s_{j,j} = 0$, so now I can complete the sum to the whole rectangle:

\begin{align} \sum_{1\le j,k\le n}s_{j,k} & = \sum_{1\le j\lt k\le n}s_{j,k} + \sum_{1\le j = k \le n} s_{j,k} + \sum_{1\le k \lt j \le n}s_{k,j}\\ & = \sum_{1\le j \lt k \le n}s_{j,k} + 0 + \sum_{1\le j \lt k \le n}s_{j,k}\\ & = 2\sum_{1\le j \lt k \le n}s_{j,k}\\ \end{align}

The expansion of $s_{j,k}$ is $a_jA_jb_kB_k - a_jB_jA_kb_k - A_jb_ja_kB_k + b_jB_ja_kA_k$. Showing the summation just for the first one (the other three are identical):

\begin{align} \sum_{1\le j, k \le n} a_jA_jb_kB_k & = \sum_{j=1}^n\sum_{k=1}^n a_jA_jb_kB_k\\ & = \sum_{j=1}^n a_jA_j \left(\sum_{k=1}^n b_kB_k \right)\\ & = \left(\sum_{j=1}^n a_jA_j\right)\left(\sum_{k=1}^n b_kB_k \right)\\ & = \left(\sum_{k=1}^n a_kA_k\right)\left(\sum_{k=1}^n b_kB_k \right)\\ \end{align}

Putting it all together:

\begin{align} \sum_{1\le j\lt k\le n}(a_jb_k - a_kb_j)(A_jB_k - A_kB_j) & = \left(\sum_{k=1}^n a_kA_k\right)\left(\sum_{k=1}^n b_kB_k\right) - \left(\sum_{k=1}^n a_kB_k\right)\left(\sum_{k=1}^n A_kb_k\right)\\ \end{align}

In particular, with $a_k = A_k$ and $b_k = B_k$, the sum is $\left(\sum_{k=1}^n a_k^2 \right)\left(\sum_{k=1}^n b_k^2 \right) - 2 \left(\sum_{k=1}^n a_kb_k \right)$.

$\sum_{k=1}^n \frac{2k+1}{k(k+1)}$

Partial fractions

\begin{align} \sum_{k=1}^n\frac{2k+1}{k(k+1)} & = \sum_{k=1}^n(k+(k+1))\left(\frac{1}{k}-\frac{1}{k+1} \right)\\ & = \sum_{k=1}^n\left(\frac{k}{k} + \frac{k+1}{k} - \frac{k}{k+1} - \frac{k+1}{k+1} \right)\\ & = \sum_{k=1}^n \frac{k+1}{k} - \sum_{k=1}^n \frac{k}{k+1}\\ & = n + H_n - \sum_{k=1}^n \frac{k}{k+1} - \sum_{k=1}^n\frac{1}{k+1} + \sum_{k=1}^n\frac{1}{k+1}\\ & = n + H_n - \sum_{k=1}^n \frac{k+1}{k+1} + \sum_{k=1}^n \frac{1}{k+1}\\ & = H_n + \sum_{k-1=1}^n \frac{1}{k}&&k\leftarrow k-1\\ & = H_n + \sum_{k=2}^{n+1} \frac{1}{k}\\ & = H_n + H_{n+1} - 1\\ & = H_h + H_n + \frac{1}{n+1} - \frac{n+1}{n+1}\\ & = 2H_n - \frac{n}{n+1}\\ \end{align}

Sum by parts

Using

\begin{align} \Delta v & = \frac{1}{k(k+1)} = (k-1)^{\underline{-2}}\\ v & = -(k-1)^{\underline{-1}}\\ Ev & = -k^{\underline{-1}}\\ u & = 2k+1\\ \Delta u & = 2\\ \end{align}

First the sum by part

\begin{align} \sum \frac{2x+1}{x(x+1)}\delta x & = -(2x+1)(x-1)^{\underline{-1}} + 2 \sum x^{\underline{-1}} \delta x + c\\ & = -\frac{2x+1}{x} + 2 H_x + c\\ \end{align}

Then the evaluation

\begin{align} \sum_{k=1}^n\frac{2k+1}{k(k+1)} & = \left. -\frac{2x+1}{x}+2H_x\right|_1^{n+1}\\ & = -\frac{2(n+1)+1}{n+1} + 2 H_{n+1} + 2 + 1 - 2\\ & = 2 H_{n+1} + 1 - 2 - \frac{1}{n+1}\\ & = H_{n+1} + H_n - 1\\ & = 2H_n - \frac{n}{n+1}\\ \end{align}

$\sum_{1\le k \lt n}\frac{H_k}{(k+1)(k+2)}$

For the sum by part, I use

\begin{align} \Delta v & = x^{\underline{-2}}\\ v & = -x^{\underline{-1}}\\ Ev & = -(x+1)^{\underline{-1}}\\ u & = H_x\\ \Delta u & = x^{\underline{-1}}\\ \end{align}

The sum by part

\begin{align} \sum_{k=1}^n H_x x^{\underline{-2}} \delta x & = -H_x x^{\underline{-1}} + \sum (x+1)^{\underline{-1}}x^{\underline{-1}}\delta x + c\\ & = -H_x x^{\underline{-1}} + \sum x^{\underline{-2}} \delta x + c\\ & = -H_x x^{\underline{-1}} - x^{\underline{-1}} + c\\ & = -(H_x + 1) x^{\underline{-1}} + c\\ \end{align}

The evaluation is

\begin{align} \sum_{0\le k \lt n} \frac{H_k}{(k+1)(k+2)} & = \left. -\frac{H_x + 1}{x+1} \right|_0^n\\ & = 1 - \frac{H_n + 1}{n+1}\\ \end{align}

Product laws

I don’t think I listed all the laws for this exercise, as the only complete list for the sum laws in the book is in the answer for this exercise.

I will not repeat it here; suffice to say that when we replace sum by product, the laws can be updated by replacing product by exponentiation, and sum by product.

$\prod_{1\le j \le k \le n}a_ja_k$

While it took me a few false starts, I eventually found that the triangular completion used for (2.32) works here as well.

\begin{align} \left(\prod_{1\le j\le k \le n} a_ja_k \right)^2 & = \left(\prod_{1\le j,k \le n}a_ja_k \right) \left(\prod_{1\le j=k \le n}a_ja_k\right)\\ & = \left(\prod_{1\le j,k \le n} a_j\right) \left(\prod_{1\le j,k \le n} a_k\right) \left(\prod_{1\le k \le n}a_k^2\right)\\ & = \left(\prod_{1\le k \le n} a_k^n\right) \left(\prod_{1\le j \le n} a_j^n\right) \left(\prod_{1\le k \le n}a_k^2\right)\\ & = \prod_{1\le k\le} a_k^{2n+2}\\ \end{align}

So $\prod_{1\le j \le k \le n}a_ja_k = \left(\prod_{1\le k\le} a_k\right)^{n+1}$.

$\sum_{k=1}^n \frac{(-2)^{\underline k}}{k}$

As suggested, I worked out $\Delta c^{\underline x}$:

\begin{align} \Delta c^{\underline x} & = c^{\underline{x+1}} - c^{\underline x}\\ & = c(c-1)\cdots (c-x+1)(c-x) - c(c-1)\cdots (c-x+1)\\ & = c^{\underline x}(c-x-1)\\ \end{align}

I did not immediately saw the relation between this and the original sum. First I rewrote the original sum to remove the division:

\begin{align} \sum_{k=1}^n \frac{(-2)^{\underline k}}{k} & = \sum_{k=1}^n \frac{(-2)^{\underline{k-1}}(-2-k+1)}{k}\\ & = -\sum_{k=1}^n \frac{(-2)^{\underline{k-2}(k+1)(-2-k+2)}}{k}\\ & = \sum_{k=1}^n \frac{(-2)^{\underline{k-2}(k+1)(k)}}{k}\\ & = \sum_{k=1}^n (-2)^{\underline{k-2}}(k+1)\\ \end{align}

Now the relation is visible. So we have

\begin{align} \sum_1^{n+1}\frac{(-2)^{\underline x}}{x}\delta x & = \sum_1^{n+1}(-2)^{\underline x}(x+1)\delta x\\ x & = \left. - (-2)^{\underline{x-2}}\right|_1^{n+1}\\ & = (-2)^{\underline{-1}} - (-2)^{\underline{n-1}}\\ & = -1 - (-2)(-3) \cdots (-n)\\ & = (-1)^n n! - 1\\ \end{align}

Incorrect derivation

As stated in the book, the infinite sums do no converge, so the third step is invalid.

And that’s all for today.

Comments