Binomial theorem proof by induction

[phospho]

On my problem sheet I got asked to prove:

$(1+x)^n = \displaystyle\sum _{k=0} ^n \binom{n}{k} x^k$

here is my attempt by induction...

n = 0
LHS$(1+x)^0 = 1$
RHS:$\displaystyle \sum_{k=0} ^0 \binom{0}{k} x^k = \binom{0}{0}x^0 = 1\times 1 = 1$


LHS = RHS hence true for n = 0

assume true for n = r i.e.:

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

n = r+1:

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

consider $\displaystyle \sum_{k=0}^r \binom{r}{k} x^{k+1}$

let k = s-1 then:

$\displaystyle \sum_{k=0}^r \binom{r}{k} x^{k+1} = \displaystyle \sum_{s=1}^{r+1} \binom{r}{s-1}x^s = \displaystyle \sum_{k=1}^{r+1} \binom{r}{k-1}x^k$

hence we get:

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

$= \displaystyle \sum_{k=1}^r \binom{r}{k}x^k + \displaystyle \sum_{k=1}^r \binom{r}{k-1}x^k + \binom{0}{0}x^0 + \binom{r+1}{r}x^{r+1}$

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

hence shown to be true for n = r + 1

is this proof OK or have I made a mistake somewhere?

 

[phospho]

bump, anyone?

 

[vanhees71]

As far as I can see, it looks good. Perhaps you have to prove the "Pascal triangle identity" for the binomial coefficients,
\binom{r}{k} + \binom{r}{k-1}=\binom{r+1}{k},
which is just an easy to prove identity using the definition of the binomial coeficients
\binom{r}{k}=\frac{r!}{k!(r-k)!}.

 

[phospho]

As far as I can see, it looks good. Perhaps you have to prove the "Pascal triangle identity" for the binomial coefficients,
\binom{r}{k} + \binom{r}{k-1}=\binom{r+1}{k},
which is just an easy to prove identity using the definition of the binomial coeficients
\binom{r}{k}=\frac{r!}{k!(r-k)!}.

I've proved that previously

I just noticed a mistake in my proof

instead of $\binom{r+1}{r} x^{r+1}$ I should have $\binom{r}{r} x^{r+1}$ right?

 

[vanhees71]

Argh, that I've overlooked. Sorrry. Of course
\binom{r}{r}=\binom{r+1}{r+1}=1.
So it's been just a type :-).

 

[FeDeX_LaTeX]

If you're interested, you could also do a proof using Fubini's theorem on the sum, if you can spot a small trick.