Simplify $\sum^{20}_{k=10} k\binom{k-1}{9}$.

Question

Simplify $$\sum^{20}_{k=10} k\binom{k-1}{9}$$ as much as possible.

I feel like I could utilize the hockey stick identity, but have not found a way to do so with that extra $k$.

Any help would be appreciated.

Answer 1

Note that $$k{k-1 \choose 9}=k\frac{(k-1)!}{9!(k-10)!}=\frac{k!}{9!(k-10)!}=10\frac{k!}{10!(k-10)!}=10{k \choose 10}$$ Now you can use the Hockey-stick identity $$\sum^{20}_{k=10} k\binom{k-1}{9}=10\sum_{k=10}^{20}{k\choose 10}=10{21\choose 11}$$

Answer 2

If you couldn't think about how to get rid of the '$k$':

What we need to evaluate is \begin{align*} \sum^{20}_{k=10} k\binom{k-1}{9}&=20{19\choose 10}+19{18\choose 9}+\cdots+10{9\choose 9}\\ \end{align*} Using Hockey-stick identity, we can evaluate \begin{align*} \sum^{20}_{k=10} k\binom{k-1}{9}&=10{9\choose 9}+\cdots+2{17\choose 9}+{18\choose 10}\\ \sum^{20}_{k=10} k\binom{k-1}{9}&=\underbrace{\underbrace{{9\choose 9}+{10\choose 9}+\cdots+{18\choose 9}}_{{19\choose 10}+}+\underbrace{{9\choose 9}+{10\choose 9}+\cdots+{17\choose 9}+\cdots}_{{18\choose 10}+\cdots}+\underbrace{{9\choose 9}}_{{10\choose 10}}}_{\color{red}{20\choose 11}}\\ \end{align*} But we seek $20\displaystyle\sum^{20}_{k=10} \binom{k-1}{9}-\color{red}{20\choose 11}=20{20\choose10}-{20\choose 11}=10{21\choose 11}$.

Answer 3

Here is a combinatorial proof that $$\sum_{k=1}^n\,k\,\binom{k-1}{r-1}=r\,\binom{n+1}{r+1}$$ for all nonnegative integers $n$ and $r$. We use the convention that $\displaystyle\binom{M}{N}=0$ and $\displaystyle\binom{M}{-1}=0$ if $M$ and $N$ are nonnegative integers such that $M<N$. The original question is about the special case $(n,r)=(20,10)$.

Consider the coloring task of $[n]:=\{0,1,2,\ldots,n\}$ as follows. We want to color $r$ elements of $[n]$ with blue and $1$ element of $[n]$ with red in such a way that the red element is not the maximum value amongst all the colored elements. We determine the number of ways to perform this task by counting in two ways.

By choosing $r+1$ elements to be colored, we can do the task in $\displaystyle \binom{n+1}{r+1}$ ways. Among $r+1$ elements we have chosen, there are $r$ ways to pick the single element to be colored red (because the red element cannot be the maximum amongst the chosen elements), and all the other chosen elements are colored blue. Therefore, the task can be done in $$r\,\binom{n+1}{r+1}$$ ways.

Now, suppose that the largest element to be colored is $k\in\{1,2,\ldots,n\}$. Then, we can choose one of the $k$ elements in $\{0,1,2,\ldots,k-1\}$ to be colored red, which obviously can be done in $k$ ways. Ergo, there are $r-1$ elements left from $\{0,1,2,\ldots,k-1\}$ (minus the red element) to be colored blue. This can be done in $\displaystyle \binom{k-1}{r-1}$ ways. Thus, the total number of ways to color the elements of $[n]$ for each $k$ is $$k\,\binom{k-1}{r-1}\,.$$