- #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: