A. Summations

Exercises

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)$.

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

A.1-3

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

A.1-4

Notice that our infinite series is absolutely convergent, since it transforms into a decreasing geometric series with $x=\frac {1}{2}$. Consequently, we can even rearrange the terms, although the derivation below only relies on the linearity of convergent series. 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 simply use $x=-\frac{1}{2}$ in equation (A.7).

A.1-5

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.

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

A.1-7 🌟

Introduces and proves the identity $\sum_{k=1}^n \sqrt {k\lg k}=\Theta(n^{3/2} {\lg^{1/2} n})$.

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})$.

★ A.1-8 🌟

Introduces and proves the identity $\sum_{k=1}^n \frac {1}{2k-1} =\ln ({\sqrt{n}}) +O(1)$.

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 +\ln 2+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\ln2+2O(1) \\ 2\sum_{k=1}^n \frac {1}{2k-1}+H_n &=2\ln n +2\ln2+2O(1) \\ 2\sum_{k=1}^n \frac {1}{2k-1}+\ln n + O(1) &=2\ln n +2\ln2+2O(1) \\ 2\sum_{k=1}^n \frac {1}{2k-1} &=\ln n +2\ln2+2O(1)-O(1) \\ \sum_{k=1}^n \frac {1}{2k-1} &=\ln {\sqrt{n}} +O(1). \end{align*}$$

★ A.1-9 🌟

Introduces the direct comparison test for deciding about convergence of infinite series and shows that $\sum_k (k-1)/2^k=0$.

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 first we must prove that our series converges. For the sake of variety, let’s use 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}=-1+\sum_{k=1}^{\infin} \frac {k-1}{2^k}=-1+\sum_{k=1}^{\infin} \frac {k}{2^k}-\sum_{k=1}^{\infin} \frac {1}{2^k}=-1+\frac{1/2}{(1-1/2)^2}-\frac{1}{1-1/2}+1=0.$$

★ A.1-10 🌟

Introduces the limit comparison test and shows that $\sum_{k=1}^\infty (2k+1)x^{2k}=\frac {x^2(3-x^2)}{(1-x^2)^2}$.

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 the previous exercise, 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}.$$

★ A.1-11 🌟

Demonstrates the exp-log technique, telescoping sums, and shows that $\prod_{k=2}^n \left(1-\frac {1}{k^2}\right)=\frac {n+1}{2n}$.

$$P=\prod_{k=2}^n \left(1-\frac {1}{k^2}\right)=\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 \left(1-\frac {1}{k^2}\right)=\frac {n+1}{2n}. \end{align*}$$

There is also an alternative method by noticing that $P = \left( \prod_{k=2}^n \frac{k-1}{k} \right) \times \left( \prod_{k=2}^n \frac{k+1}{k} \right)$. This leads to a telescoping product.

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.$$

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 \\ &\therefore \sum_{k=0}^{\lfloor\lg n\rfloor}\left\lceil\frac{n}{2^k}\right\rceil=O(n). \end{align*}$$

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

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

A.2-5

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

Problems

A-1 Bounding summations

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 =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 =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)$.