Proving identities like $\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}$ combinatorially I have to give a combinatorial proof of
$$\sum_{k=1}^nk{n\choose k}^2=n{2n-1\choose n}.$$
I find it difficult to solve such problems. I'm not a brilliant person and never will be so I need to have algorithms to solve most problems. Usually I won't just "see" solutions unless I have a thorough enough understanding of a theory. This is also the case here. I know what the symbols mean, but I don't see what I should count and how to obtain the identity.
I think the right-hand side counts $n$-element subsets of a $(2n-1)$-element set with one element chosen to be "special". I think I should find a partition of the set of such subsets into $n$ parts so that the left-hand side is the sum of the cardinalities of the parts. Is there $n$ of anything on the right-hand side? Well, there are $n$ choices for the "special" elements, but only after I've chosen the $n$-element subset. Otherwise I can choose the "special element" in $2n-1$ ways.
This is a homework problem so I probably shouldn't ask for a full solution. But I would like to have some guidelines for approaching such problems, perhaps based on this example.
 A: Since $\binom{n}{k} = \dfrac{n}{k}\binom{n-1}{k-1}$ the identity can be written as $$\sum_{k=1}^n\binom{n}{n-k}\binom{n-1}{k-1} = \binom{2n-1}{n-1}.$$
Suppose we have $2n-1$ items in line and we need to choose $n-1$ items from them. The right hand side is the number of ways to do this in the obvious way. Another way to choose our $n-1$ items from this line: Divide the line into two sections; the first section contains the first $n$ items, the second contains the last $n-1$ items. When picking $n-1$ items from the entire line, we could pick all $n-1$ from the first line and none from the second ($k=1$), or $n-2$ from the first line and $1$ from the second ($k=2$) ... ... or none from the first line and $n-1$ from the second ($k=n$).
A: For $a,b,n \in \mathbb{N}$ we have
$$\binom{a+b}{n} = \sum_{p+q=n} \binom{a}{p} \cdot \binom{b}{q}$$
since both sides count the subsets of $\{1,\dotsc,a\} \sqcup \{1,\dotsc,b\}$ with $n$ elements. This could also be derived from the isomorphism $\Lambda^n(V \oplus W) = \bigoplus_{p+q=n} \Lambda^p(V) \otimes \Lambda^q(W)$ of exterior powers, where $V,W$ are free modules of rank $a$ resp. $b$ (decategorification).
In particular,
$$\sum_{k=0}^{n} k \binom{n}{k}^2 = n \sum_{k=0}^{n} \binom{n}{n-k} \binom{n-1}{k-1}=n \binom{2n-1}{n-1}=n \binom{2n-1}{n}.$$
One can also derive a lot of other formulas as a special case, for example
$$\sum_{k=0}^{n} \binom{n}{k}^2 = \sum_{k=0}^{n} \binom{n}{k} \binom{n}{n-k} = \binom{2n}{n}.$$
A: It seems easier to look at the left-hand side : 
$\sum \binom n k ^2 = \binom {2n} n$ is the number of ways to choose $n$ elements out of a set $X$ of $2n$ elements, where we are given a partition $X = X_1 \cup X_2$ with $\# X_i = n$.
Next, $\sum k \binom n k ^2$ is the number of ways to do this and then choose a special element among the ones chosen in $X_1$. So, reversing the order of the choices (choose the special element first), then forgetting as much as possible about the partition, you get that is the number of ways to pick one special element in $X_1$ and then pick $n-1$ other elements in $X$.
Then it shouldn't be too hard to explain why this is equal to the right-hand side.
A: Since you said you'd prefer a hint, I will show you how a related problem is approached. In retrospect I can see that this is not what is meant by a combinatorial proof, but maybe it will still be helpful.
Suppose you want to prove that:
$$\sum^n_{s=0} \binom{n}{s}^2 = \binom{2n}{n}$$
To do the above, consider the binomial expansions of both sides of:
$$(1+x)^n(1+x)^n = (1+x)^{2n}$$
(i.e. expand the RHS binomially and expand both parts of the LHS binmially and write out the product).
I have not verified it yet but I believe a similar approach may work for the problem you provided, as long as you choose an appropriate identity to start with.
A: $\newcommand{\angles}[1]{\left\langle\, #1 \,\right\rangle}
 \newcommand{\braces}[1]{\left\lbrace\, #1 \,\right\rbrace}
 \newcommand{\bracks}[1]{\left\lbrack\, #1 \,\right\rbrack}
 \newcommand{\ceil}[1]{\,\left\lceil\, #1 \,\right\rceil\,}
 \newcommand{\dd}{{\rm d}}
 \newcommand{\ds}[1]{\displaystyle{#1}}
 \newcommand{\expo}[1]{\,{\rm e}^{#1}\,}
 \newcommand{\fermi}{\,{\rm f}}
 \newcommand{\floor}[1]{\,\left\lfloor #1 \right\rfloor\,}
 \newcommand{\half}{{1 \over 2}}
 \newcommand{\ic}{{\rm i}}
 \newcommand{\iff}{\Longleftrightarrow}
 \newcommand{\imp}{\Longrightarrow}
 \newcommand{\pars}[1]{\left(\, #1 \,\right)}
 \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}}
 \newcommand{\pp}{{\cal P}}
 \newcommand{\root}[2][]{\,\sqrt[#1]{\vphantom{\large A}\,#2\,}\,}
 \newcommand{\sech}{\,{\rm sech}}
 \newcommand{\sgn}{\,{\rm sgn}}
 \newcommand{\totald}[3][]{\frac{{\rm d}^{#1} #2}{{\rm d} #3^{#1}}}
 \newcommand{\verts}[1]{\left\vert\, #1 \,\right\vert}$
$\ds{\sum_{k = 1}^{n}k{n \choose k}^{2} = n{2n - 1 \choose n}:\ {\large ?}}$

\begin{align}&\sum_{k = 1}^{n}k{n \choose k}^{2}
=\sum_{k = 1}^{n}k{n \choose k}\oint_{\verts{z}\ =\ 1}
{\pars{1 + z}^{n} \over z^{k + 1}}\,{\dd z \over 2\pi\ic}
=\oint_{\verts{z}\ =\ 1}
{\pars{1 + z}^{n} \over z}\sum_{k = 1}^{n}k{n \choose k}\pars{1 \over z}^{k}
\,{\dd z \over 2\pi\ic}
\end{align}

Note that
$\ds{\sum_{k = 1}^{n}k{n \choose k}a^{k}
     =a\,\partiald{}{a}\sum_{k = 0}^{n}{n \choose k}a^{k}
     =a\,\partiald{\pars{1 + a}^{n}}{a} = na\pars{1 + a}^{n - 1}}$ such that

\begin{align}
&\color{#66f}{\large\sum_{k = 1}^{n}k{n \choose k}^{2}}
=\oint_{\verts{z}\ =\ 1}
{\pars{1 + z}^{n} \over z}\bracks{n\,{1 \over z}\,\pars{1 + {1 \over z}}^{n - 1}}
\,{\dd z \over 2\pi\ic}
\\[3mm]&=n\oint_{\verts{z}\ =\ 1}{\pars{1 + z}^{2n - 1} \over z^{n + 1}}
\,{\dd z \over 2\pi\ic}
=\color{#66f}{\large n{2n - 1 \choose n}}
\end{align}

A: Let $S=\displaystyle\sum_{k}^n k{n \choose k}^2=0{n \choose 0}^2+1{n \choose 1}^2+\dots+n{n \choose n}^2$, then we have
$$
\begin{array}{c}
S&=&\displaystyle 0{n \choose 0}^2&+&\displaystyle 1{n \choose 1}^2&+&\dots&+&\displaystyle n{n \choose n}^2\\
S&=&\displaystyle n{n \choose n}^2&+&\displaystyle (n-1){n \choose n-1}^2&+&\dots&+&\displaystyle 0{n \choose 0}^2\\\hline
2S&=&\displaystyle n{n \choose 0}^2&+&\displaystyle n{n \choose 1}^2&+&\dots&+&\displaystyle n{n \choose n}^2.
\end{array}
$$
Thus
$2S=\displaystyle n\left[ {n \choose 0}^2+ {n \choose 1}^2+\dots+ {n \choose n}^2\right]=n{2n\choose n}=n\cdot \frac{2n}{n}{2n-1\choose n}$,
we havem $\displaystyle\sum_{k}^n k{n \choose k}^2=S=n{2n-1\choose n}.$
