A.2-1

Show that \(\sum_{k = 0}^n 1/k^2\) is bounded above by a constant.

Sol’n

rough draft:

\[ \begin{align*} \sum_{k = 2}^n \frac {1}{k^2} & \le \int_1^n \frac {1}{x^2}\, dx \\ & = \frac {-1}{x} \bigg|_1^n \\ & = 1 - \frac {1}{n} \\ & < 1. \end{align*} \]

A.2-2

Find an asymptotic upper bound on the summation

\[ \sum_{k = 0}^{\lfloor \lg n \rfloor} \left\lceil n/2^k \right\rceil. \]

Sol’n

rough draft:

\[ \begin{align*} \sum_{k = 0}^{\lfloor \lg n \rfloor} \left\lceil \frac {n}{2^k} \right\rceil & \le \sum_{k = 0}^{\lfloor \lg n \rfloor} \left( \frac {n}{2^k} + 1 \right) \\ & = n \cdot \sum_{k = 0}^{\lfloor \lg n \rfloor} \left( \frac {1}{2} \right)^k + 1 + \lfloor \lg n \rfloor \\ & = n \cdot \frac {1 - \left(\frac{1}{2}\right)^{\lfloor \lg n \rfloor}}{1 - \frac {1}{2}} + 1 + \lfloor \lg n \rfloor \\ & \le n \cdot \frac {1 - \frac{1}{2^{\lg n}}}{1 - \frac {1}{2}} + 1 + \lfloor \lg n \rfloor \\ & = 2(n - 1) + 1 + \lfloor \lg n \rfloor \\ & = O(n). \end{align*} \]

A.2-3

Show that the \(n\)th harmonic number is \(\Omega(\lg n)\) by splitting the summation.

Sol’n

rough draft:

\[ \begin{align*} \sum_{k = 1}^n \frac {1}{k} & \ge \sum_{i = 0}^{\lfloor \lg n \rfloor - 1} \sum_{j = 0}^{2^i - 1} \frac {1}{2^i + j} \\ & \ge \sum_{i = 0}^{\lfloor \lg n \rfloor - 1} \sum_{j = 0}^{2^i - 1} \frac {1}{2^{i + 1}} \\ & = \sum_{i = 0}^{\lfloor \lg n \rfloor - 1} 1 \\ & = \Omega(\lg n). \end{align*} \]

A.2-4

Approximate \(\sum_{k = 1}^n k^3\) with an integral.

Sol’n

rough draft:

\[ \begin{align*} \sum_{k = 1}^n k^3 & = \Theta\left(\int_0^n x^3\, dx \right) \\ & = \Theta\left(\frac {1}{4} x^4\bigg|_0^n\right) \\ & = \Theta(n^4). \end{align*} \]

A.2-5

Why didn’t we use the integral approximation (A.12) directly on \(\sum_{k = 1}^n 1/k\) obtain an upper bound on the \(n\)th harmonic number?

Sol’n

rough draft:

To show us how hard it can be to use split of summation.