Proof by Induction involving Binomial Coefficients

[Tollschnee]

Homework Statement

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)

Homework Equations

(x choose y) = (x!)/((x-y)!y!)

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.

 

[scurty]

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.

 

[Tollschnee]

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.

 

[Ray Vickson]

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.

You don't necessarily need to do induction on 'n'; you could, instead, do induction on 'a' or 'b' or 'a+b'.