Problem: Show that $ \sum_{k=0}^n k\binom{n}{k}^2=n\binom{2 n-1}{n-1} $ Solution: The tricky part about this sum on the LHS is the ${n \choose k}^{2}$ term. Really, this is just ${n \choose k} {n \choose n-k}$, which *looks* more like creating a subset of $n$ elements from two sets of $n$ elements where we select $k$ from the first and the remaining $n-k$ from the second. In particular, consider $D = \{(x,A): x \in X, A \subset X \cup Y, |A| = |Y| = |X| = n, X \cap Y = \emptyset\}$ One way to count this is to consider the number of elements in $X$ that will contribute to $X$. For a fixed $k$ with $0 \leq k \leq n$, if we choose $k$ elements from $X$ to belong in $A$ then there are $n-k$ elements left that we must choose from $Y$ to be in $A$. Selecting some $x \in X$ to belong to our triple, we see by the multiplication principle that the number of ways to do this is $k { n \choose k} {n \choose n-k} = k{n \choose k}^2$. Summing over all $k$, we see that $|D| = \sum_{k=0}^n k\binom{n}{k}^2$. On the other hand, it is clear that if we simply select some element from $X$, say $x$ to belong in $A$, there are $n$ ways to do this and ${2n - 1 \choose n-1}$ ways to select the remaining $n-1$ elements from $X \cup Y \backslash \{ x \}$. Hence, the conclusion follows.