Combinatorics Proof?

**Tulki** · September 23rd 2009, 10:52 PM

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.

**Grandad** · September 24th 2009, 01:30 AM

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.

Grandad

**Tulki** · September 24th 2009, 10:10 AM

Wow. Ha, we haven't even started with Induction yet, but in any case, thank you very much.

I'll study your response until I totally understand it!

Thread: Combinatorics Proof?

LinkBack

Thread Tools

Display

Combinatorics Proof?

Similar Math Help Forum Discussions

Combinatorics proof help

Combinatorics & Partitions proof

Combinatorics

Perfect Square combinatorics proof

Combinatorics Proof

Search Tags