search

#### Tag - Identities

Sums of geometric series Sun, Jul 23, 2017 02:00 CEST

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).$

Converging series Fri, Apr 21, 2017 02:00 CEST

Let $$-1 < x < 1$$,

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

Log Log Log Thu, Apr 14, 2016 02:00 CEST

## Theorem

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

Binomial coefficient tricks Wed, Jun 24, 2015 00:00 CEST

$$\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.