Compute $S_n=\sum_{k=1}^{n} {n \choose k} k^2$ Compute $S_n=\sum_{k=1}^{n} {n \choose k} k^2$.
This is took from Arthur Engel’s book, from the enumerative combinatorics chapter. I can’t understand the author’s explanation. He says the sum represents the number of ways to choose a comittee, a chairman, and its secretary (possible the same person) from a set with n elements. I don’t understant why this happens.
 A: ${n \choose k} k^2={n \choose k} {k \choose 1} {k \choose 1}$ this is the way to choose  $k$ objects form $n$ object, and choose two objects form  those $K$ object with replacement. so
$\sum_{k=1}^{n}{n \choose k} k^2=\sum_{k=1}^{n}{n \choose k} {k \choose 1} {k \choose 1}$ is 
the ways to choose a committee with arbitrary numbers, and then choose two people with replacement from the comittee. 
A: Use generating function techniques. You know:
$\begin{align*}
  (1 + z)^n
    &= \sum_k \binom{n}{k} z^k \\
  z \frac{d}{d z} \sum_k \binom{n}{k} z^k 
    &= \sum_k \binom{n}{k} k z^k \\
  z \frac{d}{d z} \left( z \frac{d}{d z} (1 + z)^n \right)
    &= \sum_k \binom{n}{k} k^2 z^k \\
    &= \frac{(1 + z)^n (n^2 z^2 + n z)}{(1 + z)^2}
\end{align*}$
Your sum is the value of this at $z = 1$, i.e. $(n + 1) n \cdot 2^{n - 2}$
A: Here is the algebric way to prove it :
Let $ n $ be a positive integer greater than $ 1 $, know : $$ \left(\forall k\in\left[\!\left[1,n-1\right]\!\right]\right),\ k^{2}\displaystyle\binom{n-1}{k}=k\left(n-k\right)\displaystyle\binom{n-1}{k-1}$$
Thus, \begin{aligned} \displaystyle\sum_{k=1}^{n-1}{k^{2}\displaystyle\binom{n-1}{k}}&=\displaystyle\sum_{k=1}^{n-1}{k\left(n-k\right)\displaystyle\binom{n-1}{k-1}} \\ &=n\displaystyle\sum_{k=1}^{n-1}{k\displaystyle\binom{n-1}{k-1}}-\displaystyle\sum_{k=1}^{n-1}{k^{2}\displaystyle\binom{n-1}{k-1}}\\ \displaystyle\sum_{k=1}^{n-1}{k^{2}\displaystyle\binom{n-1}{k}}&=n\displaystyle\sum_{k=0}^{n-2}{\left(k+1\right)\displaystyle\binom{n-1}{k}}-\displaystyle\sum_{k=1}^{n-1}{k^{2}\displaystyle\binom{n-1}{k-1}}\\ \iff \displaystyle\sum_{k=1}^{n-1}{k^{2}\left[\displaystyle\binom{n-1}{k}+\displaystyle\binom{n-1}{k-1}\right]}&=n\displaystyle\sum_{k=0}^{n-2}{k\displaystyle\binom{n-1}{k}}+n\displaystyle\sum_{k=0}^{n-2}{\displaystyle\binom{n-1}{k}}\\ \iff \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \displaystyle\sum_{k=1}^{n}{k^{2}\displaystyle\binom{n}{k}}&=n\displaystyle\sum_{k=0}^{n-1}{k\displaystyle\binom{n-1}{k}}+n\displaystyle\sum_{k=0}^{n-1}{\displaystyle\binom{n-1}{k}}\end{aligned}
(In the fourth line, we added $ \sum\limits_{k=1}^{n-1}{k^{2}\binom{n-1}{k-1}} $ to both sides of the equation, and in the last line we used pascal's triangle formula, then we added $ n^{2} $ to both sides of the equation)
Using an index change by symmetry, we have $ \sum\limits_{k=0}^{n-1}{k\binom{n-1}{k}}=\sum\limits_{k=0}^{n-1}{\left(n-1-k\right)\binom{n-1}{k}} $, thus $ \sum\limits_{k=0}^{n-1}{k\binom{n-1}{k}}=\frac{n-1}{2}\sum\limits_{k=0}^{n-1}{\binom{n-1}{k}} $, hence : $$ \fbox{$
   \begin{array}{rcl}\displaystyle\sum_{k=0}^{n}{k^{2}\displaystyle\binom{n}{k}}&=\displaystyle\frac{n\left(n+1\right)}{2}\displaystyle\sum_{k=0}^{n-1}{\displaystyle\binom{n-1}{k}}\end{array}
   $} $$
Which means the final result would be : $ 2^{n-2}n\left(n+1\right) $
