Sum of Binomial Coefficients over Lower Index

Theorem

$\ds \sum_{i \mathop = 0}^n \binom n i = 2^n$

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

Corollary

$\ds \forall n \in \Z_{\ge 0}: \sum_{i \mathop \in \Z} \binom n i = 2^n$

Proof 1

For all $n \in \N$, let $\map P n$ be the proposition:

$\ds \sum_{i \mathop = 0}^n \binom n i = 2^n$

$\map P 0$ is true, as this just says $\dbinom 0 0 = 1$.

This holds by definition.

Basis for the Induction

$\map P 1$ is true, as this just says $\dbinom 1 0 + \dbinom 1 1 = 2$.

This is our basis for the induction.

Induction Hypothesis

Now we need to show that, if $\map P k$ is true, where $k \ge 1$, then it logically follows that $\map P {k + 1}$ is true.

So this is our induction hypothesis:

$\ds \sum_{i \mathop = 0}^k \binom k i = 2^k$

Then we need to show:

$\ds \sum_{i \mathop = 0}^{k + 1} \binom {k + 1} i = 2^{k + 1}$

Induction Step

This is our induction step:

 $\ds \sum_{i \mathop = 0}^{k + 1} \binom {k + 1} i$ $=$ $\ds \binom {k + 1} 0 + \sum_{i \mathop = 1}^k \binom {k + 1} i + \binom {k + 1} {k + 1}$ $\ds$ $=$ $\ds \binom {k + 1} 0 + \sum_{i \mathop = 1}^k \paren {\binom k {i - 1} + \binom k i} + \binom {k + 1} {k + 1}$ Pascal's Rule $\ds$ $=$ $\ds \paren {\sum_{i \mathop = 0}^{k - 1} \binom k i + \binom {k + 1} {k + 1} } + \paren {\binom {k + 1} 0 + \sum_{i \mathop = 1}^k \binom k i}$ Translation of Index Variable of Summation $\ds$ $=$ $\ds \paren {\sum_{i \mathop = 0}^{k - 1} \binom k i + \binom k k} + \paren {\binom k 0 + \sum_{i \mathop = 1}^k \binom k i}$ as $\dbinom {k + 1} {k + 1} = \dbinom k k = 1$ and $\dbinom {k + 1} 0 = \dbinom k 0 = 1$ $\ds$ $=$ $\ds \sum_{i \mathop = 0}^k \binom k i + \sum_{i \mathop = 0}^k \binom k i$ Translation of Index Variable of Summation $\ds$ $=$ $\ds 2^k + 2^k$ $\ds$ $=$ $\ds 2^{k + 1}$

So $\map P k \implies \map P {k + 1}$ and the result follows by the Principle of Mathematical Induction.

Therefore:

$\ds \forall n \in \N: \sum_{i \mathop = 0}^n \binom n i = 2^n$

$\blacksquare$

Proof 2

Let $S$ be a set with $n$ elements.

From the definition of $r$-combination, $\ds \sum_{i \mathop = 0}^n \binom n i$ is the total number of subsets of $S$.

Hence $\ds \sum_{i \mathop = 0}^n \binom n i$ is equal to the cardinality of the power set of $S$.

Hence the result.

$\blacksquare$

Proof 3

From the Binomial Theorem, we have that:

$\ds \forall n \in \Z_{\ge 0}: \paren {x + y}^n = \sum_{i \mathop = 0}^n \binom n i x^{n - i} y^i$

Putting $x = y = 1$ we get:

 $\ds 2^n$ $=$ $\ds \paren {1 + 1}^n$ $\ds$ $=$ $\ds \sum_{i \mathop = 0}^n \binom n i 1^{n - i} 1^i$ $\ds$ $=$ $\ds \sum_{i \mathop = 0}^n \binom n i$

$\blacksquare$