Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Vandermonde's Identity

  1. Apr 16, 2007 #1
    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. jcsd
  3. Apr 16, 2007 #2


    User Avatar
    Gold Member

    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.
    didnt know it has a name. (-:
    Last edited: Apr 16, 2007
  4. Apr 16, 2007 #3
    I want to do it without using binomial theorem. So by induction, but my combinatorics is weak...
  5. Apr 18, 2007 #4
    So does anyone know of a proof using induction?

    The identity is also known as vandermonde's convolution

    [tex] \sum_{k=0}^{n}{a\choose k}{b \choose n-k}={a+b\choose n} [/tex]

    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:

    [tex] {a\choose 0} = 1 [/tex]

    [tex] {a\choose n} = \frac{1}{n!} \prod_{i=1}^{n}{a-i+1} [/tex]

    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:

    [tex] \sum_{k=0}^{n+1}{a\choose k}{b \choose n+1-k}={a+b\choose n+1} [/tex]

    Starting with RHS:

    [tex] {a+b\choose n+1} = \frac{1}{(n+1)!} \prod_{i=1}^{n+1}{a+b-i+1} [/tex]

    [tex] = \frac{a+b-n}{n+1} {a+b\choose n} [/tex]

    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
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Similar Discussions: Vandermonde's Identity
  1. Integral Identity (Replies: 5)

  2. The identity function (Replies: 2)

  3. Complex identity (Replies: 9)

  4. Exponential Identities (Replies: 2)

  5. Trigonoemtric Identity (Replies: 5)