Binomial Proof

1. Jul 17, 2008

Gammage

1. The problem statement, all variables and given/known data
Let l, m, and n be positive integers with l $$\leq$$ m and l $$\leq$$ n. Prove the identity.
($$\stackrel{m + n}{l}$$) = ($$\stackrel{m}{0}$$)($$\stackrel{n}{l}$$) + ($$\stackrel{m}{1}$$)($$\stackrel{n}{l-1}$$)+...+($$\stackrel{m}{l}$$)($$\stackrel{n}{0}$$)

2. The attempt at a solution
I have no clue, I see proof and my brain goes dead. I thought I could just start writing the definition of the parts out on both sides and maybe something would make sense but it got messy quick and I didn't see any light at the end of that tunnel.

2. Jul 18, 2008

dynamicsolo

How about a proof by induction? The integers l, m, and n have to be positive, so we'd start from l = 1:

$$(\stackrel{m+n}{1}) = (\stackrel{m}{0})(\stackrel{n}{1}) + (\stackrel{m}{1})(\stackrel{n}{0}) = m + n$$

which plainly works. (It doesn't work for l = 0, but it doesn't have to, under the specified conditions.)

Now assume the proposition

($$\stackrel{m + n}{l}$$) = ($$\stackrel{m}{0}$$)($$\stackrel{n}{l}$$) + ($$\stackrel{m}{1}$$)($$\stackrel{n}{l-1}$$)+...+($$\stackrel{m}{l}$$)($$\stackrel{n}{0}$$) .

What happens when we advance to the case for ($$\stackrel{m + n}{l+1}$$) ?

Last edited: Jul 18, 2008