Sum of Odd Index Binomial Coefficients

From ProofWiki

Jump to: navigation, search

Theorem

$\displaystyle \sum_{i \ge 0} \binom n {2 i + 1} = 2^{n-1}$

where $\binom n i$ is a binomial coefficient.

That is:

$\displaystyle \binom n 1 + \binom n 3 + \binom n 5 + \cdots = 2^{n-1}$

$\displaystyle \sum_{i \in \Z} \binom n i = 2^n$

That is:

$\displaystyle \binom n 0 + \binom n 1 + \binom n 2 + \binom n 3 + \cdots + \binom n n = 2^n$

as $\displaystyle \binom n i = 0$ for $i < 0$ and $i > n$.

This can be written more conveniently as:

$\displaystyle (1) \qquad \binom n 0 + \binom n 1 + \binom n 2 + \binom n 3 + \binom n 4 + \cdots = 2^n$

$\displaystyle \sum_{i \in \Z} \left({-1}\right)^i \binom n i = 0$

That is:

$\displaystyle (2) \qquad \binom n 0 - \binom n 1 + \binom n 2 - \binom n 3 + \binom n 4 - \cdots = 0$

Subtracting $(2)$ from $(1)$, we get:

$\displaystyle 2 \binom n 1 + 2 \binom n 3 + 2 \binom n 5 + \cdots = 2^n$

as the even index coefficients cancel out.

Dividing by $2$ throughout gives us the result.

$\blacksquare$