Inductive proofs are fun.

Binomial coefficients

These series identities are based on exercises from the first chapter of Statistical Inference¹

Alternating sum equal zero

Theorem

For $n \geq 2$ , $\sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k}) = 0$

Proof

For $n = 2$ , $\sum_{k = 0}^{2} {(- 1)}^{k} (\binom{2}{k}) = 1 - 2 + 1 = 0$ .

Induction hypothesis (IH): assume that this holds for $n \geq 2$ . We want to show that $\sum_{k = 0}^{n + 1} {(- 1)}^{k} (\binom{n + 1}{k}) = 0$

follows. Use Pascal's rule:

$\begin{matrix} (\binom{n}{k}) & = \frac{n!}{k! (n - k)!} \\ = \frac{(n - 1)! (k + n - k)}{k! (n - k)!} \\ = (n - 1)! (\frac{k}{k! (n - k)!} + \frac{n - k}{k! (n - k)!}) \\ = \frac{(n - 1)!}{(k - 1)! (n - 1 - k + 1)!} + \frac{(n - 1)!}{k! (n - 1 - k)!} \\ = (\binom{n - 1}{k - 1}) + (\binom{n - 1}{k}) \end{matrix}$

Then,

$\begin{matrix} \sum_{k = 0}^{n + 1} (- 1)^{k} (\binom{n + 1}{k}) \\ = (- 1)^{0} (\binom{n + 1}{0}) + \sum_{k = 1}^{n} (- 1)^{k} \overset{Pascal's rule}{\overset{⏞}{(\binom{n + 1}{k})}} + (- 1)^{n + 1} (\binom{n + 1}{n + 1}) \\ = (- 1)^{0} (\binom{n}{0}) + \sum_{k = 1}^{n} (- 1)^{k} ((\binom{n}{k}) + (\binom{n}{k - 1})) + (- 1)^{n + 1} (\binom{n}{n}) \\ = (- 1)^{0} (\binom{n}{0}) + \sum_{k = 1}^{n} (- 1)^{k} (\binom{n}{k}) + \sum_{k = 1}^{n} (- 1)^{k} (\binom{n}{k - 1}) + (- 1)^{n + 1} (\binom{n}{n}) \\ = \overset{IH}{\overset{⏞}{\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k})}} + \sum_{k = 1}^{n} (- 1)^{k} (\binom{n}{k - 1}) + (- 1)^{n + 1} (\binom{n}{n}) \\ = 0 + \sum_{k = 0}^{n - 1} (- 1)^{k - 1} (\binom{n}{k}) + (- 1)^{n + 1} (\binom{n}{n}) \\ = (- 1) (\sum_{k = 0}^{n - 1} (- 1)^{k} (\binom{n}{k}) + (- 1)^{n} (\binom{n}{n})) \\ = (- 1) \overset{IH}{\overset{⏞}{\sum_{k = 0}^{n} (- 1)^{k} (\binom{n}{k})}} \\ = 0 \end{matrix}$

and by the principle of induction for $n \geq 2$ , $\sum_{k = 0}^{n} {(- 1)}^{k} (\binom{n}{k}) = 0 .$

Sum equal two to the power of n

Theorem

For $n \geq 2$ , $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n}$ holds.

Proof

Let $n = 2$ , then $\sum_{k = 0}^{2} (\binom{2}{k}) = 1 + 2 + 1 = 4 = 2^{2}$

Assume this holds for $n \geq 2$ . Then,

$\begin{matrix} \sum_{k = 0}^{n + 1} (\binom{n + 1}{k}) \\ = (\binom{n + 1}{0}) + \sum_{k = 1}^{n} (\binom{n + 1}{k}) + (\binom{n + 1}{n + 1}) \\ = (\binom{n}{n}) + \sum_{k = 1}^{n} (\binom{n}{k - 1}) + \sum_{k = 1}^{n} (\binom{n}{k}) + (\binom{n}{0}) \\ = \sum_{k = 0}^{n - 1} (\binom{n}{k}) + (\binom{n}{n}) + (\binom{n}{0}) + \sum_{k = 1}^{n} (\binom{n}{k}) \\ = \sum_{k = 0}^{n} (\binom{n}{k}) + \sum_{k = 0}^{n} (\binom{n}{k}) \\ = 2 \cdot 2^{n} = 2^{n + 1} \end{matrix}$

