Lesson 5

Let us start with the proof of an auxiliary lemma that shows the growth of the sum of a geometric series. It also helps to understand where the three cases in the theorem come from.

Lemma. Let \(\alpha>0\). Then \[\sum_{i=0}^{n}\alpha^{i}= \begin{cases}\Theta(\alpha^n) & \text{if \(\alpha>1\),}\\ \Theta(n) & \text{if \(\alpha=1\),}\\ \Theta(1) & \text{if \(\alpha<1\).}\end{cases}\] Less formally, the lemma can be stated as follows: the sum of an increasing geometric series grows like its last term, the sum of a decreasing series grows like a constant, and the sum of a constant series grows like the number of terms.

Proof. The formula for geometric series for \(\alpha \neq 1\) (which we divide by) is: \[\sum_{i=0}^{n}\alpha^{i} = \frac{\alpha^{n+1}-1}{\alpha-1}\] Consider three cases.

1. \(\alpha>1\). Then \(\alpha^{n}(\alpha-1) \le \alpha^{n+1}-1 < \alpha^{n+1}\) and \(\frac{\alpha^{n+1}-1}{\alpha-1}\) can be bounded as: \[\alpha^{n} \le \frac{\alpha^{n+1}-1}{\alpha-1}< \frac{\alpha}{\alpha-1}\alpha^{n} \ .\]
2. \(\alpha=1\). Then the formula cannot be used, but the sum equals \(n+1\).
3. \(\alpha<1\). Then \(1-\alpha \le 1-\alpha^{n+1}< 1\) and \(\frac{\alpha^{n+1}-1}{\alpha-1}\) can be bounded as: \[1 \le \frac{1-\alpha^{n+1}}{1-\alpha}< \frac{1}{1-\alpha}\ .\]