- #1
Tollschnee
- 3
- 0
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.
Last edited: