# Math Help - Combinatorics Proof?

1. ## 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.

2. Hello Tulki
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 $\binom{n}{r}$ to denote ${^nC_r}$.

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

Proof of Lemma:

$\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)!}$

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

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

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

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

Then the Induction Hypothesis: Suppose $P(r)$ is the propositional function: For any $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:

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

$=\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 $P(r) \Rightarrow P(r+1)$.

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

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

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