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!

Proof by Induction involving Binomial Coefficients

  1. Feb 16, 2014 #1
    1. The problem statement, all variables and given/known data
    Prove by induction that for any positive integers a, b, and n,
    (a choose 0)(b choose n) + (a choose 1)(b choose n-1) + ... + (a choose n)(b choose 0) = (a+b choose n)


    2. Relevant equations
    (x choose y) = (x!)/((x-y)!y!)


    3. The attempt at a solution
    I am able to do the first step of induction, the basis. That is quite simple because all I had to do was set n equal to 1 and solve both sides. I ended up with a+b=a+b. My problem is with proving the inductive step (assuming that n works and using that to prove that n+1 works). I understand the equation conceptually and how it works, however the problem requires I do a proof by induction and I cannot figure out how to prove the inductive step.
     
    Last edited: Feb 16, 2014
  2. jcsd
  3. Feb 16, 2014 #2
    The usual approach is to start with your left side of the equation (for k+1), use the assumption (assume it works for k...) to reduce the math, and finally conclude after some simplification/rearranging the right hand side (for k+1).

    You can of course work from the right side to conclude the left, but in inductive proofs it is generally easier to work with the more "complicated" side in order to conclude the "easier" side.
     
  4. Feb 16, 2014 #3
    So I have reduced the right side (a+b choose n+1) to (a+b choose n)*(a+b-n)/(n+1)
    I obtained this from applying the formula I was given and applying it to both (a+b choose n) and (a+b choose n+1) and simplifying the latter to contain the former along with whatever else... in this case: (a+b-n)/(n+1)

    I guess the real trouble I am having at this point is dealing with the series on the left side of the equation and simplifying it out to match the right side. I've been trying to find some way to make the n+1 series match the n series along with some multiplier, but I can't find the trick.
     
    Last edited: Feb 16, 2014
  5. Feb 17, 2014 #4

    Ray Vickson

    User Avatar
    Science Advisor
    Homework Helper

    You don't necessarily need to do induction on 'n'; you could, instead, do induction on 'a' or 'b' or 'a+b'.
     
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: Proof by Induction involving Binomial Coefficients
Loading...