Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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 :)


The answer

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!!! $$

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
LOL - It takes 3 lines using your method. Thanks! My method was "not very close" as mentioned by Jonas. Why didn't I think of that equation before? Sometimes my brain just seems to get stuck..... O_O – Johann Mar 16 '12 at 6:44
@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
@Jonas Thanks a lot! I am sure I will to need to be able to understand and do combinatorial proofs somewhere in the course so your combinatorial approach is most appreciated...Cheers – Johann Mar 16 '12 at 7:28

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.