# Prove that $\sum _{k=1}^n\:k\left(n-1\right)^{k-1}\binom{n}{k} =n^n$

Show that $$\sum _{k=1}^n\:k\left(n-1\right)^{k-1}\begin{pmatrix}n\\ k\end{pmatrix}=n^n.$$

So far I've done: \begin{align*} \sum _{k=1}^n\:\left(n-1\right)^{k-1}\frac{n!}{\left(k-1\right)!\left(n-k\right)!} &=\ \sum _{k=1}^n\:n\left(n-1\right)^{k-1}\begin{pmatrix}n-1\\ k-1\end{pmatrix}\\ &= \sum _{k=1}^n\:2^{n-1}\cdot n\left(n-1\right)^{k-1} \\ &= n2^{n-1}\cdot \sum _{k=1}^n\:\left(n-1\right)^{k-1}. \end{align*} And got stuck in here, though it doesn't seem to be close to the correct answer ($\ n^n$) anyway... Could I get some hints on how to get this one done? Thank you. *looked for this a while, hopefully it's not a duplicate

• Where does $2^{n-1}$ come from? – Lord Shark the Unknown Aug 19 '17 at 9:42
• The sum of all combinations n-1,k-1. – Alexander Aug 19 '17 at 9:47
• @Alexander you seem to be forgetting that $$\sum (a\cdot b) \neq \left( \sum a \right) \cdot \left( \sum b \right)$$ – user12345 Aug 19 '17 at 10:16
• @userSeventeen you're right, thanks for letting me know about the mistake – Alexander Aug 19 '17 at 10:37

After setting $j=k-1$, by the Binomial Theorem we obtain $$\sum _{k=1}^n\:k\left(n-1\right)^{k-1}\binom{n}{k}= n\sum _{k=1}^n\left(n-1\right)^{k-1}\binom{n-1}{k-1}\\=n\sum _{j=0}^{n-1}\binom{n-1}{j}\left(n-1\right)^{j}1^{n-1-j}=n((n-1)+1)^{n-1}=n^n.$$
• By binomial theorem $n^{n-1}(a+b)^{n-1}=\sum _{j=0}^{n-1}\binom{n-1}{j}a^jb^{n-1-j}$ with $a=n-1$ and $b=1$. – Robert Z Aug 19 '17 at 10:01
You get $$n\sum_{k=1}^n(n-1)^{k-1}\binom{n-1}{k-1} =n\sum_{j=0}^{n-1}(n-1)^j\binom{n-1}{j} =n\sum_{j=0}^{n-1}\binom{n-1}{j}x^j$$ where $x=n-1$ and I made the substitution $j=k-1$. Can you see where to go from here?