Appendix A

Exercise A.1-1

Any function belonging to $O(f_k(i))$ is upper bounded by $f_k(i)$. Using the definition of the big O notation, $g_k(i)=O(f_k(i))$ implies $g_k(i) \le c_kf_k(i)$ for some real constant $c_k>0$ and all $i \ge \hat i_k$. Define $c=max\{c_k:1\le k \le n\}$ and $i_0=max\{\hat i_k:1\le k \le n\}$. For all $i\ge i_0$ (assuming $n \ge 0)$

$$\begin{align*} \sum_{k=1}^n O(f_k(i)) &\le \sum_{k=1}^n c_kf_k(i) \\ &\le \sum_{k=1}^n cf_k(i) \\ &= c\sum_{k=1}^n f_k(i) \\ &\therefore \sum_{k=1}^n O(f_k(i))=O(\sum_{k=1}^n f_k(i)) \end{align*}$$

The asymptotic variable on both sides is $i$ whilst $n$ is essentially fixed. Regardless how we substitute those $n$ functions on the left, their sum is asymptotically bounded from above by a corresponding sum of upper bounds as $i \to \infty$.

This equation is frequently employed in analysis of algorithms. Suppose our algorithm consists of $n=3$ sections whose running times are $O(i\lg i)$, $O(i^2)$ and $O(i)$. The total time is commensurate with their sum, which by our equation is $O(i\lg i+i^2+i)=O(i^2)$, so our algorithm is quadratic in $i$.

Exercise A.1-2

$$\begin{align*} \sum_{k=1}^n(2k-1)&= 2\sum_{k=1}^n k - \sum_{k=1}^n 1 && \text{(by the linearity property)} \\ &=\frac{2n(n+1)}{2}-n && \text{(by equation (A.1))} \\ &= n^2 \end{align*}$$

Exercise A.1-3

$$111,111,111= \sum_{k=0}^8 10^k=\frac{10^9-1}{10-1}=\frac{999,999,999}{9}$$

Exercise A.1-4

Notice that our infinite series is absolutely convergent, since it transforms into a decreasing geometric series with $x=\frac {1}{2}$, if we use absolute values of summands. Consequently, we can rearrange the terms. Denote the original sum as S, thus

$$\begin{align*} 2S &= 2-(1-\frac {1}{2}+\frac {1}{4}-...)=2-S \\ &\therefore 3S=2 \implies S=\frac {2}{3} \end{align*}$$

Another possibility is to substitute $x=-\frac{1}{2}$ in equation (A.7).

Exercise A.1-5

We will find the two bounds (lower and upper) separately. The upper bound is

$$\begin{align*} \sum_{k=1}^n k^c &\le \sum_{k=1}^n n^c=n^c\sum_{k=1}^n 1=n^{c+1} \\ &\therefore \sum_{k=1}^n k^c=O(n^{c+1}) \qquad \checkmark \end{align*}$$

The lower bound demands more work, as we drop half of the terms and try to bound a partial sum.

$$\begin{align*} \sum_{k=1}^n k^c&\ge \sum_{k=\lceil{n/2}\rceil}^n k^c \\ &\ge\sum_{k=\lceil{n/2}\rceil}^n \lceil{n/2}\rceil^c \\ &= (n-\lceil{n/2}\rceil+1)\lceil{n/2}\rceil^c \\ &=(\lfloor{n/2}\rfloor+1)\lceil{n/2}\rceil^c \\ &\ge \lceil{n/2}\rceil^{c+1} \\ &\ge {(n/2)}^{c+1} \\ &={\left(\frac{1}{2}\right)}^{c+1}n^{c+1} \\ &\therefore \sum_{k=1}^n k^c=\Omega(n^{c+1})\qquad \checkmark \end{align*}$$

Theorem 3.1 implies that $\sum_{k=1}^n k^c=\Theta(n^{c+1})$.

You may also want to look at Faulhaber's formula. It generalizes the sum of integer powers.

Exercise A.1-6

Differentiating both sides of the infinite geometric series (A.11) gives

