Proving $\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1}$

[Corrected question]

I'm struggling at proving the following combinatorical identity: $$\sum_{k=0}^{n}k{n\choose k}^2 = n{2n-1 \choose n-1}$$ I would like to see a combinatorical (logical) solution, or an algebraic solution.

• Oh, my! I forgot to square the binom in the left hand side! What should I do? – NightRa Aug 17 '13 at 8:38
• You should hit the edit button and correct the question, and possibly add an indication that the question has changed. I've already done it for you now. (I can unfortunately not undo my vote to close this question.) – Marc van Leeuwen Aug 17 '13 at 8:44

So the left hand side has been changed to give the equation $$\sum_{k=0}^nk\binom nk^2 = n\binom{2n-1}{n-1}.$$ This becomes slightly easier if you replace one factor $\binom nk$ by the equivalent $\binom n{n-k}$, to give as equation to prove $$\sum_{k=0}^nk\binom nk\binom n{n-k} = n\binom{2n-1}{n-1}.$$ Suppose you have a group consisting of $n$ boys and $n$ girls. A team of $n$ has to be formed out of them, and a captian designated of the team, which has to be a girl (I did not succeed in thinking of a less discriminatory example). On one hand, one can fix the number $k$ of girls and $n-k$ of boys on the team first, then choose the team in one of $\binom nk\binom n{n-k}$ ways and a captain in one of $k$ ways, so the left hand side counts the number of possible selections. On the other hand one could start out to choose one of the $n$ girls as captain, and let her choose $n-1$ team mates among the remaining $2n-1$ children; this is counted by the right hand side.

Here's a relatively simple way to do this with just algebra.

We want to sum

$$S=\sum_{k=0}^n k\binom{n}{k}^2 = \sum_{k=0}^n k\binom{n}{k}\binom{n}{n-k} .$$

Note, using symmetry, that this is equal to

$$\sum_{k=0}^n (n-k)\binom{n}{k}\binom{n}{n-k}.$$

Adding these, we get

$$2S=n\sum_{k=0}^n \binom{n}{k}\binom{n}{n-k}.$$

This means it suffices to evaluate

$$\sum_{k=0}^n \binom{n}{k}\binom{n}{n-k}.$$ This sum is $\binom{2n}{n}$. For justification, I quote another answer:

$$(1+x)^n(x+1)^n=(1+x)^{2n}$$

$$\left(\sum_{0\le r\le n}\binom nr x^r \right)\left(\sum_{0\le r\le > n}\binom nr x^{n-r}\right)=\sum_{0\le r\le 2n}\binom {2n}rx^r$$

Compare the coefficients of $x^n.$

But wait? We have $2n$ and $n$ where we want $2n-1$ and $n-1$! This is not a problem. Recall the "in-n-out" formula:

$$\binom{n}{k}=\frac{n}{k}\binom{n-1}{k-1}.$$

It’s false as stated. Take $n=3$:

$$\sum_{k=0}^3k\binom3k=0\cdot1+1\cdot3+2\cdot3+3\cdot1=12\ne 30=3\binom52$$

In fact

$$\sum_{k=0}^nk\binom{n}k=\sum_{k=0}^nn\binom{n-1}{k-1}=n\sum_{k=1}^n\binom{n-1}{k-1}=n\sum_{k=0}^{n-1}\binom{n-1}k=n2^{n-1}\;.$$

A combinatorial proof of this corrected identity isn’t too hard to find. Start with a pool of $n$ people. For each $k\in\{0,\dots,n\}$, the term $k\binom{n}k$ is the number of ways to choose a $k$-person team and then pick one member of the team to be captain. Summing over $k$ gives the total number of ways to pick a team of any size up through $n$ and then choose one of its members to be captain. Alternatively, we can first pick any of the $n$ people to be the team captain, and we can then pick any subset of the remaining $n-1$ people to make up the rest of the team; this combination of selections can be made in $n2^{n-1}$ ways.

Added: For the corrected question, imagine that you have $n$ women and $n-1$ men. There are $\binom{2n-1}n=\binom{2n-1}{n-1}$ ways to choose a team of $n$ people from that group and $n$ ways to choose one of them to be captain, so we can choose a team of $n$ with its captain in $n\binom{2n-1}{n-1}$ ways. Alternatively, we can choose $k-1$ men in $\binom{n-1}{k-1}$ ways and $n-k$ women in $\binom{n}{n-k}=\binom{n}k$ ways to get our team of $n$, and we can then choose a captain in $n$ ways, for a total of

$$n\binom{n-1}{k-1}\binom{n}k=k\binom{n}k^2$$

teams with captain having exactly $k-1$ men. Here I'm using the identity $k\binom{n}k=n\binom{n-1}{k-1}$, which is easily verified algebraically or combinatorially. Now just sum over the possible values of $k$ to get the result.

