# Sum of Binomial Coefficients over Lower Index

## Theorem

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

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

### Corollary

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

## Proof 1

For all $n \in \N$, let $P \left({n}\right)$ be the proposition:

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

$P(0)$ is true, as this just says $\dbinom 0 0 = 1$. This holds by definition.

### Basis for the Induction

$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 $P \left({k}\right)$ is true, where $k \ge 1$, then it logically follows that $P \left({k + 1}\right)$ is true.

So this is our induction hypothesis:

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

Then we need to show:

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

### Induction Step

This is our induction step:

 $\displaystyle \sum_{i \mathop = 0}^{k + 1} \binom {k + 1} i$ $=$ $\displaystyle \binom {k + 1} 0 + \sum_{i \mathop = 1}^k \binom {k + 1} i + \binom {k + 1} {k + 1}$ $\displaystyle$ $=$ $\displaystyle \binom {k + 1} 0 + \sum_{i \mathop = 1}^k \left({\binom k {i - 1} + \binom k i}\right) + \binom {k + 1} {k + 1}$ Pascal's Rule $\displaystyle$ $=$ $\displaystyle \left({\sum_{i \mathop = 0}^{k - 1} \binom k i + \binom {k + 1} {k + 1} }\right) + \left({\binom {k + 1} 0 + \sum_{i \mathop = 1}^k \binom k i}\right)$ Translation of Index Variable of Summation $\displaystyle$ $=$ $\displaystyle \left({\sum_{i \mathop = 0}^{k - 1} \binom k i + \binom k k}\right) + \left({\binom k 0 + \sum_{i \mathop = 1}^k \binom k i}\right)$ as $\displaystyle \binom {k + 1} {k + 1} = \binom k k = 1$ and $\displaystyle \binom {k + 1} 0 = \binom k 0 = 1$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = 0}^k \binom k i + \sum_{i \mathop = 0}^k \binom k i$ Translation of Index Variable of Summation $\displaystyle$ $=$ $\displaystyle 2^k + 2^k$ $\displaystyle$ $=$ $\displaystyle 2^{k + 1}$

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

Therefore:

$\displaystyle \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, $\displaystyle \sum_{i \mathop = 0}^n \binom n i$ is the total number of subsets of $S$.

Hence $\displaystyle \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:

$\displaystyle \forall n \in \Z_{\ge 0}: \left({x + y}\right)^n = \sum_{i \mathop = 0}^n \binom n i x^{n - i}y^i$

Putting $x = y = 1$ we get:

 $\displaystyle 2^n$ $=$ $\displaystyle \left({1 + 1}\right)^n$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = 0}^n \binom n i 1^{n-i} \ 1^i$ $\displaystyle$ $=$ $\displaystyle \sum_{i \mathop = 0}^n \binom n i$

$\blacksquare$