• Support PF! Buy your school textbooks, materials and every day products Here!

Binomial theorem proof by induction

  • Thread starter phospho
  • Start date
  • #1
251
0
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?
 

Answers and Replies

  • #2
251
0
bump, anyone?
 
  • #3
vanhees71
Science Advisor
Insights Author
Gold Member
2019 Award
14,803
6,299
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]
 
  • #4
251
0
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?
 
  • #5
vanhees71
Science Advisor
Insights Author
Gold Member
2019 Award
14,803
6,299
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 :-).
 
  • Like
Likes 1 person
  • #6
FeDeX_LaTeX
Gold Member
437
13
If you're interested, you could also do a proof using Fubini's theorem on the sum, if you can spot a small trick.
 
Last edited:

Related Threads on Binomial theorem proof by induction

Replies
5
Views
3K
  • Last Post
Replies
1
Views
962
  • Last Post
Replies
6
Views
1K
Replies
3
Views
977
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
833
  • Last Post
Replies
11
Views
5K
  • Last Post
Replies
6
Views
3K
  • Last Post
Replies
0
Views
1K
Top