Proof of Vandermonde's Identity by Induction

[SeReNiTy]

Can someone point me in the right direction with vandermonde's identity, I'm seeking a algebraic proof.

essentially it its the sum of (a ,k)(b ,n-k) = (a+b ,n) when summed over k = 0 to n.

Could someone right this out in latex since it is probably incomprehensible. I used (a ,k) to denote the binomial co-efficients and a,b are real numbers.

 

[MathematicalPhysicist]

bassically you sum up the coefficients of (1+x)^a*(1+x)^b=(1+x)^(a+b).
where (a+b,n) is the coeffeicnt of x^n.
it also works for a,b which are not positive integers.
p.s
didnt know it has a name. (-:

 

[SeReNiTy]

I want to do it without using binomial theorem. So by induction, but my combinatorics is weak...

 

[SeReNiTy]

So does anyone know of a proof using induction?

The identity is also known as vandermonde's convolution

$$\sum_{k=0}^{n}{a\choose k}{b \choose n-k}={a+b\choose n}$$

Where a,b are real numbers. I already know of the proof using binomial theorem and the combinatorics counting argument, now I'm looking for a way to do it by induction, anyone got any hints/tips?

First off a few definitions for those that don't know, the binomial co-efficient can be defined for non intergers as follows:

$${a\choose 0} = 1$$

$${a\choose n} = \frac{1}{n!} \prod_{i=1}^{n}{a-i+1}$$

So far I got the following, the base case n=0 is trivial, now the inductive hypothesis is the above identity and I attempt to show the following is true assuming the inductive hypothesis:

$$\sum_{k=0}^{n+1}{a\choose k}{b \choose n+1-k}={a+b\choose n+1}$$

Starting with RHS:

$${a+b\choose n+1} = \frac{1}{(n+1)!} \prod_{i=1}^{n+1}{a+b-i+1}$$

$$= \frac{a+b-n}{n+1} {a+b\choose n}$$

Now you can apply the inductive hypothesis, but after that I'm lost. Tried many, many different algebraic tricks and ended up with nothing useful, just a lot of different equivalent forms of the convolution!