Sum of Binomial Coefficients for Given n

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 $\displaystyle \binom 0 0 = 1$. This holds by definition.

Basis for the Induction

$P(1)$ is true, as this just says $\displaystyle \binom 1 0 + \binom 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 $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 \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \sum_{i=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 \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\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}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	from Pascal's Rule
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\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)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Permutation of Indices
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\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)\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	as $\displaystyle \binom {k+1} {k+1} = \binom k k = 1$ and $\displaystyle \binom {k+1} 0 = \binom k 0 = 1$
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{i \mathop = 0}^k \binom k i + \sum_{i \mathop = 0}^k \binom k i\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	Permutation of Indices
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^k + 2^k\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle 2^{k+1}\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

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_+: \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 \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle 2^n\)	\(=\)	\(\displaystyle \left({1 + 1}\right)^n\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{i \mathop = 0}^n \binom n i 1^{n-i} \ 1^i\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)
	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)	\(=\)	\(\displaystyle \sum_{i \mathop = 0}^n \binom n i\)	\(\displaystyle \)	\(\displaystyle \)	\(\displaystyle \)

$\blacksquare$

Sources

• Murray R. Spiegel: Mathematical Handbook of Formulas and Tables (1968): $3.7$
• George E. Andrews: Number Theory (1971): $\S 3.1$: Exercise $2$