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). \]

Let \(-1 < x < 1\),

$$ 1 + x + x^2 + x^3 + x^4 + \cdots = \frac{1}{1-x}. $$

Theorem

$$ \frac{\log n}{\log \log n}! = \Theta(n) $$

$$ \binom{n}{k} = \binom{n}{n-k} $$

holds because keeping \(k\) elements from \(n\) elements is equivalent to discarding \(n-k\) elements from \(n\) elements.