4 Geometric sums
Before we finally state and prove the Master theorem, we need to prove two basic properties regarding geometric sums. These are both straightforward proofs with no clever tricks or surprises, but are still stated for the sake of completeness.
Let \(x \in \mathbb {R}\) and \(n \in \mathbb {N}\). A geometric sum is a sum of the form
\[ \sum _{k=0}^n x^k. \]
Let \(x \neq 1\) and \(n \in \mathbb {N}\). Then the following inequality holds:
\[ \sum _{k=0}^n x^k \leq \frac{x^{n+1} - 1}{x - 1} \]
Proof
We prove the proposition by induction on \(n\). The base case is simple:
\begin{align*} \frac{x^{0+1} - 1}{x-1} & = \\ & = \frac{x^1 - 1}{x-1} \\ & = \frac{x-1}{x-1} \\ & = 1 \\ & = x^0 \\ \end{align*}
The inductive step is also straightforward:
\begin{align*} \sum _{k=0}^{n} x^k & = \sum _{k=0}^{n-1} x^k + x^n \\ & = \frac{x^n - 1}{x-1} + \frac{x-1}{x-1} x^n \\ & = \frac{x^n - 1}{x-1} + \frac{x^{n+1} - x^n}{x-1} \\ & = \frac{x^{n+1} - 1}{x-1} \end{align*}
Let \(0 {\lt} x {\lt} 1\) and \(n \in \mathbb {N}\). Then the following inequality holds:
\[ \sum _{k=0}^n x^k \leq \frac{1}{1-x} \]
Proof
The inequality follows directly from the previous proposition and the restriction on values of \(x\):
\begin{align*} \sum _{k=0}^n x^k & = \frac{x^{n+1} - 1}{x-1} \\ & = \frac{1 - x^{n+1}}{1-x} \\ & \leq \frac{1 - x^{n+1}}{1-x} \end{align*}