$$\begin{align*} \sum_{k=1}^n k^2x^{k-1}&=\frac{(1-x)^2+2x(1-x)}{(1-x)^4}\\ &=\frac{(1-x)+2x}{(1-x)^3}\\ &=\frac {1+x}{(1-x)^3} \\ &\therefore \sum_{k=1}^n k^2x^k = \frac {x(1+x)}{(1-x)^3} && \text{(after multiplying both sides with } x \text{)} \end{align*}$$

Exercise A.1-7

The upper bound is

$$\begin{align*} \sum_{k=1}^n \sqrt {k\lg k} &\le \sum_{k=1}^n \sqrt {n\lg n} =n\sqrt {n\lg n}= n^{3/2} {\lg^{1/2} n} \\ &\therefore \sum_{k=1}^n \sqrt {k\lg k}=O(n^{3/2} {\lg^{1/2} n}) \qquad \checkmark \end{align*}$$

The lower bound can be attained by splitting the summation as in Exercise A.1-5 assuming $n \ge 4$, so that $\lg n - 1 \ge (\lg n)/2$.

$$\begin{align*} \sum_{k=1}^n \sqrt {k\lg k} &\ge \sum_{k=\lceil{n/2}\rceil}^n \sqrt {k\lg k} \\ &\ge \sum_{k=\lceil{n/2}\rceil}^n \sqrt {\lceil{n/2}\rceil \lg \lceil{n/2}\rceil} \\ &= (n-\lceil{n/2}\rceil+1) \sqrt {\lceil{n/2}\rceil \lg \lceil{n/2}\rceil} \\ &=(\lfloor{n/2}\rfloor+1) \sqrt {\lceil{n/2}\rceil \lg \lceil{n/2}\rceil} \\ &\ge \lceil{n/2}\rceil \sqrt {\lceil{n/2}\rceil \lg \lceil{n/2}\rceil} \\ &\ge (n/2) \sqrt {(n/2) \lg (n/2)} \\ &= (n/2) \sqrt {(n/2) (\lg n - 1)} \\ &\ge (n/2) \sqrt {(n/2) (\lg n)/2} \\ &=\left(\frac{1}{4}\right) n^{3/2} {\lg^{1/2} n} \\ &\therefore \sum_{k=1}^n \sqrt {k\lg k}=\Omega(n^{3/2} {\lg^{1/2} n})\qquad \checkmark \end{align*}$$

Theorem 3.1 implies that $\sum_{k=1}^n \sqrt {k\lg k}=\Theta(n^{3/2} {\lg^{1/2} n})$.

Exercise A.1-8

Equations (A.8) and (A.9) are our starting points.

$$\sum_{k=1}^n \frac {1}{2k-1}+\sum_{k=1}^n \frac {1}{2k}=\sum_{k=1}^{2n} \frac {1}{k}=H_{2n}=\ln 2n + O(1)=\ln n +1+O(1) \qquad \checkmark$$

We will keep all constants and bundle them under single O(1) only in the last step for better visibility. Observe that $aO(1)+bO(1)+c=O(1)$ for all real constants $a$, $b$ and $c$. Let us multiply the leftmost and rightmost expressions by 2.

$$\begin{align*} 2\sum_{k=1}^n \frac {1}{2k-1}+\sum_{k=1}^n \frac {1}{k}&=2\ln n +2+2O(1) \\ 2\sum_{k=1}^n \frac {1}{2k-1}+H_n &=2\ln n +2+2O(1) \\ 2\sum_{k=1}^n \frac {1}{2k-1}+\ln n + O(1) &=2\ln n +2+2O(1) \\ 2\sum_{k=1}^n \frac {1}{2k-1} &=\ln n +2+2O(1)-O(1) \\ \sum_{k=1}^n \frac {1}{2k-1} &=\ln {\sqrt{n}} +O(1) \end{align*}$$

Exercise A.1-9

We have an infinite sum similar to the one in (A.11) with $x=1/2$. The linearity property also applies to infinite convergent series, but we must prove that our series converges. We can easily accomplish this by using the direct comparison test. The infinite sum in (A.11) converges for the given $x$, thus we can use it as a reference. For all $k>0$ it is indeed true that $0 \le \frac {k-1}{2^k} < \frac {k}{2^k}$, so our series converges.

First we will use the linearity property of summations and afterward apply (A.11) and (A.7).

