# Vandermonde's Identity

1. Apr 16, 2007

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

2. Apr 16, 2007

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

Last edited: Apr 16, 2007
3. Apr 16, 2007

### SeReNiTy

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

4. Apr 18, 2007

### 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 alot of different equivalent forms of the convolution!

Last edited: Apr 18, 2007