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! 
 A: *

*This identity is known as "Abel's Identity". It can be proved by generalizing:


$$\sum_{k} \binom{n}{k} (k+s-n)^{k} (r+n-k)^{n-k-1} = \frac{(r+s)^n}{r}$$
(By plugging $s=n-1,r=1$ we get the original identity.) A nicer way to write it is:
$$\sum_{k} \binom{n}{k} (s-k)^{n-k} (r+k)^{k-1} = \frac{(r+s)^n}{r}$$
Sometimes an additional parameter is added:
$$\sum_{k} \binom{n}{k} (s-tk)^{n-k} (r+tk)^{k-1} = \frac{(r+s)^n}{r}$$
This generalized identity is much easier to prove.


*

*One more hint: To prove the generalized identity, one can expand $(s-k)^{n-k}$ by the binomial theorem, and change order of summation.

A: 
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.

As yee wish; it's yer question after all.
There are the following exponential generating functions:
$$\begin{align*}
\frac{-z}{W(-z)(1+W(-z))}&=\sum_{k=0}^\infty\frac{(k-1)^k}{k!}z^k\\
\frac{-W(-z)}{z}&=\sum_{k=0}^\infty\frac{(k+1)^{k-1}}{k!}z^k
\end{align*}$$
where $W(z)$ is the Lambert function. (Sometimes, these EGFs are instead expressed in terms of the "tree function" $T(z)=-W(-z)$.) The Maclaurin series for $-W(-z)$ looks like this:
$$-W(-z)=\sum_{k=1}^\infty \frac{k^{k-1}}{k!} z^k$$
which you will have to prove, perhaps by composing two appropriate series.
Now, the OP's identity can be recast as a convolution:
$$\sum_{k=0}^n \frac{(k-1)^k}{k!}\frac{(n-k+1)^{n-k-1}}{(n-k)!}=\frac{n^n}{n!}$$
Switching to the generating function view, the convolution on the left has the generating function
$$\left(\frac{-z}{W(-z)(1+W(-z))}\right)\left(\frac{-W(-z)}{z}\right)=\frac1{1+W(-z)}$$
which means
$$\frac1{1+W(-z)}=1+\sum_{k=1}^\infty\frac{k^k}{k!}z^k$$
Now to prove the validity of this identity, you could start by deriving the formula (and the corresponding series) for the derivative of the Lambert function. Recall the fundamental relation $W(z)\exp(W(z))=z$; use implicit differentiation to derive an expression $W^\prime(z)$ which can then be manipulated to look like $\dfrac1{1+W(-z)}$. Again, the details are left up to you.
A: A nice proof uses the Lagrange-Bürman inversion formula. Start defining:
\begin{equation}
C(z) = z e^{C(z)}
\end{equation}
which gives the expansion:
\begin{equation}
e^{\alpha C(z)} = \alpha \sum_{n \ge 0} \frac{(\alpha + n)^{n - 1} z^n}{n!}
\end{equation}
Then you have:
\begin{equation}
e^{(\alpha + \beta) C(z)} = e^{\alpha C(z)} \cdot e^{\beta C(z)}
\end{equation}
Expanding and comparing both sides gives Abel's binomial theorem:
  \begin{equation}
    (\alpha + \beta) (\alpha + \beta + n)^{n - 1}
      = \sum_{0 \le k \le n}
   \binom{n}{k}
     (\alpha + k)^{k - 1}
     (\beta + n - k)^{n - k - 1}
  \end{equation}
A: As an additional observation I would like to point out that the series expansion of $$e^{\alpha T(z)}$$ where $$T(z) = z \times e^{T(z)}$$ can also be computed with the Cauchy Residue Theorem, which gives a variant of Lagrange Inversion.
We seek to compute $$[z^n] e^{\alpha T(z)} =
\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} e^{\alpha T(z)} \; dz.$$
Put $w=T(z)$ in the functional equation for $T(z)$ to get 
$$z = w e^{-w} \quad \text{and} \quad
dz = e^{-w} - w e^{-w} = (1-w) e^{-w}.$$
Substitute this into the integral to obtain
$$\frac{1}{2\pi i} \int_{|w|=\epsilon} 
\frac{e^{w(n+1)}}{w^{n+1}} e^{\alpha w} e^{-w} (1-w) \; dw.$$
This is
$$\frac{1}{2\pi i} \int_{|w|=\epsilon} 
\frac{e^{w(n+\alpha)}}{w^{n+1}} (1-w) \; dw.$$
Now we can read off the residue at $w=0$ to get
$$\frac{(n+\alpha)^n}{n!} - \frac{(n+\alpha)^{n-1}}{(n-1)!}
= (n+\alpha) \frac{(n+\alpha)^{n-1}}{n!} - n \frac{(n+\alpha)^{n-1}}{n!}
= \alpha  \frac{(n+\alpha)^{n-1}}{n!}$$
as quoted in the answer by @vonbrand above.
A: 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.
A: long ago, I see this problem was solved by $WZ$ methods.
see:http://en.wikipedia.org/wiki/Lambert%27s_W_function
the same problem we have 
$$\displaystyle\sum_{k=1}^{n-1}C_{n}^{k}k^{k-1}(n-k)^{n-k-1}=2n^{n-2}(n-1)$$
