0
$\begingroup$

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^{???}$$

$\endgroup$
5
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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&=0\text{ by convention}\\ {{0}\choose{0}}a^0b^0&=3 \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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.