1

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.

Martin Sleziak
  • 53,687
iw.kuchin
  • 115

2 Answers2

4

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

Brian M. Scott
  • 616,228
  • Wow. Thanks for the elegant combinatorial prove. Small fix: I believe, last formula should use $n+1$ instead of $n$ in right part. Thanks again. – iw.kuchin Sep 27 '13 at 07:36
  • @iw.kuchin: You’re welcome, and thanks for catching the typo in the last formula. – Brian M. Scott Sep 27 '13 at 07:39
  • There is a remarkable coincidende with this answer I gave yesterday to a somewhat different question, especially with the Added part (though more recent than the current answer, I formulated taht addition without having read this answer, just by combining the combinaotiral arguments before it). – Marc van Leeuwen Sep 27 '13 at 08:42
  • @Marc: I’ll be damned: they do work out in remarkably similar fashion. (I didn’t look further at the earlier question after I saw that you’d answered it at length: I was catching up on what I’d missed while I was asleep.) – Brian M. Scott Sep 27 '13 at 08:54
2

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).

Marc van Leeuwen
  • 115,048
  • Thanks for the idea of absoption of $k$ into binomial coefficient. – iw.kuchin Sep 27 '13 at 09:40
  • How is $\displaystyle \sum_{k=0}^n k \binom{n}{k}=\sum_{k=0}^n k\binom{n+k-1}{k}$? Or does $\displaystyle \left(! ! \binom{n}{k} ! !\right)$ - this notation mean something else? Because they clearly aren't equal as the first one evaluates to $n ~2^{n-1}$ and the second one $\displaystyle n\binom{2n}{n+1}$ as you showed. – V.G Feb 27 '21 at 12:55
  • Yes, $\left(! ! \binom{n}{k} ! !\right)$ means the number of $k$-multisets that can be chosen out of an $n$-element base set. That number is equal to the binomial coefficient $\binom{n+k-1}k$. – Marc van Leeuwen Mar 03 '21 at 17:22