# Algebraic Proof that $\sum\limits_{k=0}^m \binom{r}{k} \binom{m+n-r}{m-k} = \binom{m+n}{m}$

How do I prove that:

$$\sum\limits_{k=0}^m \binom{r}{k} \binom{m+n-r}{m-k} = \binom{m+n}{m} ~~~~~~~~~ (r <= m + n)$$

by using an algebraic identity?

My Attempt:

I know of the generating functions: $$(1 + x)^n = \sum\limits_{k=0}^n \binom{r}{k} x^k ~~~~~ and ~~~~~~ \frac {1}{(1 + x)^{n + 1}} = \sum\limits_{k=0}^{\infty} \binom{n + k}{k} x^k$$

and after a bit of trial and error I came up with the algebraic identity:

$$(1 - x)^r \frac {1}{(1 - x)^{n + r + 1}} = \frac {1}{(1 - x)^{n + 1}} ~~~~~~~~~~~~~~~~~ (a)$$

The right hand side of (a) clearly matches the 2nd generating function. So:

$$\frac {1}{(1 + x)^{n + 1}} = \sum\limits_{m=0}^{\infty} \binom{n + m}{m} x^m$$

The left hand side of (a) can be expressed as product of summations:

\begin{align*} \displaystyle{ (1 - x)^r \frac {1}{(1 - x)^{n + r + 1}} } &=\displaystyle{ \sum\limits_{m=0}^{\infty} \binom{r}{m} (-x)^m \sum\limits_{k=0}^{\infty} \binom{n + r + k}{k} x^k } \\ &=\displaystyle{ \sum\limits_{m=0}^{\infty} \sum\limits_{k=0}^{m} \binom{r}{k} (-x)^k \binom{n + r + m - k}{m - k} x^{m-k} } \\ &=\displaystyle{ \sum\limits_{m=0}^{\infty} \sum\limits_{k=0}^{m} \binom{r}{k} \binom{n + r + m - k}{m - k} (-1)^k x^m } \end{align*}

But now I am stuck since I don't know how to make:

$$\binom{n + r + m - k}{m - k} (-1)^k ~~~~ equal ~~~~ \binom{m+n-r}{m-k} ~~~~~ ?????$$

to complete the proof.

Will my method work or should I be using another algebraic identity? I am quite new to combinatorics so please keep concepts understandable by a beginner. Thanks :)

EDIT

It turns out that my equation wasn't taking me anywhere close to the answer - LOL! Here is the answer with the new algebraic identity:

\begin{align*} (1 + x)^r (1 + x)^{m+n-r} &= (1 + x)^{m + n} \\ \sum\limits_{m=0}^r \binom{r}{m} x^m \sum\limits_{k=0}^{m + n-r} \binom{n+m-r}{k} x^k &= \sum\limits_{m=0}^{n + m} \binom{n+m}{m} x^m \\ \sum\limits_{m=0}^{r + (m+n-r)} \sum\limits_{k=0}^m \binom{r}{m} \binom{n+m-r}{m-k} x^m &= \sum\limits_{m=0}^{n + m} \binom{n+m}{m} x^m \\ \sum\limits_{m=0}^{m+n} \sum\limits_{k=0}^m \binom{r}{m} \binom{n+m-r}{m-k} x^m &= \sum\limits_{m=0}^{n + m} \binom{n+m}{m} x^m \\ \end{align*}

Equating coefficients gives:

$$\sum\limits_{k=0}^m \binom{r}{m} \binom{n+m-r}{m-k} = \binom{n+m}{m} ~~~~~~~~~~~~~~~~ QED!!!$$

-
Your work looks good, and you do get a nice identity for binomial coefficients that way. Unfortunately, it's not the one you want to prove, and I don't think it's very close to the one you want to prove. If you follow Broskiana's suggestion, you'll see that the problem is a bit simpler than what you were attempting. (One other comment-- when you list the two generating functions you know, the second one should be $\frac{1}{(1-x)^{n+1}}$, not $\frac{1}{(1+x)^{n+1}}$. Obviously, you realize this, since all your work is correct!) – Jonas Kibelbek Mar 16 '12 at 6:22
@jonas-kibelbek Thanks for reviewing though my work even though it was way off. I am new to combinatorics so it is good to know my manipulations are ok :) – Johann Mar 16 '12 at 6:48

Since you know binomial series i think you can compare the coefficient of $x^m$ in $(1+x)^r(1+x)^{m+n-r}$ and $(1+x)^{n+m}$. It should be very straight forward from here.
@Johann: By the way, the combinatorial proof and algebraic proof are related. The combinatorial proof is this: We want to count the ways to choose $m$ marbles from a set of $m+n$ marbles (which is $\binom{m+n}{m}$). Suppose $r$ of the marbles are red-- then when we choose $m$ marbles, we will get $k$ red ones, where $k$ could be any number from 0 to $r$, and $m-k$ ordinary marbles (that is, $\sum_{k=0}^r \binom{r}{k} \binom{m+n-r}{m-k}$). In the algebraic proof, pulling out the factor $(1+x)^r$ is kind of like painting those $r$ copies of $x$ red. – Jonas Kibelbek Mar 16 '12 at 7:00