5
$\begingroup$

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

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

  • 1
    @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 :)2012-03-16

1 Answers 1

2

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.

  • 1
    @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...Cheers2012-03-16