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.