How can I calculate sum of multichoose multiplied by its argument? I need to calculate sum like this:
$\sum\limits_{k=1}^n k\textstyle\left(\!\!{n\choose k}\!\!\right)$
WolframAlpha is giving nice answer: $n{2n \choose n+1}$ But I don't know how to prove this result.
Analogous expression for simple binomial coefficients:
$\sum\limits_{k=1}^n k{n\choose k} = n \cdot 2^{n-1}$
can be easily proved by taking derivative of $(1+x)^n$ and setting $x$ to $1$ after that. But for multichoose I'm dealing with infinite series
$(1-x)^{-n} = \sum\limits_{k=0}^\infty {n-1+k\choose k} x^k$
and solution with setting $x$ to something won't work, I believe.
 A: Suppose that you want to pick a team of $n+1$ people from a group of $2n$ candidates, and you want to designate one member of the team as the captain. No two candidates are the same height, and the tallest member of the team is not allowed to be the captain. You can choose the team in $\binom{2n}{n+1}$ ways, and you then have $n$ choices for the captain, so you can complete the selection in $n\binom{2n}{n+1}$ ways.
Let the candidates be $c_1,c_2,\ldots,c_{2n}$, arranged in order of increasing height. Clearly a team of $n+1$ people will include at least one person from the set $U=\{c_{n+1},c_{n+2},\ldots,c_{2n}\}$; in particular, the tallest member of the team will be from $U$. For $k=1,\ldots,n$, how many ways are there to select the team so that $c_{n+k}$ is its tallest member?
We can do it by selecting $n-1$ team members from $\{c_1,c_2,\ldots,c_{n-1+k}\}$, which can be done in $$\binom{n-1+k}{n-1}=\binom{n-1+k}k$$ ways, and then selecting one of the remaining $k$ members of the set $\{c_1,c_2,\ldots,c_{n-1+k}\}$ to be the captain. This last step can be done in $k$ ways, so there are $k\binom{n-1+k}k$ ways to select a team whose tallest member is $c_{n+k}$. Since $k$ can be any element of $\{1,2,\ldots,n\}$, it follows that
$$\sum_{k=1}^nk\binom{n-1+k}k=n\binom{2n}{n+1}\;.$$
A: Here is a prosaic derivation using standard binomial coefficient identities.
$$
  \begin{align}
   \sum_{k=0}^n k\left(\!\!\binom nk\!\!\right) 
   &= \sum_{k=0}^n k\binom{n+k-1}k
    = \sum_{k=0}^n k\binom{n+k-1}{n-1}
\quad\text{symmetry}
\\ &= \sum_{k=0}^n (n+k-n)\binom{n+k-1}{n-1}
\\ &= \sum_{k=0}^n n\binom{n+k}n-n\sum_{k=0}^n \binom{n+k-1}{n-1}
\quad\text{absorption of $n+k$}
\\ &= n\sum_{k=0}^n(\binom{n+k}n-\binom{n+k-1}{n-1})
\\ &= n\sum_{k=0}^n\binom{n+k-1}n
\quad\text{Pascal's recurrence}
\\ &= n\binom{2n}{n+1}
\quad\text{upper summation.}
 \end{align}
$$
Note that symmetry is invalid for $(n,k)=(0,0)$, but the factor $k$ saves the day (in case $n=0$).
I've used terminology from Concrete Mathematics, except for Pascal's recurrence which is called the addition formula there. For those who have that book, it might be noteworthy that the summation obtained after symmetry is very similar to the sum $S$ in their Problem 2 from section 5.2, page 175, and so its the method used to solve it (except that Pascal's recurrence doesn't apply as neatly there).