$$\sum_{k=0}^{\infin} \frac {k-1}{2^k}=\sum_{k=0}^{\infin} \frac {k}{2^k}-\sum_{k=0}^{\infin} \frac {1}{2^k}=\frac{1/2}{(1-1/2)^2}-\frac{1}{1-1/2}=0$$

Exercise A.1-10

If $x=0$, then the result is zero, so assume that $x \neq 0$. Let $y=x^2$, since $|x|<1 \implies y<1$.

The story is similar to Exercise A.1-9, although we cannot use the same convergence test. The limit comparison test turns out to be appropriate. We will again use the sum in (A.11) as a reference (using y instead of x), since we know it converges. All terms in both sums are positive (recall that $k\ge1$), so we can calculate the limit.

$$\lim_{k \to \infin} \frac {(2k+1)y^k}{ ky^k}=\lim_{k \to \infin} \frac {2k+1}{k}=2 \qquad \checkmark$$

According to the test our sum converges. We can now proceed exactly as in the previous exercise.

$$\begin{align*} \sum_{k=1}^\infty (2k+1)y^k&=2\sum_{k=1}^\infty ky^k +\sum_{k=0}^\infty y^k-1 \\ &=\frac {2y}{(1-y)^2}+\frac {1}{1-y}-1 \\ &=\frac {y(3-y)}{(1-y)^2}\qquad \checkmark \end{align*}$$

We have tweaked the starting index for $k$ in the expansion, hence that extra -1. After reversing the initial substitution we get

$$\sum_{k=1}^\infty (2k+1)x^{2k}=\frac {x^2(3-x^2)}{(1-x^2)^2}$$

Exercise A.1-11

$$P=\prod_{k=2}^n (1-\frac {1}{k^2})=\prod_{k=2}^n \frac {k^2-1}{k^2}=\prod_{k=2}^n \frac {(k-1)(k+1)}{k^2} \qquad \checkmark$$

Observe that all terms of the product are positive. Therefore, we can convert a formula with a product to a formula with a summation by using the identity from the book.

$$\begin{align*} \lg P&=\sum_{k=2}^n(\lg (k-1)+\lg(k+1)-2\lg k) \\ &=\underbrace{\sum_{k=2}^n(\lg(k-1)-\lg k)}_{\text{telescopes}}+\underbrace{\sum_{k=2}^n(\lg(k+1)-\lg k)}_{\text{telescopes}} \\ &=\lg 1-\lg n-\lg2+\lg(n+1) \\ &=\lg \frac {n+1}{2n} \qquad \checkmark\\ &\therefore \prod_{k=2}^n (1-\frac {1}{k^2})=\frac {n+1}{2n} \end{align*}$$

Exercise A.2-1

$f(k) =\frac{1}{k^2}$ is a monotonically decreasing function, so we can use integral approximation (A.19) to bound the summation.

$$\sum_{k=1}^n \frac{1}{k^2}=1+\sum_{k=2}^n \frac{1}{k^2}\le 1+\int_1^n \frac{dx}{x^2}=1-\frac{1}{x}\bigg\rvert_1^n=2-\frac{1}{n}<2$$

Exercise A.2-2

$$\begin{align*} \sum_{k=0}^{\lfloor\lg n\rfloor}\left\lceil\frac{n}{2^k}\right\rceil &< \sum_{k=0}^{\lfloor\lg n\rfloor}\left(\frac{n}{2^k}+1\right) && \text{(by inequality (3.2))} \\ &\le \sum_{k=0}^{\lfloor\lg n\rfloor}\frac{n}{2^k} +\lg n+1 && \text{(by linearity property)}\\ &< \sum_{k=0}^\infty\frac{n}{2^k} +\lg n+1\\ &= \frac{n}{1-1/2}+\lg n+1 && \text{(by equation (A.7))} \\ &= 2n+\lg n+1 \\ &\le 3n && \text{(for all } n \ge 2 \text{) } \\ &\therefore \sum_{k=0}^{\lfloor\lg n\rfloor}\left\lceil\frac{n}{2^k}\right\rceil=O(n) \end{align*}$$

Exercise A.2-3

