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,
[tex]\binom{r}{k} + \binom{r}{k-1}=\binom{r+1}{k},[/tex]
which is just an easy to prove identity using the definition of the binomial coeficients
[tex]\binom{r}{k}=\frac{r!}{k!(r-k)!}.[/tex]

 

[phospho]

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

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
[tex]\binom{r}{r}=\binom{r+1}{r+1}=1.[/tex]
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.