RtW

17 April 2022


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*}

Gotcha 3

Page 27. Derivation of (2.11):

\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 🎉 🥳 !

Creative Commons License This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International License.

Created by Y.E.T.If you see an error, please report it.