The idea is to split the range 1 to n into $\lfloor\lg n\rfloor$ pieces and lower-bound the contribution of each piece by 1/2. The pieces are the same as in the case of calculating the upper bound. The only difference is that the representative (pivot) of each piece is $1/2^{i+1}$ instead of $1/2^i$ for $i=0,1,...,\lfloor\lg n\rfloor-1$. Furthermore, some pieces may be missing in the last segment (for $i=\lfloor\lg n\rfloor$), but this is OK for getting the lower bound.

$$\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/2) \\ &= \lfloor\lg n\rfloor/2 \\ &> (\lg n - 1)/2 \\ &\therefore \sum_{k=1}^n\frac{1}{k} = \Omega(\lg n) \end{align*}$$

Exercise A.2-4

$f(k)=k^3$ is monotonically increasing, so we can use integral approximation (A.18) to bound the summation.

$$\begin{align*} \int_0^nx^3\,dx = \frac{n^4}{4}&\le \sum_{k=1}^nk^3 \le \int_1^{n+1}x^3\,dx =\frac{(n+1)^4-1}{4} \\ &\therefore \sum_{k=1}^nk^3=\Theta(n^4) \end{align*}$$

Exercise A.2-5

We would have an improper integral, since f(k) is undefined for $k=0$.

Problem A-1

a.

$$\begin{align*} \sum_{k=1}^n k^r = \Theta(n^{r+1}) && \text{(see Exercise A.1-5)} \end{align*}$$

b.

The upper bound is

$$\sum_{k=1}^n\lg^sk \le \sum_{k=1}^n\lg^sn = n\lg^sn \therefore \sum_{k=1}^n\lg^sk=O(n\lg^sn) \qquad \checkmark$$

The lower bound is

$$\begin{align*} \sum_{k=1}^n\lg^sk &\ge \sum_{k=\lceil{n/2}\rceil}^n\lg^sk \\ &\ge \sum_{k=\lceil{n/2}\rceil}^n\lg^s(\lceil{n/2}\rceil) \\ &= (n-\lceil{n/2}\rceil+1)\lg^s(\lceil{n/2}\rceil) \\ &= (\lfloor{n/2}\rfloor+1)\lg^s(\lceil{n/2}\rceil) \\ &\ge \lceil{n/2}\rceil\lg^s(\lceil{n/2}\rceil) \\ &\ge (n/2)\lg^s(n/2) \\ &= (n/2)\lg^s n-n/2 \\ &\therefore \sum_{k=1}^n\lg^sk=\Omega(n\lg^sn) \qquad \checkmark \end{align*}$$

Theorem 3.1 implies that $\sum_{k=1}^n\lg^sk=\Theta(n\lg^sn)$.

c.

The upper bound is

$$\sum_{k=1}^n k^r\lg^s k \le \sum_{k=1}^n n^r\lg^sn = n^{r+1}\lg^sn \therefore \sum_{k=1}^n k^r\lg^sk=O(n^{r+1}\lg^sn)\qquad \checkmark$$

The lower bound is

$$\begin{align*} \sum_{k=1}^n k^r\lg^sk &\ge \sum_{k=\lceil{n/2}\rceil}^n k^r\lg^sk \\ &\ge \sum_{k=\lceil{n/2}\rceil}^n {\lceil{n/2}\rceil}^r\lg^s(\lceil{n/2}\rceil) \\ &= (n-\lceil{n/2}\rceil+1) {\lceil{n/2}\rceil}^r\lg^s(\lceil{n/2}\rceil) \\ &= (\lfloor{n/2}\rfloor+1) {\lceil{n/2}\rceil}^r\lg^s(\lceil{n/2}\rceil) \\ &\ge {\lceil{n/2}\rceil}^{r+1}\lg^s(\lceil{n/2}\rceil) \\ &\ge (n/2)^{r+1}\lg^s(n/2) \\ &= (n/2)^{r+1}\lg^s n-(n/2)^{r+1} \\ &\therefore \sum_{k=1}^n k^r\lg^sk=\Omega(n^{r+1}\lg^sn)\qquad \checkmark \end{align*}$$

Theorem 3.1 implies that $\sum_{k=1}^n k^r\lg^sk=\Theta(n^{r+1}\lg^sn)$.