Sums and Recurrences: Gotchas

In the previous post, we started looking into chapter 2.2 of Concrete Mathematics. This post lists a few gotchas found in the remaining part of the chapter.

Gotcha 1

Page 27. This factor $s_n$ is cleverly chosen to make … means we assume that $s_nb_n = s_{n - 1}a_{n - 1}$ .

Gotcha 2

Page 27. To get (2.10), recall that $S_n = s_na_nT_n$ . Hence

$\begin{align*} T_n &= \frac{S_n}{s_na_n} \\ &= \frac{1}{s_na_n} \times S_n \\ &= \frac{1}{s_na_n} \left(s_1b_1T_0 + \sum_{k=1}^{n}s_kc_k \right) \ . \end{align*}$

$\begin{align*} s_n &= \frac{s_{n - 1}a_{n - 1}}{b_n} \\ &= \frac{a_{n - 1}}{b_n} \times \frac{s_{n - 2}a_{n - 2}}{b_{n - 1}} \\ & \dots \\ &= \frac{a_{n - 1}a_{n - 2} \dots a_1}{b_nb_{n - 1} \dots b_2} \times s_1 \\ &= \frac{a_{n - 1}a_{n - 2} \dots a_1}{b_nb_{n - 1} \dots b_2} \ . \end{align*}$

Here $s_1 = 1$ as an empty product.

Gotcha 4

Page 28. Let's see how exactly We can now subtract the second equation from the first.

$\begin{align*} & nC_n - (n - 1)C_{n - 1} \\ &= n^2 + n + 2\sum_{k=0}^{n-1}C_k - \left((n-1)^2 + (n-1) + 2\sum_{k=0}^{n-2}C_k \right) \\ &= n^2 + n + 2\sum_{k=0}^{n-1}C_k - \left(n^2 - 2n + 1 + n - 1 + 2\sum_{k=0}^{n-2}C_k \right) \\ &= n^2 + n + 2\sum_{k=0}^{n-1}C_k - \left(n^2 - n + 2\sum_{k=0}^{n-2}C_k \right) \\ &= n^2 + n + 2\sum_{k=0}^{n-1}C_k - n^2 + n - 2\sum_{k=0}^{n-2}C_k \\ &= 2 \left(\sum_{k=0}^{n-1}C_k - \sum_{k=0}^{n-2}C_k \right) + 2n \\ &= 2C_{n - 1} + 2n \ . \end{align*}$

Gotcha 5

Page 28. We add a tiny but significant detail to the expansion of the summation factor. It starts with substitution of $a_n = n$ and $b_n = n + 1$ into (2.11).

$\begin{align*} s_n &= \frac{a_{n-1} a_{n-2} \dotsc a_1}{b_n b_{n-1} \dotsc b_2} \\ &= \frac{(n-1) \cdot (n-2) \cdot \dotsc \cdot 3 \cdot 2 \cdot 1}{(n+1) \cdot n \cdot (n-1) \cdot (n-2) \cdot \dotsc \cdot 3} \\ &= \frac{2 \cdot 1}{(n + 1) \cdot n} \\ &= \frac{2}{(n + 1)n} \ . \end{align*}$

Gotcha 6

Page 29. Substituting the summation factor into (2.10), for $a_n = n$ , $b_n = n + 1$ , $c_n = 2n$ , we derive that

$\begin{align*} C_n &= \frac{1}{\frac{2}{(n+1)n} \cdot n} \left(s_1 \cdot b_1 \cdot 0 + \sum_{k=1}^{n}\frac{2}{(k+1)k} \cdot 2 \cdot k \right) \\ &= \frac{n+1}{2} \sum_{k=1}^{n}\frac{4}{k+1} \\ &= 2(n + 1)\sum_{k=1}^{n}\frac{1}{k+1} \ . \end{align*}$

Gotcha 7

Page 29. We finalize this journey through gotchas with a lucky number 7. And we're looking into deriving the formula (2.14), which is even luckier.

$\begin{align*} C_n &= 2(n + 1)\sum_{k=1}^{n}\frac{1}{k+1} \\ &= 2(n + 1) \left( H_n - 1 + \frac{1}{n+1} \right) \\ &= 2(n + 1)H_n - 2(n + 1) + \frac{2(n+1)}{n+1} \\ &= 2(n + 1)H_n - 2n - 2 + 2 \\ &= 2(n + 1)H_n - 2n \ . \end{align*}$

And we're done here 🎉 🥳 !

Repertoire Method

Concrete AfterMath