Home » Blog » Prove the binomial theorem by induction

Prove the binomial theorem by induction

Prove the binomial theorem:

    \[ (a+b)^n = \sum_{k=0}^n \binom{n}{k} a^k b^{n-k}. \]

Further, prove the formulas:

    \[ \sum_{k=0}^n \binom{n}{k} = 2^n \qquad \text{and} \qquad \sum_{k=0}^n (-1)^k \binom{n}{k}, \ \ \text{for } n > 0. \]


First, we prove the binomial theorem by induction.
Proof. For the case n =1 on the left we have,

    \[ (a+b)^n = (a+b)^1 = a+b. \]

On the right,

    \[ \sum_{k=0}^n \binom{n}{k} a^k b^{n-k} = \sum_{k=0}^1 \binom{n}{k} a^k b^{n-k} = \binom{1}{0} a^0 b^{1-0} + \binom{1}{1}a^1 b^{1-1} = b + a = a + b. \]

Hence, the formula is true for the case n=1.
Assume then that the formula is true for some n = m \in \mathbb{Z}_{>0}. Then we have,

    \begin{align*}  &&(a+b)^m &= \sum_{k=0}^m \binom{m}{k} a^k b^{m-k} \\ &\implies & (a+b)^{m+1} &= \left(\sum_{k=0}^m \binom{m}{k} a^k b^{m-k} \right) (a+b) \\ &\implies & (a+b)^{m+1} &= \sum_{k=0}^m \binom{m}{k} a^{k+1} b^{m-k} + \sum_{k=0}^m \binom{m}{k} a^k b^{m+1-k}\\ &&&= a^{m+1} + \sum_{k=0}^{m-1} \binom{m}{k} a^{k+1} b^{m-k} + \sum_{k=0}^m \binom{m}{k} a^k b^{m+1-k} \\ &&&= a^{m+1} + \sum_{k=1}^m \binom{m}{k-1} a^{k} b^{m+1-k} + \sum_{k=0}^m \binom{m}{k} a^k b^{m+1-k} & (\text{reindex})\\ &&&= a^{m+1} + b^{m+1} + \sum_{k=1}^m \binom{m}{k-1} a^{k} b^{m+1-k} + \sum_{k=1}^m \binom{m}{k} a^k b^{m+1-k} \\ &&&= a^{m+1} + b^{m+1} + \sum_{k=1}^m \left( \left( \binom{m}{k-1} + \binom{m}{k} \right) (a^k b^{m+1-k}) \right) \\ &&&= a^{m+1} + b^{m+1} + \sum_{k=1}^m \binom{m+1}{k} a^k b^{m+1-k} & (\text{I.4.10, #3}) \\ &&&= \sum_{k=0}^{m+1} \binom{m+1}{k} a^k b^{m+1-k}. \end{align*}

Thus, if the formula is true for the case m then it is true for the case m+1. Hence, we have proved the formula for all n \in \mathbb{Z}_{>0}. \qquad \blacksquare

As an application of the binomial theorem we then prove the two formulas.
For the first, apply the binomial theorem with a = b = 1. Then,

    \[ (a+b)^n = \sum_{k=0}^n a^k b^{n-k} \quad \implies \quad (1+1)^n = 2^n = \sum_{k=0}^n \binom{n}{k}. \]

For the second, apply the binomial theorem with a=-1 and b =1. Then,

    \[ (a+b)^n = (-1+1)^n = 0^n = 0 = \sum_{k=0}^n \binom{n}{k} (-1)^k. \]

3 comments

  1. Anonymous says:

    Hi,

    In line 4, the “a m plus one” should not be taken out, as the first term of the final expression is “b m plus one” only. Taking out the am+1 also means there is an “m-1” term in the summation term, which is currently improperly taken out by reindexing.

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):