MHB Is This Binomial Coefficient Identity True?

AI Thread Summary
The discussion revolves around the identity involving binomial coefficients: $$\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\binom{n-1}{k-1}$$ for natural numbers n and k where n > k. Vincent expresses difficulty in proving this identity and attempts various methods, including expansion and induction, without success. Sudharaka provides a solution using combinatorial reasoning and identities, specifically leveraging Pascal's rule and Vandermonde's identity to demonstrate the validity of the equation. The conversation concludes with Vincent expressing gratitude for the clarification provided.
VincentP
Messages
7
Reaction score
0
I'm having trouble proving the following identity (I don't even know if it's true):
$$\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\binom{n-1}{k-1}$$ $$\forall n,k \in \mathbb{N} : n>k$$
Thank you in advance for any help!
Vincent
 
Physics news on Phys.org
VincentP said:
I'm having trouble proving the following identity (I don't even know if it's true):
$$\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\binom{n-1}{k-1}$$ $$\forall n,k \in \mathbb{N} : n>k$$
Thank you in advance for any help!
Vincent

Maybe expanding the binomial coefficients would help. Recall that $ \displaystyle {n\choose{m}} = \frac{n!}{m!(n-m)!} $
 
Prove It said:
Maybe expanding the binomial coefficients would help. Recall that $ \displaystyle {n\choose{m}} = \frac{n!}{m!(n-m)!} $

Well I have tried that of course:
$$ \sum_{r=1}^k \frac{k!}{r!(k-r)!} \frac{(n-k-1)!}{(r-1)!(n-k-r)!} \stackrel{?}{=} \frac{(n-1)!}{(k-1)!(n-k)!} $$
But I don't know where to go from here since I still can't sum the left hand side. I also tried to prove it by induction but I failed to prove the induction step.
 
VincentP said:
I'm having trouble proving the following identity (I don't even know if it's true):
$$\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\binom{n-1}{k-1}$$ $$\forall n,k \in \mathbb{N} : n>k$$
Thank you in advance for any help!
Vincent

Hi Vincent, :)

Thank you for submitting this problem, I enjoyed solving it. :)

Since, \(\binom{k}{r}=\binom{k}{k-r}\) we have,

\[\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\sum_{r=1}^{k}\binom{k}{k-r} \binom{n-k-1}{r-1}\]

Using the Pascal's rule we get,

\begin{eqnarray}

\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}&=&\sum_{r=1}^{k}\left[{k+1 \choose k-r+1}-{k \choose k-r+1}\right]\binom{n-k-1}{r-1}\\

&=&\sum_{r=1}^{k}{k+1 \choose k-r+1}\binom{n-k-1}{r-1}-\sum_{r=1}^{k}{k \choose k-r+1}\binom{n-k-1}{r-1}\\

\end{eqnarray}

Now use the Vandermonde's identity to get,

\[\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}={n \choose k}-\binom{n-1}{k}\]

Using the Pascal's rule again we get,

\[\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}={n-1 \choose k-1}\]

Kind Regards,
Sudharaka.
 
For a completely different, combinatorial, way to look at this problem, suppose that you have $n-1$ objects, and you want to select $k-1$ of them. There are $n-1\choose k-1$ ways of making the selection.

Now suppose that $k$ of the objects are white, and the remaining $(n-1)-k$ are black. Then another way to select $k-1$ objects is as follows. First, choose a number $r$ between 1 and $k$ (inclusive). Then select $r-1$ black balls and $(k-1)-(r-1) = k-r$ white balls. The number of ways to do that is ${k\choose k-r}{(n-1)-k\choose r-1} = {k\choose r}{n-k-1\choose r-1}.$ Sum that from $r=1$ to $k$ to get the total number of ways to select $k-1$ objects.
 
@ Sudharaka
Thank you very much for your explanation!
I have one question though: Doesn't Vandermonde's identity require the sum to start at r=0?

@Opalg
Thank you for your reply, that's a very interesting approach to the problem!
 
VincentP said:
@ Sudharaka
Thank you very much for your explanation!
I have one question though: Doesn't Vandermonde's identity require the sum to start at r=0?

@Opalg
Thank you for your reply, that's a very interesting approach to the problem!

You are welcome. :) I have neglected an in between step that may have aroused the confusion.

\[\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\sum_{r=1}^{k}{k+1 \choose k-r+1}\binom{n-k-1}{r-1}-\sum_{r=1}^{k}{k \choose k-r+1}\binom{n-k-1}{r-1}\]

Substitute \(u=r-1\). Then the right hand side becomes,

\[\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\sum_{u=0}^{k}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k}{k \choose k-u}\binom{n-k-1}{u}\]

I hope this clarifies your doubts. :)

Kind Regards,
Sudharaka.
 
Sudharaka said:
You are welcome. :) I have neglected an in between step that may have aroused the confusion.

\[\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\sum_{r=1}^{k}{k+1 \choose k-r+1}\binom{n-k-1}{r-1}-\sum_{r=1}^{k}{k \choose k-r+1}\binom{n-k-1}{r-1}\]

Substitute \(u=r-1\). Then the right hand side becomes,

\[\sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\sum_{u=0}^{k}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k}{k \choose k-u}\binom{n-k-1}{u}\]

I hope this clarifies your doubts. :)

Kind Regards,
Sudharaka.

Well not quite.
If you substitute the index of summation $ u=r-1 $ you have to change the lower as well as the upper bound of summation, because otherwise you change the number of summands. Therefore if you substitute $ u=r-1 $ we get:
$$ \sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\sum_{u=0}^{k-1}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k-1}{k \choose k-u}\binom{n-k-1}{u} $$ Which doesn't match Vandermonde's Identity anymore, because the upper bound of summation doesn't appear in the lower index of the binomial coefficant.

Kind Regards,
Vincent
 
VincentP said:
Well not quite.
If you substitute the index of summation $ u=r-1 $ you have to change the lower as well as the upper bound of summation, because otherwise you change the number of summands. Therefore if you substitute $ u=r-1 $ we get:
$$ \sum_{r=1}^k \binom{k}{r} \binom{n-k-1}{r-1}=\sum_{u=0}^{k-1}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k-1}{k \choose k-u}\binom{n-k-1}{u} $$ Which doesn't match Vandermonde's Identity anymore, because the upper bound of summation doesn't appear in the lower index of the binomial coefficant.

Kind Regards,
Vincent

Note that,

\[\sum_{u=0}^{k-1}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k-1}{k \choose k-u}\binom{n-k-1}{u}=\sum_{u=0}^{k}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k}{k \choose k-u}\binom{n-k-1}{u}\]

since when \(u=k\) the right hand side is equal to zero. If you have any more questions about this please don't hesitate to ask. :)

Kind Regards,
Sudharaka.
 
  • #10
Sudharaka said:
Note that,

\[\sum_{u=0}^{k-1}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k-1}{k \choose k-u}\binom{n-k-1}{u}=\sum_{u=0}^{k}{k+1 \choose k-u}\binom{n-k-1}{u}-\sum_{u=0}^{k}{k \choose k-u}\binom{n-k-1}{u}\]

since when \(u=k\) the right hand side is equal to zero. If you have any more questions about this please don't hesitate to ask. :)

Kind Regards,
Sudharaka.

I think that clarifies everything, thanks so much.
Vincent
 
  • #11
VincentP said:
I think that clarifies everything, thanks so much.
Vincent

I am glad to be of help. :)

Kind Regards,
Sudharaka.
 

Similar threads

Back
Top