# Combinatorial proof of a binomial identity

• Nov 11th 2008, 10:57 PM
gusztav
Combinatorial proof of a binomial identity
Hi, I'm trying to combinatorially prove the following identity:

$\displaystyle \sum_{i=0}^{r} \binom{n+i}{n}=\binom{n+1+r}{n+1}$

On the right side, $\displaystyle \binom{n+1+r}{n+1}$ is the number of ways we can choose a $\displaystyle (n+1)$-element subset from a $\displaystyle (n+1+r)$-element set, while on the left side there is the sum of ways we can select an $\displaystyle n$-element subset from a $\displaystyle n$-element, $\displaystyle (n+1)$-element,...,$\displaystyle (n+r)$-element set...

How can we prove that the numbers on both sides of the equation are actually identical?

I'd be really grateful for any help.

Thanks!
• Nov 12th 2008, 04:42 AM
PaulRS
See here
• Nov 12th 2008, 02:42 PM
Tony
You could try using proof by induction:
You need this formula,$\displaystyle \binom{n}{j}=\frac{n!}{j!\left(n-j\right)!}$

1: let r=1 and show that the two sides are equal.

2: Assume that it's true for r = k.

This tells us, $\displaystyle \sum_{i=0}^{k}\binom{n+i}{n}=\binom{n+k+1}{n+1}$

3: Now prove that it's true for r = k+1
$\displaystyle \sum_{i=0}^{k+1}\binom{n+i}{n}=\sum_{i=0}^{k}\bino m{n+i}{n}+\binom{n+k+1}{n}$

This is equal to, $\displaystyle \binom{n+k+1}{n+1}+\binom{n+k+1}{n}=\binom{n+k+2}{ n+1}$

Now making use of the formula from the start

$\displaystyle \frac{\left(n+k+1\right)!}{\left(n+1\right)!\left( k\right)!} +\frac{\left(n+k+1\right)!}{n!\left(k+1\right)!} = \frac{\left(n+k+2\right)!}{\left(n+1\right)!\left( k+1\right)!}$

simplify the LHS

$\displaystyle \frac{\left(n+k+1\right)!n!\left(k+1\right)! +\left(n+k+1\right)!\left(n+1\right)!k!}{\left(n+1 \right)!\left(k!\right)\left(n\right)!\left(k+1\ri ght)!}= \frac{\left(n+k+2\right)!}{\left(n+1\right)!\left( k+1\right)!}$

using $\displaystyle n! = n\left(n-1\right)!$ and simplifying further

$\displaystyle \frac{\left(n+k+1\right)!n!\left(k+1\right)\left(k \right)! +\left(n+k+1\right)!\left(n+1\right)\left(n\right) !k!}{\left(n+1\right)!\left(k!\right)\left(n\right )!\left(k+1\right)!}= \frac{\left(n+k+2\right)\left(n+k+1\right)!}{\left (n+1\right)!\left(k+1\right)!}$

You can show the two sides are equal for k+1 so equal for all k ( or r)