- Thread starter
- #1

- Thread starter VincentP
- Start date

- Thread starter
- #1

Maybe expanding the binomial coefficients would help. Recall that $ \displaystyle {n\choose{m}} = \frac{n!}{m!(n-m)!} $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

- Thread starter
- #3

Well I have tried that of course:Maybe expanding the binomial coefficients would help. Recall that $ \displaystyle {n\choose{m}} = \frac{n!}{m!(n-m)!} $

$$ \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.

- Feb 5, 2012

- 1,621

Hi Vincent,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

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.

- Moderator
- #5

- Feb 7, 2012

- 2,807

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.

- Thread starter
- #6

- Feb 5, 2012

- 1,621

You are welcome. I have neglected an in between step that may have aroused the confusion.@ 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!

\[\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.

- Thread starter
- #8

Well not quite.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.

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

- Feb 5, 2012

- 1,621

Note that,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

\[\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.

- Thread starter
- #10

I think that clarifies everything, thanks so much.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.

Vincent

- Feb 5, 2012

- 1,621

I am glad to be of help.I think that clarifies everything, thanks so much.

Vincent

Kind Regards,

Sudharaka.