Concrete Mathematics: Chapter 2: Part 1

Sigma Notation

Chapter 2 is about understanding the sigma notation for sums. The general delimited form looks as follows:

$$\sum\limits_{k=1}^n{a_k}$$

However, the book declares that the delimited form is not as explicit when compared to a more generalized form and so should only be used for a finished equation rather than when working with them. A more generalized form can look like the following:

$$\sum\limits_{1 \le k \le n}{a_k}$$

When comparing the two there is a big difference in the notation. This is where you can clearly see that the generalized form can be more useful. Below is the same summation (squaring the odd numbers from 1 to 100) but using the two different notations.

$$ \begin{aligned} \text{Delimited} &= \sum_{k = 0}^{49}(2k + 1)^2 \\ \text{Generalized} &= \sum_{ \scriptstyle1 \le k \le 100 \atop\scriptstyle k \text{ odd}} k^2 \end{aligned} $$

Iverson Bracket

This chapter also mentions the Iverson bracket, which is essentially a mathematical if statement where it returns 1 for true and 0 for false. The iverson bracket looks as follows:

$$ [p \text{ prime}] = \begin{cases} 0, & \text{if}\ p \text{ is a prime number} \\ 1, & \text{if}\ p \text{ is not a prime number} \end{cases} $$

With this we can write more expressive delimited sums. Take this for example, a sum for finding the reciprocal of primes smaller than or equal to N.

$$ \sum \limits_{p}[p \text{ prime}][p \le N]/p $$

Tower of Hanoi

With these new tools, the book takes a brief look back at the tower of Hanoi example. As this is the original tower of Hanoi puzzle the solution is different from the previous blog in this series, so ill recap. The recursion is as follows:

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

Now the book mysteriously tell us to divide both sides by $2^n$ (actually multiplying by $2^{-n}$), this is so we can remove the $2$ which is multiplying the $T_{n-1}$. This puts out equation in a form which can easily be converted to a summation. I'll talk a little more about how we find out what number to multiply by in the next blog. Anyway lets do the division.

$$ \begin{aligned} T_0/2^0 &= 0;\\ T_n/2^n &= 2T_{n-1}/2^n + 1/2^n, \quad \text{for }n>0 \\ \textrm{Remember that}\ 2^n/2 &= 2^{n-1} \\ \therefore\ T_n/2^n &= T_{n-1}/2^{n-1} + 1/2^n, \quad \text{for }n>0 \end{aligned} $$

Now we can simplify the equation a little bit by setting $S_n=T_n/2^n$, which gives us the following recursive solutions.

$$ \begin{aligned} S_0 &= 0;\\ S_n &= S_{n-1} + 1/2^n, & \text{for }n>0 \\ &= S_{n-1} + 2^{-n}, & \text{for }n>0 \end{aligned} $$

This gives us the summation below.

$$ S_n = \sum \limits_{k = 1}^{n} 2^{-k} $$

This doesn't exactly look like $2^n-1$. Fortunately the book gives us a small amount of closure by telling us what this series is equal to.

$$\sum \limits_{k=1}^{n}2^{-k} = (\frac{1}{2})^{-1} + (\frac{1}{2})^{-2} + \ldots + (\frac{1}{2})^{-n} = 1 - (\frac{1}{2})^n.$$

Now we can show that the previous sum is equal to $2^n - 1.$

$$ \begin{aligned} S_n &= \sum \limits_{k = 1}^{n} 2^{-k} \\ &= 1 - (\frac{1}{2})^n \\ \end{aligned} $$

Now solve for $T_n$:

$$ \begin{aligned} T_n &= 2^nS_n \\ &= 2^n (1-(\frac{1}{2})^n) \\ &= 2^n (1-2^{-n}) \\ &= 2^n - 2^n \cdot 2^{-n} \\ &= 2^n - 1 \end{aligned} $$

There were a few leaps of faith during this blog post, where we just followed what the book told us to do. These parts will be addressed in later blogs for the same chapter.