Welcome to our community

Be a part of something great, join today!

[SOLVED] Sum with Binomial Coefficients

VincentP

New member
Feb 17, 2012
7
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

Well-known member
MHB Math Helper
Jan 26, 2012
1,404
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

New member
Feb 17, 2012
7
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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
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

MHB Oldtimer
Staff member
Feb 7, 2012
2,725
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

New member
Feb 17, 2012
7
@ 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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621
@ 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

New member
Feb 17, 2012
7
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-known member
MHB Math Helper
Feb 5, 2012
1,621
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

New member
Feb 17, 2012
7
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

Well-known member
MHB Math Helper
Feb 5, 2012
1,621