Concrete Mathematics: Chapter 2: Part 2

Summation Factor

As mentioned in the previous blog, I need to go over a few things that were mentioned but never explained. The first is the summation factor. This is what is used in order to reduce a recursive equation down to a more simple version. So we can reduce a recursion from

$a_nT_n = b_nT_{n-1} + c_n$

to the form

$S_n = S_{n-1} + s_nc_n$

by multiplying by a summation factor and then substituting in $S_n = s_na_nT_n.$ This greatly reduces the recurrence so it is much easier to convert it into a summation with sigma notation. The above would then translate to the following summation:

$S_n = s_0a_0T_0 + \sum \limits^n_{k=1}s_kc_k = s_1a_1T_0 + \sum \limits^n_{k=1}s_kc_k$

It is important to note that there is the term $s_0a_0T_0$ as this is used when the starting terms are non-zero or the summation factor is undefined. The book makes subtle use of this term with the quicksort example. I will talk a bit about that later on.

Now we know how to use the summation factor, we need to learn how to get the summation factor. In the first part for this chapter I just multiplied the tower of Hanoi recursion by $2^{-n}$ without explaining where that was from. Well, it turns out that was found using the equation

$s_n = \frac{a_{n-1}a_{n-2} \ldots a_1}{b_nb_{n-1} \ldots b_2}$

Okay. Let's try that and see if we can get $2^{-n}.$

First we note that $a_n=1$, $b_n=2$ and $c_n=1$. This means that the formula is the following

$\begin{aligned} s_n &= \frac{1 \cdot 1 \cdot \ldots \cdot 1}{2 \cdot 2 \cdot \ldots \cdot 2} &(\text{Substitute in the values}) \\ s_n &= \frac{1}{2^{n-1}} &(\text{There are}\ n-1\ \text{terms of}\ b_n) \\ s_n &= 2^{-(n-1)} &(\text{Rearrange}) \end{aligned}$

That's weird, we ended up with a different summation factor than the one that's in the book. Not to worry, the book tells us that it's ok to use any multiple of the summation factor and it should still work. So let's carry on.

$\begin{aligned} T_0 &= 0; \\ T_n &= 2T_{n-1} + 1, &\text{for}\ n>0 \end{aligned}$

Multiply by summation factor, $2^{-(n-1)}$

$\begin{aligned} T_0/2^{n-1} &= 0 \\ T_n/2^{n-1} &= 2T_{n-1}/2^{n-1} + 1/2^{n-1} \\ &= T_{n-1}/2^{n-2} + 2^{-(n-1)} \\ \end{aligned}$

Let $S_n = T_n/2^{n-1}$

$\begin{aligned} S_n &= S_{n-1} + 2^{-(n-1)} \\ &= \sum \limits^n_{k=1}2^{-(k-1)} \end{aligned}$

Convert back to $T_n$

$\begin{aligned} T_n/2^{n-1} &= \sum \limits^n_{k=1}2^{-(k-1)} \\ T_n &= 2^{n-1} \sum \limits^n_{k=1}2^{-(k-1)} \end{aligned}$

Now we can try some values to verify that this will indeed work. First $n=3,$

$\begin{aligned} T_n &= 2^2(2^{-0} \cdot 2^{-1} \cdot 2^{-2}) \\ &= 4\left(1 \cdot \frac{1}{2} \cdot \frac{1}{4}\right) \\ &= 7 \end{aligned}$

Great! Checking other $n$ shows that this is a summation solution for the tower of Hanoi. However it is not as elegant as the solution the book gave when it used $2^{-n}$ as the summation factor. So make sure to play with the summation factor when converting recurrences to sums.

Problem with quicksort example

So far this book has stumped me in a few places, but I can generally work through the problem until the answer clicks. However, the one I have spent the most time on was a problem with the quicksort example.

While working through their examples, I couldn't see where they gained the extra term for the final solution. Fortunately, I found the solution on math.stackexchange. I turns out that the summation factor is undefined for the early terms and so we need to add them to the summation which doesn't include the terms.

$\begin{aligned} S_n &= S_2 + \sum_{k=3}^ns_kc_k \\ &= s_2a_2C_2 + \sum_{k=3}^ns_kc_k\\ &= \frac13 \cdot 2 \cdot 3 + \sum_{k=3}^n \frac{4k}{k(k+1)} \\ &= 2 + 4 \sum_{k=3}^n \frac1{k+1} \end{aligned}$

Then convert back to $C_n$

$\begin{aligned} C_n &= \frac{S_n}{s_na_n}\\ &= \frac{n+1}2 \left(2 + 4 \sum_{k=3}^n \frac1{k+1} \right) \\ &= (n+1) \left(1 + 2 \sum_{k=1}^n \frac1{k+1}-2 \sum_{k=1}^2 \frac1{k+1} \right) \\ &= (n+1) \left(1 + 2 \sum_{k=1}^n \frac1{k+1} - \frac53 \right)\\ &= (n+1) \left(2 \sum_{k=1}^n \frac1{k+1} - \frac23 \right) \\ &= 2(n+1) \sum_{k=1}^n \frac1{k+1} - \frac23(n+1) \end{aligned}$

Many thanks to Brian M. Scott for answering the question posed by Cyril on StackExchange. I'd still be trying to figure it out otherwise.