Sum of Binomial Coefficients over Lower Index/Proof 1
Jump to navigation
Jump to search
Theorem
- $\ds \sum_{i \mathop = 0}^n \binom n i = 2^n$
Proof
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 holds by Binomial Coefficient with Zero and Binomial Coefficient with One (or Binomial Coefficient with Self).
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$