# [SOLVED]Sum with Binomial Coefficients

#### VincentP

##### New member
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
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
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
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
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
@ 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
@ 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
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
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
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
I think that clarifies everything, thanks so much.
Vincent
I am glad to be of help.

Kind Regards,
Sudharaka.