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

{% hint style="info" %}
You may also want to look at [Faulhaber's formula](https://en.wikipedia.org/wiki/Faulhaber's_formula). It generalizes the sum of integer powers.
{% endhint %}

## 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](#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](https://en.wikipedia.org/wiki/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](#exercise-a.1-9), although we cannot use the same convergence test. The [limit comparison test](https://en.wikipedia.org/wiki/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

&#x20;$$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](https://en.wikipedia.org/wiki/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)$$.