> For the complete documentation index, see [llms.txt](https://evarga.gitbook.io/sh-intro-to-algs/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://evarga.gitbook.io/sh-intro-to-algs/part-viii-appendix-mathematical-background/appendix-a.md). # 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\*} $$ {% hint style="info" %} Another possibility is to simply use $$x=-\frac{1}{2}$$ in equation (A.7). {% endhint %} ### 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})$$. {% hint style="info" %} You may also want to look at [Faulhaber's formula](https://en.wikipedia.org/wiki/Faulhaber%27s_formula). It generalizes the sum of integer powers. {% endhint %} ### A.1-6 Differentiating both sides of the in๏ฌnite 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 ๐ŸŒŸ {% hint style="success" %} Introduces and proves the identity $$\sum\_{k=1}^n \sqrt {k\lg k}=\Theta(n^{3/2} {\lg^{1/2} n})$$. {% endhint %} 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](#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 ๐ŸŒŸ {% hint style="success" %} Introduces and proves the identity $$\sum\_{k=1}^n \frac {1}{2k-1} =\ln ({\sqrt{n}}) +O(1)$$. {% endhint %} 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 ๐ŸŒŸ {% hint style="success" %} Introduces the [direct comparison test](https://en.wikipedia.org/wiki/Direct_comparison_test) for deciding about convergence of infinite series and shows that $$\sum\_k (k-1)/2^k=0$$. {% endhint %} We have an infinite sum similar to the one in (A.11) with $$x=1/2$$. The linearity property also applies to in๏ฌnite 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 ๐ŸŒŸ {% hint style="success" %} Introduces the [limit comparison test](https://en.wikipedia.org/wiki/Limit_comparison_test) and shows that $$\sum\_{k=1}^\infty (2k+1)x^{2k}=\frac {x^2(3-x^2)}{(1-x^2)^2}$$. {% endhint %} 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 ๐ŸŒŸ {% hint style="success" %} 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}$$. {% endhint %} $$ 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\*} $$ {% hint style="info" %} 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. {% endhint %} ### 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](https://en.wikipedia.org/wiki/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)$$. --- # Agent Instructions This documentation is published with GitBook. GitBook is the documentation platform designed so that both humans and AI agents can read, navigate, and reason over technical content effectively. Learn more at gitbook.com. ## Querying This Documentation If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question. Perform an HTTP GET request on the current page URL with the `ask` query parameter: ``` GET https://evarga.gitbook.io/sh-intro-to-algs/part-viii-appendix-mathematical-background/appendix-a.md?ask= ``` The question should be specific, self-contained, and written in natural language. The response will contain a direct answer to the question and relevant excerpts and sources from the documentation. Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.