CombinatorialIdentity Putnam Intermediate

Problem - 2687
Compute the value of $$\displaystyle\sum_{k=1}^n k^2\binom{n}{k}$$

The answer is $\boxed{n(n+1)2^{n-2}}$.

It is well known that $k\binom{n}{k} = n\binom{n-1}{k-1}$. Therefore, $$\begin{align*} \sum_{k=1}^n k^2\binom{n}{k} =\ &\sum_{k=1}^n\left(k\cdot n\cdot\binom{n-1}{k-1}\right) \\ =\ & n \sum_{k=1}^n (k-1+1)\binom{n-1}{k-1}\\ =\ & n\sum_{k=1}^n \left((k-1)\binom{n-1}{k-1}+ \binom{n-1}{k-1}\right) \\ =\ & n \sum_{k=1}^n \left((n-1)\binom{n-2}{k-2} + \binom{n-1}{k-1}\right)\\ =\ & n(n-1)\sum_{k=2}^n\binom{n-2}{k-2} + n\sum_{k=1}^n \binom{n-1}{k-1}\\ \\ =\ & n(n-1)\cdot 2^{n-2}+n\cdot 2^{n-1}\\ \\=\ &n(n+1)\cdot 2^{n-2} \end{align*}$$

report an error