Solving binomial theorem via induction

Question

I'm trying to prove binomial theorem by induction, but I'm a little stuck. I would look at online resources as this problem has been done many times, but the version I am trying to prove the binomial theorem in a different form.

$$(1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k$$

I'm mostly confused as to how I can make the left side be equivalent to a summation, any help is appreciated. Try to hint me along!

Answer 1

We show by induction the following is valid for $n\geq 0$ \begin{align*} (1 + x)^n = \sum_{k = 0}^{n} \binom{n}{k} x^k \end{align*}

Base step: $n=0$

We have to show \begin{align*} (1 + x)^0 = \sum_{k = 0}^{0} \binom{0}{k} x^k \end{align*}

Since the left-hand side is $$(1+x)^0=1$$ and the right-hand side is $$\sum_{k = 0}^{0} \binom{0}{k} x^k=\binom{0}{0}x^0=1,$$ both sides are equal and the claim is valid for $n=0$.

Induction hypothesis: $n=N$

We assume the validity of \begin{align*} (1 + x)^N = \sum_{k = 0}^{N} \binom{N}{k} x^k\tag{1} \end{align*}

Induction step: $n=N+1$

We have to show \begin{align*} (1 + x)^{N+1} = \sum_{k = 0}^{N+1} \binom{N+1}{k} x^k \end{align*}

We obtain \begin{align*} (1 + x)^{N+1} &= (1+x)(1+x)^N\tag{2}\\ &=(1+x)\sum_{k = 0}^{N} \binom{N}{k} x^k\tag{3}\\ &=\sum_{k = 0}^{N} \binom{N}{k} x^k+\sum_{k = 0}^{N} \binom{N}{k} x^{k+1}\tag{4}\\ &=\binom{N}{0}x^0+\sum_{k=1}^N\binom{N}{k}x^k+\sum_{k=0}^{N-1}\binom{N}{k}x^{k+1}+\binom{N}{N}x^{N+1}\tag{5}\\ &=\binom{N+1}{0}x^0+\sum_{k=1}^N\binom{N}{k}x^k+\sum_{k=1}^{N}\binom{N}{k-1}x^{k}+\binom{N+1}{N+1}x^{N+1}\tag{6}\\ &=\sum_{k=0}^{N+1}\binom{N+1}{k}x^k\tag{7} \end{align*} and the claim follows.

Comment:

• In (2) we split the product, since we want to apply the induction hypothesis.

• In (3) we apply the induction hypothesis (1).

• In (4) we multiply out.

• In (5) we separate the first summand $\binom{N}{0}$ from the left sum and the last summand $\binom{N}{N}x^{N+1}$ from the right sum.

• In (6) we use the binomial identities \begin{align*} \binom{N}{0}=\binom{N+1}{0}=1\qquad\text{and}\qquad\binom{N}{N}=\binom{N+1}{N+1}=1 \end{align*} We also shift the index $k$ of the right sum by one to start from $k=1$. This all is a preparation for the next step to easily collect all the terms in one sum.

• In (7) we apply the binomial identity \begin{align*} \binom{N}{k}+\binom{N}{k-1}=\binom{N+1}{k} \end{align*} and the two sums can be merged into one sum. We also see the left-most term $\binom{N+1}{0}$ and the right-most term $\binom{N+1}{N+1}$ can be made part of the sum using index $k=0$ and $k=N+1$.