1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Binomial theorem proof by induction

  1. Oct 20, 2013 #1
    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?
     
  2. jcsd
  3. Oct 21, 2013 #2
    bump, anyone?
     
  4. Oct 21, 2013 #3

    vanhees71

    User Avatar
    Science Advisor
    2016 Award

    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]
     
  5. Oct 21, 2013 #4
    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?
     
  6. Oct 22, 2013 #5

    vanhees71

    User Avatar
    Science Advisor
    2016 Award

    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 :-).
     
  7. Oct 22, 2013 #6

    FeDeX_LaTeX

    User Avatar
    Gold Member

    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: Oct 22, 2013
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Binomial theorem proof by induction
Loading...