Combinatorial proof

A

Albi

Junior Member
Joined
May 9, 2020
Messages
145
Guys, I'm trying to prove the hockey-stick identity using a combinatoric proof, here's what I tried:[math]\sum ^{r}_{k=0}\binom{n+k}{k}= \binom{n+r+1}{r}[/math]first I turned the RHS into [imath]\binom{n}{0}+ \binom{n+1}{1}+\binom{n+2}{2}+\cdots + \binom{n+r}{r}[/imath] 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 [imath]\binom{n+r+1}{r}[/imath] 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.
 
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.
 
Jomo said:
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.
Click to expand...
I've solved this using Paslac's triangle, but I can't solve it using a combinatorial argument.
 
Did you try a double inductive proof?

[math]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}.[/math]
I got you started.
 
JeffM said:
Did you try a double inductive proof?

[math]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}.[/math]
I got you started.
Click to expand...
I did it by induction already, I guess you don' t get my question, I want to use the combinatorial approach, not algebra.
 
Albi said:
I did it by induction already, I guess you don' t get my question, I want to use the combinatorial approach, not algebra.
Click to expand...
You said you used Pascal's triangle, not induction. What do you even mean by a non-algebraic combinatorial approach?
 
JeffM said:
You said you used Pascal's triangle, not induction. What do you even mean by a non-algebraic combinatorial approach?
Click to expand...
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.
 
Albi said:
Guys, I'm trying to prove the hockey-stick identity using a combinatoric proof, here's what I tried:[math]\sum ^{r}_{k=0}\binom{n+k}{k}= \binom{n+r+1}{r}[/math]first I turned the RHS into [imath]\binom{n}{0}+ \binom{n+1}{1}+\binom{n+2}{2}+\cdots + \binom{n+r}{r}[/imath] 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 [imath]\binom{n+r+1}{r}[/imath] 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.
Click to expand...
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, [math]\binom{n}{0}+ \binom{n+1}{1}+\binom{n+2}{2}+\cdots + \binom{n+r}{r} = \binom{n+r+1}{r}[/math] becomes [math]\binom{2}{0}+ \binom{2+1}{1}+\binom{2+2}{2}+\binom{2+3}{3} = \binom{2+3+1}{3}[/math] that is, [math]\binom{2}{0}+ \binom{3}{1}+\binom{4}{2}+\binom{5}{3} = \binom{6}{3}[/math]
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 [math]\sum ^{r}_{k=0}\binom{n+k}{k}= \binom{n+r+1}{r}[/math] is equivalent to [math]\sum ^{r}_{k=0}\binom{n+k}{n}= \binom{n+r+1}{n+1}[/math] 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!
 
You must log in or register to reply here.
Top