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.
 A: 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}.$$
A: 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.
A: 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.
A: 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.
A: 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.
A: 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.
