How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$? How do I prove the following identity directly?
$$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$
I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized that my $x$ and $a$ in this case are dynamic variables. Any hints? Don't give me the answer; I really want to think through this on my own, but a nudge in the correct direction would be awesome. Thanks! 

How you tried induction? First consider, the base case $n=0$. Then show that if it holds for $n$ then this implies that it holds for $n+1$. Another way could be to write $n = (n-k+1)+(k+1)$, and then do the expansion of $n^n$, i.e going the other way.
