Revisited: Binomial Theorem: An Inductive Proof

Question

I'm asked to use the fact that $\begin{pmatrix}n\\r\end{pmatrix}+\begin{pmatrix}n\\r-1\end{pmatrix}=\begin{pmatrix}n+1\\r\end{pmatrix}$ to show, by induction, that $$(a+b)^n=\begin{pmatrix}n\\0\end{pmatrix}a^n+\begin{pmatrix}n\\1\end{pmatrix}a^{n-1}b+\cdots+\begin{pmatrix}n\\r\end{pmatrix}a^{n-r}b^r+\begin{pmatrix}n\\n\end{pmatrix}b^n,$$ but I'm not sure where to start. I suspect that for the inductive step I multiply both sides by $(a+b)$, but from there I'm not sure where to go.

---

So this is what I've got so far doing it this way:

We are given that $$(a+b)^n=\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}a^{n-k}b^k$$ Let $n=1$. Clearly $$(a+b)^1=\begin{pmatrix}1\\0\end{pmatrix}a^1+\begin{pmatrix}1\\1\end{pmatrix}b^1=a+b.$$ Now let us assume that this equality holds for some arbitrary $n>1$, namely for the equality below: $$(a+b)^n=\sum_{k=0}^n\begin{pmatrix}n\\k\end{pmatrix}a^{n-k}b^k$$ We must now show that this holds for $n+1$. We do this by multiplying each side of the equality above by $(a+b)$: $$(a+b)(a+b)^n=\sum^{n}_{k=0}\begin{pmatrix}n\\k\end{pmatrix}a^{n-k+1}b^k+\sum^{n}_{k=0}\begin{pmatrix}n\\k\end{pmatrix}a^{n-k}b^{k+1}$$ Note that $$\sum^{n}_{k=0}\begin{pmatrix}n\\k\end{pmatrix}a^{n-k+1}b^k=\sum^{n+1}_{k=1}\begin{pmatrix}n\\k-1\end{pmatrix}a^{???}b^{???}$$

Answer 1

One can work with $(1+x)^n$ for simplicity, then plug $x=ab^{-1}$; but since you're not doing that, I'll keep $a$ and $b$. Note that if we write $$(a+b)^n=\sum_{k=0}^n \binom nk a^kb^{n-k}$$ using our inductive hypothesis then $$(a+b)^{n+1}=(a+b)(a+b)^n=\sum_{k=0}^n \binom nk a^{k+1}b^{n-k}+\sum_{k=0}^n \binom nk a^{k}b^{n-k+1}$$

Modify the indices so that $\displaystyle \binom nk+\binom{n}{k-1}$ appears. Don't forget to use that $\displaystyle \binom nk=0$ if $k<0$ or $k>n$ to keep $k=0$ and obtain $k=n+1$ "for free". In particular, you can simply change the upper limits of the last term to $n+1$, and take $k\to k-1$ on the first sum, then keep $k=0$ since $\displaystyle \binom n{-1}=0$.

SPOILER We have that

$$\sum_{k=0}^n \binom nk a^{k+1}b^{n-k}=\sum_{k=1}^{n+1}\binom{n}{k-1}a^kb^{n-k+1}=\sum_{k=0}^{n+1}\binom{n}{k-1}a^kb^{n-k+1}$$

and that

$$\sum_{k=0}^n \binom nk a^{k}b^{n-k+1}=\sum_{k=0}^{n+1} \binom nk a^{k}b^{n-k+1}$$

Answer 2

First proof that $\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$

Proof:

$\binom{n}{k} + \binom{n}{k-1} = \frac{n!}{k!(n-k)!} + \frac{n!}{(k-1)!(n-k+1)!} = \frac{n!}{k!(n-k)!} + \frac{n!}{k!(n-k)!}\frac{k}{n-k+1} = \frac{n!}{k!(n-k)!}(1+\frac{k}{n-k+1}) = \frac{n!}{k!(n-k)!}\frac{n+1}{n-k+1} = \frac{(n+1)!}{k!(n+1-k)!}=\binom{n+1}{k}$

Then main thing proof:

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

Note:

$n!(n+1) = (n+1)!$ or $(n-1)!=\frac{n!}{n}$

Answer 3

The inductive proof of the binomial theorem is really lovely and good looking. The goal here is to prove, $\forall n,k\in\mathbb{N}$ such that $n\geq k$, and for any reals $a,b$, that: $$(a+b)^n=\sum_{k=0}^n {{n}\choose{k}}a^{n-k}b^k $$

BASIS

Let verify that the equality holds at rank $n=0$. Indeed: \begin{align*} (a+b)^0&=1\text{ by convention}\\ {{0}\choose{0}}a^0b^0&=1 \end{align*} Hence, the equality holds at initial rank.

INDUCTIVE STEP

We assume that, for $r\in\mathbb{N}$, the equality: $$(a+b)^r=\sum_{k=0}^r {{r}\choose{k}}a^{r-k}b^k $$ holds for any reals $a$ and $b$.

At rank $(r+1)$: \begin{align*} (a+b)^{n+1}&=(a+b)\sum_{k=0}^{r}{{n}\choose{k}}a^{r-k}b^k\\ &=a\sum_{k=0}^{r}{{r}\choose{k}}a^{r-k}b^k+b\sum_{k=0}^{r}{{r}\choose{k}}a^{r-k}b^k\\ &=\sum_{k=0}^{r}{{r}\choose{k}}a^{r+1-k}b^k+\sum_{k=0}^{r}{{r}\choose{k}}a^{r-k}b^{k+1}\\ &=\sum_{k=0}^{r}{{r}\choose{k}}a^{r+1-k}b^k+\sum_{k=1}^{r+1}{{r}\choose{k-1}}a^{r+1-k}b^{k}\\ &={{r}\choose{0}}a^{r+1}+\sum_{k=1}^{r}{{r}\choose{k}}a^{r+1-k}b^k+\sum_{k=1}^{r}{{r}\choose{k-1}}a^{r+1-k}b^{k}+{{r}\choose{r}}b^{r+1}\\ &={{r+1}\choose{0}}a^{r+1}+\sum_{k=1}^{r}\left[{{r}\choose{k}}+{{r}\choose{k-1}}\right]a^{r+1-k}b^k+{{r+1}\choose{r+1}}b^{r+1}\\ &={{r+1}\choose{0}}a^{r+1}+\sum_{k=1}^{r}{{r+1}\choose{k}}a^{r+1-k}b^k+{{r+1}\choose{r+1}}b^{r+1}\text{ with the Pascal equality}\\ &=\sum_{k=0}^{r+1}{{r+1}\choose{k}}a^{r+1-k}b^k \end{align*} The equality holds at rank $(r+1)$.

CONCLUSION

Therefore, by induction on $r$, the equality: $$(a+b)^n=\sum_{k=0}^n {{n}\choose{k}}a^{n-k}b^k $$ is true $\forall n,k\in\mathbb{N}$ such that $n\geq k$ for any $a$ and $b$ reals.