Sum of Binomial Coefficients over Lower Index

From ProofWiki
Jump to navigation Jump to search

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


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$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Sum_of_Binomial_Coefficients_over_Lower_Index&oldid=626756"