• Apart from the first sentence, this looks a lot like your answer here. I know finding your previous answer may be more effort than typing it again, but this site would benefit from linking the same questions together. – Marc van Leeuwen Aug 17 '13 at 8:41
• @Marc: The question of effort didn't even arise: I didn't remember that there was a previous answer that was relevant. In any case I don't consider it the same question; closely related, certainly, but definitely not the same. – Brian M. Scott Aug 17 '13 at 9:09
• Well the expression in the title of the question referred to matches what used to be the left hand side of the equation here, up to the names of the variables and the inclusion of the unproductive $k=0$ (but I'll admit there was \sum\limits there and \sum here), and you rejected the proposed right hand side anyway. Of course now the left hand side has been changed here, they are no longer the same questions at all. – Marc van Leeuwen Aug 17 '13 at 9:42
• @Marc: I just don't consider a question asking for a proof of the false $A=B$ the same as a question asking for a proof of the correct $A=C$, where $B$ and $C$ are quite different. The answers are largely similar, but the questions are to my mind distinctly different. – Brian M. Scott Aug 17 '13 at 9:54

Here is what might be the worst possible solution to this problem. We begin like ccorn does by noting

\begin{aligned} \sum_{k=0}^n k\,\binom{n}{k}^2 &= \sum_{k=0}^n k\,\binom{n}{k}^2\,x^{k-1}\bigg|_{x=1} = \left(\frac{\mathrm{d}}{\mathrm{d}x}\sum_{k=0}^n \binom{n}{k}^2\,x^k\right)\bigg|_{x=1} \end{aligned}.

We examine

$$\sum_{k=0}^n \binom{n}{k}^2 x^k.$$

Let $y=x^{1/2}$. The above expression can be rewritten as

$$\int_0^{1 } \left(\sum_{k=0}^n \binom{n}{k}y^k e^{2\pi ikt} \right) \left(\sum_{k=0}^n \binom{n}{k}y^k e^{-2\pi ikt} \right) \ dt.$$

Using the binomial theorem, this becomes

$$\int_0^{1 } \left(1+y e^{2\pi it}\right)^n \left(1+y e^{-2\pi it} \right)^n \ dt= \int_0^1 (1 + y(e^{2\pi i t }+e^{-2\pi i t}) + x)^n \ dt$$

$$= \int_0^1 (1 + 2y\cos(2\pi t)+x)^n \ dt.$$

We want the derivative of this evaluated at $1$. We can pass the derivative with respect to $x$ inside the integral sign, so our desired expression is

$$n\int_0^1 \left(\frac{\cos(2\pi t)}{\sqrt x} +1\right) (2\sqrt x \cos(2\pi t) + x +1)^{n-1} \ dt \bigg|_{x=1}=$$

$$n\int_0^1 \left({\cos(2\pi t)} +1\right) (2 \cos(2\pi t) + 2)^{n-1} \ dt .$$

$$=2^{n-1}n \int_0^1 \left({\cos(2\pi t)} +1\right)^n \ dt .$$

This becomes $$2^{2n-1}n \int_0^1 (\cos(\pi t) )^{2n} \ dt .$$

Using integration by parts, we have the reduction formula

$$\int_0^1 (\cos(\pi t) )^{2n} \ dt = \frac{2n-1}{2n} \int_0^1 (\cos(\pi t) )^{2n-2} \ dt.$$

This gives the product

$$2^{2n-1}\cdot n \cdot \frac{2n-1}{2n} \frac{2n-3}{2n-2} \cdots \frac{1 }{ 2}\cdot 1 =2^n \cdot n \cdot \frac{2n-1}{n}\cdot \frac{2n-3}{n-1} \cdots \frac{1 }{ 1}\cdot 1$$

$$= n \frac{(2n-1)!}{(n-1)!n!}$$

Now note that $$\binom{2n-1}{n-1}=\frac{(2n-1)!}{(n-1)!n!},$$

so we recover

$$n\binom{2n-1}{n-1}$$

as desired.

Note: This answer refers to the earlier, uncorrected question and is now outdated.

For completeness, here is a non-combinatorial way to see the formula as corrected in Brian Scott's indispensable answer:

\begin{aligned} \sum_{k=0}^n k\,\binom{n}{k} &= \sum_{k=0}^n k\,\binom{n}{k}\,x^{k-1}\bigg|_{x=1} = \left(\frac{\mathrm{d}}{\mathrm{d}x}\sum_{k=0}^n \binom{n}{k}\,x^k\right)\bigg|_{x=1} \\ &= \left(\frac{\mathrm{d}}{\mathrm{d}x}(x+1)^n\right)\bigg|_{x=1} = \left(n\,(x+1)^{n-1}\right)\big|_{x=1} = n\,2^{n-1} \end{aligned}

This is easy to keep in mind: Sum over a Pascal triangle row $\Rightarrow$ binomial theorem; factor $k$ (summation index) $\Rightarrow$ derivative. Works only for the full summation range $k=0,\ldots,n$ however.

Update: More methods given here for similar questions.

Suppose we seek to evaluate $$\sum_{k=0}^n {n\choose k} \times k \times {n\choose k}.$$

Start from $${n\choose k} = \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} (1+z)^n dz.$$

This yields the following expression for the sum $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \sum_{k=0}^n {n\choose k} \times k \times \frac{(1+z)^n}{z^{k+1}} \; dz \\= \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \sum_{k=0}^n {n\choose k} \times k \times \frac{1}{z^k} \; dz$$

Now by applying the operator $z\frac{d}{dz}$ to $(1+z)^n$ we get $$\sum_{q=0}^n {n\choose q} \times q \times z^q = nz(1+z)^{n-1}$$ so that the sum in the integral simplifies to $$\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{(1+z)^n}{z} \times \frac{n}{z} \left(1+\frac{1}{z}\right)^{n-1} \; dz \\ = \frac{1}{2\pi i} \int_{|z|=\epsilon} n\times \frac{(1+z)^{2n-1}}{z^{n+1}}\; dz.$$ It follows that the value of the sum is given by $$n\times [z^n] (1+z)^{2n-1} = n\times {2n-1\choose n} = n\times {2n-1\choose n-1}.$$

A trace as to when this method appeared on MSE and by whom starts at this MSE link.