If you find any mistakes, please make a comment! Thank you.

## Use induction to show binomial theorem

Solution:

### Part a

Note that by direct computations we have
$${1 \choose 1}= {1 \choose 0}={2 \choose 0}={2\choose 2}={3\choose 0}={3 \choose 3}=1,$$ $${2 \choose 1}=2,\qquad {3 \choose 1}={3 \choose 2}=3.$$
If $n=1$, this is clear as
$$(a+b)^1=a+b={1 \choose 0}a+{1 \choose 1}b.$$ If $n=2$, we have (by FOIL method)
$$(a+b)(a+b)=a^2+ab+ba+b^2=a^2+2ab+b^2.$$ Hence $$(a+b)^2=a^2+2ab+b^2={2 \choose 0}a^2+{2 \choose 1}ab+{2 \choose 2}b^2.$$ If $n=3$, we have
$$(a+b)^3=(a+b)(a^2+2ab+b^2)=a^3+2a^2b+ab^2+ba^2+2ab^2+b^3=a^3+3a^2b+3ab^2+b^3.$$
Hence
$$(a+b)^3=a^3+3a^2b+3ab^2+b^3={3 \choose 0}a^3+{3 \choose 1}a^b+{3 \choose 2}ab^2+{3 \choose 3}b^3.$$

### Part b

We show
\label{eq:1-12-2}
{n \choose k-1}+{n \choose k}={n+1 \choose k}
directly. We shall use
$$k!=(k-1)!\cdot k,\ (n+1)!=n!(n+1),\ (n+1-k)!=(n-k)!(n+1-k).$$ Explicitly, we have
\begin{align*}
{n \choose k-1}+{n \choose k}
=&\ \frac{n!}{(k-1)!(n+1-k)!}+\frac{n!}{k!(n-k)!}\\
=&\ \frac{n!}{(k-1)!(n-k)!}\left(\frac{1}{n+1-k}+\frac{1}{k}\right)\\
=&\ \frac{n!}{(k-1)!(n-k)!}\left(\frac{k}{k(n+1-k)}+\frac{n+1-k}{k(n+1-k)}\right)\\
=&\ \frac{n!}{(k-1)!(n-k)!}\cdot \frac{k+(n+1-k)}{k(n+1-k)}\\
=&\ \frac{n!}{(k-1)!(n-k)!}\cdot \frac{n+1}{k(n+1-k)}\\
=&\ \frac{n!(n+1)}{(k-1)!\cdot k\cdot (n-k)!\cdot (n+1-k)}\\
=&\ \frac{(n+1)!}{k!(n+1-k)!}={n+1 \choose k}.
\end{align*}

### Part c

Now we show binomial theorem by induction on $n$. We have showed the induction basis in Part a.

Suppose we have binomial theorem for $n$ and we would like to show it for $n+1$. We have
\begin{align}
&\ (a+b)^{n+1}=(a+b)(a+b)^n \nonumber \\
=&\ (a+b)\Big({n \choose 0}a^n+{n \choose 1} a^{n-1}b+\cdots +{n \choose n-1} ab^{n-1}+{n \choose n}b^n\Big).\label{eq:1-12-1}
\end{align} When we multiply it out, we only need to figure out what kind of terms will be there and what is the coefficients.

First, we must get terms like $a^{n+1-k}b^{k}$ for $k=0,1,2,\dots,n+1$.

Then we only need to compute the coefficient of $a^{n+1-k}b^{k}$ in \eqref{eq:1-12-1} for $k=1,\dots,n-1$. It can be obtained in two ways.

1. Multiply $a$ from $(a+b)$ and $a^{n-k}b^{k}$ from $(a+b)^n$. The coefficient for this case will be the coefficient of $a^{n-k}b^{k}$ in $(a+b)^n$, which is ${n \choose k}$.
2. Multiply $b$ from $(a+b)$ and $a^{n+1-k}b^{k-1}$ from $(a+b)^n$. The coefficient for this case will be the coefficient of $a^{n+1-k}b^{k-1}$ in $(a+b)^n$, which is ${n \choose k-1}$.

Hence the coefficient of $a^{n+1-k}b^{k}$ in $(a+b)^{n+1}$ is the sum of those two,
$${n \choose k}+{n \choose k-1}={n+1 \choose k}$$ by \eqref{eq:1-12-2} from Part b.

It is also clear that the coefficients of $a^{n+1-k}b^{k}$ in \eqref{eq:1-12-1} for $k=0,n$ are 1 which is also ${n+1 \choose 0}={n+1 \choose n+1}=1$. Therefore, we have showed that the coefficient of $a^{n+1-k}b^{k}$ in $(a+b)^{n+1}$ is given by ${n+1 \choose k}$. This completes the proof.

This part can be done easily if we know the $\sum$ notation.

We rewrite the proof using $\sum$ notation. We have
\begin{align*}
&\ (a+b)^{n+1}=(a+b)(a+b)^n= (a+b)\sum_{k=0}^n {n \choose k}a^{n-k}b^{k}\\
=&\ \sum_{k=0}^n {n \choose k}a^{n+1-k}b^{k}+\sum_{k=0}^n {n \choose k}a^{n-k}b^{k+1}\\
=&\ a^{n+1} +\sum_{k=1}^n {n \choose k}a^{n+1-k}b^{k}+\sum_{k=0}^{n-1} {n \choose k}a^{n-k}b^{k+1}+b^{n+1}\\
=&\ a^{n+1} +\sum_{k=1}^n {n \choose k}a^{n+1-k}b^{k}+\sum_{k=1}^{n} {n \choose k-1}a^{n+1-k}b^{k}+b^{n+1}\\
=&\ a^{n+1} +\sum_{k=1}^n \left({n \choose k}+{n \choose k-1}\right)a^{n+1-k}b^{k}+b^{n+1}\\
=&\ a^{n+1} +\sum_{k=1}^n {n+1 \choose k}a^{n+1-k}b^{k}+b^{n+1}=\sum_{k=0}^{n+1} {n+1 \choose k}a^{n+1-k}b^{k}.
\end{align*} Here we used \eqref{eq:1-12-2} from Part b and ${n+1 \choose 0}={n+1 \choose n+1}=1$.