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.
Best Answer
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.