by the induction hypothesis and by the principle of induction for $n \geq 2$ , $\sum_{k = 0}^{n} (\binom{n}{k}) = 2^{n} .$

Sum equal n times two to the power of n minus one

Theorem

For $n \geq 2$ , $\sum_{k = 1}^{n} k (\binom{n}{k}) = n 2^{n - 1}$ holds.

Proof

Let $n = 2$ , then $\sum_{k = 1}^{2} k (\binom{2}{k}) = 2 + 2 = 4 = 2 \cdot 2^{2 - 1}$

Induction hypothesis (IH): Assume this holds for $n \geq 2$ . We want to show that $\sum_{k = 1}^{n + 1} k (\binom{n + 1}{k}) = (n + 1) 2^{n}$ follows. For $n + 1$ ,

$\begin{matrix} \sum_{k = 1}^{n + 1} k (\binom{n + 1}{k}) \\ = \sum_{k = 1}^{n} k (\binom{n + 1}{k}) + (n + 1) (\binom{n + 1}{n + 1}) \\ = \overset{Pascal's rule}{\overset{⏞}{\sum_{k = 1}^{n} k (\binom{n + 1}{k})}} + n (\binom{n + 1}{n + 1}) + (\binom{n + 1}{n + 1}) \\ = \sum_{k = 1}^{n} k (\binom{n}{k - 1}) + \overset{IH}{\overset{⏞}{\sum_{k = 1}^{n} k (\binom{n}{k})}} + n (\binom{n}{n}) + (\binom{n}{n}) \\ = \sum_{k = 1}^{n} k (\binom{n}{k - 1}) + (\binom{n}{n}) + n 2^{n - 1} + n (\binom{n}{n}) \\ = \sum_{k = 1}^{n} ((k - 1) (\binom{n}{k - 1}) + (\binom{n}{k - 1})) + (\binom{n}{n}) + n 2^{n - 1} + n (\binom{n}{n}) \\ = \sum_{k = 1}^{n} (k - 1) (\binom{n}{k - 1}) + n (\binom{n}{n}) + \sum_{k = 1}^{n} (\binom{n}{k - 1}) + (\binom{n}{n}) + n 2^{n - 1} \\ = \sum_{k = 0}^{n - 1} k (\binom{n}{k}) + n (\binom{n}{n}) + \sum_{k = 0}^{n - 1} (\binom{n}{k}) + (\binom{n}{n}) + n 2^{n - 1} \\ = \sum_{k = 0}^{n} k (\binom{n}{k}) + \sum_{k = 0}^{n} (\binom{n}{k}) + n 2^{n - 1} \\ = \overset{IH}{\overset{⏞}{\sum_{k = 1}^{n} k (\binom{n}{k})}} + \overset{= 2^{n}}{\overset{⏞}{\sum_{k = 0}^{n} (\binom{n}{k})}} + n 2^{n - 1} \\ = n 2^{n - 1} + 2^{n} + n 2^{n - 1} \\ = n 2^{n} + 2^{n} = (n + 1) 2^{n} \end{matrix}$

and by the principle of induction for $n \geq 2$ , $\sum_{k = 1}^{n} k (\binom{n}{k}) = n 2^{n - 1} .$

Casella, G., & Berger, R. L. (2002). Probability Theory. Statistical inference (2nd ed.). Cengage. ↩

Inductive proofs

Binomial coefficients

Alternating sum equal zero

Theorem

Proof

Sum equal two to the power of n

Theorem

Proof

Sum equal n times two to the power of n minus one

Theorem

Proof

Tags