Solving Combinatorial Identity: Exploring a Curious Equation

[icystrike]

Homework Statement

Hello PF! This is not a homework problem but I am curious to know if the following combinatorial identity exist:

$$\sum^{r-1}_{k=0} (^{n-1}_{r-(k+1)}) \times (^{r}_{k}) = (^{n+r-1}_{r-1})$$


Much thanks :)

 

[CompuChip]

Yes, it is called http://en.wikipedia.org/wiki/Vandermonde's_identity]Vandermonde's[/PLAIN] identity.

If you plug in m = r in the first formula given in that link, and shift k ==> k - 1, you get exactly what you wrote.

 

[icystrike]

Yes, it is called http://en.wikipedia.org/wiki/Vandermonde's_identity]Vandermonde's[/PLAIN] identity.

If you plug in m = r in the first formula given in that link, and shift k ==> k - 1, you get exactly what you wrote.

Thank you! It is indeed Vandermonde's identity with n, m and r substituted with n-1, r, and r-1 respectively.

I wrote this above identity as inspired by finding the number of distinct nonnegative integer-valued vectors $(x_{1},x_{2},...,x_{r})$ satisfying:

$x_{1}+x_{2}+...x_{r}=n$​