Sum with Binomial Coefficients

[VincentP]

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

 

[Prove It]

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

 

[VincentP]

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.

 

[Sudharaka]

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.

 

[Opalg]

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.

 

[VincentP]

@ 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!

 

[Sudharaka]

@ 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.

 

[VincentP]

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

 

[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

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.

 

[VincentP]

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

 

[Sudharaka]

I think that clarifies everything, thanks so much.
Vincent

I am glad to be of help. :)

Kind Regards,
Sudharaka.