# Combinatorics Proof?

• Sep 23rd 2009, 10:52 PM
Tulki
Combinatorics Proof?
For positive integers n, r show that:

C(n+r+1,r) = C(n+r,r) + C(n+r-1,r-1) + ... + C(n+2,2) + C(n+1,1) + C(n,0)

= C(n+r,n) + C(n+r-1,n) + ... + C(n+2,n) + C(n+1,n) + C(n,n)

Now, I've tried expanding the combinations, and I was able to get (n!) in the denominator of every term, though I'm not sure if that is even relevant to the proof. Not far, I know, but essentially, I'm stuck there and I don't know where to go.

Thanks in advance for any and all help.
• Sep 24th 2009, 01:30 AM
Hello Tulki
Quote:

Originally Posted by Tulki
For positive integers n, r show that:

C(n+r+1,r) = C(n+r,r) + C(n+r-1,r-1) + ... + C(n+2,2) + C(n+1,1) + C(n,0)

= C(n+r,n) + C(n+r-1,n) + ... + C(n+2,n) + C(n+1,n) + C(n,n)

Now, I've tried expanding the combinations, and I was able to get (n!) in the denominator of every term, though I'm not sure if that is even relevant to the proof. Not far, I know, but essentially, I'm stuck there and I don't know where to go.

Thanks in advance for any and all help.

We do the first part by Induction. The second is immediately obvious. I'm using the notation $\displaystyle \binom{n}{r}$ to denote $\displaystyle {^nC_r}$.

First we prove the Lemma: $\displaystyle \binom{n+r+1}{r+1}+\binom{n+r+1}{r}= \binom{n+r+2}{r+1}$

Proof of Lemma:

$\displaystyle \binom{n+r+1}{r+1}+\binom{n+r+1}{r}= \frac{(n+r+1)!}{(r+1)!n!}+ \frac{(n+r+1)!}{r!(n+1)!}$

$\displaystyle = \frac{(n+r+1)!(n+1)}{(r+1)!(n+1)!}+ \frac{(n+r+1)!(r+1)}{(r+1)!(n+1)!}$, using the fact that $\displaystyle (n+1)! = n!(n+1)$ and $\displaystyle (r+1)!=r!(r+1)$

$\displaystyle =\frac{(n+r+1)!([n+1]+[r+1])}{(r+1)!(n+1)!}$

$\displaystyle =\frac{(n+r+2)!}{(r+1)!(n+1)!}$

$\displaystyle = \binom{n+r+2}{r+1}$

Then the Induction Hypothesis: Suppose $\displaystyle P(r)$ is the propositional function: For any $\displaystyle n,\, \binom{n+r+1}{r}=\binom{n+r}{r}+\binom{n+r-1}{r-1}+...+\binom{n+2}{2}+\binom{n+1}{1}+\binom{n}{0}$

Then, using the above Lemma:

$\displaystyle P(r) \Rightarrow \binom{n+[r+1]+1}{r+1}=\binom{n+r+1}{r+1}+\binom{n+r+1}{r}$

$\displaystyle =\binom{n+r+1}{r+1}+\binom{n+r}{r}+\binom{n+r-1}{r-1}+...+\binom{n+2}{2}+\binom{n+1}{1}+\binom{n}{0}$

So $\displaystyle P(r) \Rightarrow P(r+1)$.

Now $\displaystyle P(0)$ is self-evident.

So the result is proved, by Induction, for all $\displaystyle r \ge 0$

For the second part, we note that for all $\displaystyle i,\, \binom{n+r-i}{r-i}=\binom{n+r-i}{n}$, and the result follows immediately.