Combinatorial proof

[Albi]

Guys, I'm trying to prove the hockey-stick identity using a combinatoric proof, here's what I tried:$$\sum ^{r}_{k=0}\binom{n+k}{k}= \binom{n+r+1}{r}$$first I turned the RHS into $\binom{n}{0}+ \binom{n+1}{1}+\binom{n+2}{2}+\cdots + \binom{n+r}{r}$ because I thought this might be easier to work with.

RHS: We have a group of n+r+1 and we want to choose r people to form a committee, this can be done in $\binom{n+r+1}{r}$ ways.
I'm stuck in the LHS, can someone please help?

If possible can someone give some general tips on how to approach these kinds of questions, for instance how to choose a counting problem that is related to a certain problem that I'm trying to solve.

 

[Steven G]

Why is it called the hockey-stick identity?
Recall that (n+1+r) C (r) = (n+1 + r) C (n+1)
Also recall that nCr = (n-1)C(r-1) + (n-1)Cr (either you do choose the 1st one OR you do not choose the 1st one)
See if any or both of these identities will help. Simplify the RHS by using the definition of combinations.

 

[Albi]

Why is it called the hockey-stick identity?
Recall that (n+1+r) C (r) = (n+1 + r) C (n+1)
Also recall that nCr = (n-1)C(r-1) + (n-1)Cr (either you do choose the 1st one OR you do not choose the 1st one)
See if any or both of these identities will help. Simplify the RHS by using the definition of combinations.

I've solved this using Paslac's triangle, but I can't solve it using a combinatorial argument.

 

[JeffM]

Did you try a double inductive proof?

$$n = 1 = r \implies \\ \sum_{k=0}^r \dbinom{n + k}{k} = \dbinom{1}{0} + \dbinom{2}{1} = 1 + 2 = 3 \text { and}\\ \dbinom{n + r + 1}{r} = \dfrac{3!}{1! * (3 - 1)!} = \dfrac{3!}{2!} = 3 \implies \\ \sum_{k=0}^r \dbinom{n + k}{k} =\dbinom{n + r + 1}{r}.$$
I got you started.

 

[Albi]

Did you try a double inductive proof?

$$n = 1 = r \implies \\ \sum_{k=0}^r \dbinom{n + k}{k} = \dbinom{1}{0} + \dbinom{2}{1} = 1 + 2 = 3 \text { and}\\ \dbinom{n + r + 1}{r} = \dfrac{3!}{1! * (3 - 1)!} = \dfrac{3!}{2!} = 3 \implies \\ \sum_{k=0}^r \dbinom{n + k}{k} =\dbinom{n + r + 1}{r}.$$
I got you started.

I did it by induction already, I guess you don' t get my question, I want to use the combinatorial approach, not algebra.

 

[JeffM]

I did it by induction already, I guess you don' t get my question, I want to use the combinatorial approach, not algebra.

You said you used Pascal's triangle, not induction. What do you even mean by a non-algebraic combinatorial approach?

 

[Albi]

You said you used Pascal's triangle, not induction. What do you even mean by a non-algebraic combinatorial approach?

In this type of approach we pose a counting problem, and then try to answer the problem in two different ways. One answer is the left side of the identity and the other answer is the right side. Since both answers solve the same counting problem then they must be equal.

 

[Dr.Peterson]

Guys, I'm trying to prove the hockey-stick identity using a combinatoric proof, here's what I tried:$$\sum ^{r}_{k=0}\binom{n+k}{k}= \binom{n+r+1}{r}$$first I turned the RHS into $\binom{n}{0}+ \binom{n+1}{1}+\binom{n+2}{2}+\cdots + \binom{n+r}{r}$ because I thought this might be easier to work with.

RHS: We have a group of n+r+1 and we want to choose r people to form a committee, this can be done in $\binom{n+r+1}{r}$ ways.
I'm stuck in the LHS, can someone please help?

If possible can someone give some general tips on how to approach these kinds of questions, for instance how to choose a counting problem that is related to a certain problem that I'm trying to solve.

This is among my favorite kinds of proof, but it can be quite hard to find a way to do it!

One hint is to try with specific small numbers first. For example, taking n=2 and r=3, $$\binom{n}{0}+ \binom{n+1}{1}+\binom{n+2}{2}+\cdots + \binom{n+r}{r} = \binom{n+r+1}{r}$$ becomes $$\binom{2}{0}+ \binom{2+1}{1}+\binom{2+2}{2}+\binom{2+3}{3} = \binom{2+3+1}{3}$$ that is, $$\binom{2}{0}+ \binom{3}{1}+\binom{4}{2}+\binom{5}{3} = \binom{6}{3}$$
So, we need to think of a way to select 3 from 6 balls by taking either none from 2, or one from 3, or two from 4, or 3 from 5. Commonly I find it helpful to imagine the balls coming in two different colors; maybe we have 3 red and the rest blue.

I haven't yet done this; I'm just suggesting a way to start. (But I think what I've said may come very close to a solution!)

Another thing that occurs to me in looking at the sum is that $$\sum ^{r}_{k=0}\binom{n+k}{k}= \binom{n+r+1}{r}$$ is equivalent to $$\sum ^{r}_{k=0}\binom{n+k}{n}= \binom{n+r+1}{n+1}$$ Do you see why? It is possible that this might be easier to work with.

I'll leave it there, and come back to the problem if I have time. I just wanted to offer an idea first!

 

[Steven G]

I've solved this using Paslac's triangle, but I can't solve it using a combinatorial argument.

What? Pascal's triangles is the identity that I stated.