Blog

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
\begin{equation}\label{eq:1-12-2}
{n \choose k-1}+{n \choose k}={n+1 \choose k}
\end{equation} 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.

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$.