Sums of geometric series

Sun, Jul 23, 2017 02:00 CEST

Tags: Identities, Inequalities, Analysis of Algorithms

Among the identities that are useful in the analysis of algorithms, this one shows how sums of geometric series converge when the ratio is smaller than one (in absolute value). It occurs in divide an conquer schemes. For example, it allows to show that hierarchical cuttings for \(n\) hyperplanes in \(d\) dimensions only need space proportional to \(n^d\).

\[ \sum_{i=0}^{\infty} \binom{i+j}{j} x^i = \frac{1}{ {(1-x)}^{j+1} }, \forall j \in \mathbb{N}, \forall x \in (-1,1). \]

That’s nice. There are many ways to prove it, a cool one is to first prove that

\[ \sum_{i=0}^{\infty} x^i = \frac{1}{ {(1-x)} }, \forall x \in (-1,1), \]

and then to notice that

$$ \frac{1}{ {(1-x)}^{j+1} } = {\left(\sum_{i=0}^{\infty} x^i \right)}^{j+1} = \sum_{i=0}^{\infty} \binom{i+j}{j} x^i, \forall j \in \mathbb{N}, \forall x \in (-1,1). $$

because \(\binom{i+j}{j}\) denotes the number of ways to partition the exponent of \(x^i\) into a permutation of \(j+1\) integers.

More generally, one has

\[ \sum_{i=0}^{k} \binom{i+j}{j} x^i = \frac{1}{ {(1-x)}^{j+1} } - \sum_{i=0}^{j} \frac{\binom{k+i}{i} x^{k+1}}{ {(1-x)}^{j-i+1} }, \forall j \in \mathbb{N}, \forall x \in \mathbb{R} \setminus \{\,1\,\}. \]