Prove $\sum_{k=0}^{n}\frac{n!}{k!}(n-k)n^k=n^{n+1}$ for any $n\in\mathbb N$. I want to prove the following:
$$\sum_{k=0}^{n}\frac{n!}{k!}(n-k)n^k=n^{n+1}\quad\text{for any $n\in\mathbb N$.}$$ I tried induction and invoking the binomial theorem, to little avail. I’m looking for some quick and dirty solution. Thanks for any hints.

As the answers below reveal, the following update I had added earlier is not really of much use, so I struck it.
Update: After some rearrangements, the left-hand side above can be rewritten as $$\require{enclose}
     \enclose{horizontalstrike}{n\sum_{k=0}^{n-1}\binom{n-1}{k}n^k(n-k)!}$$ This form seems to suggest resorting to the binomial theorem.
 A: Can you show $$\sum_{k=0}^m\frac{n!}{k!}(n-k)n^k=\frac{n!}{m!}n^{m+1}$$
A: Suppose we seek to evaluate
$$\sum_{k=0}^n \frac{n!}{k!} (n-k) n^k
= n! n^n \sum_{k=0}^n \frac{n-k}{k!} n^{k-n}.$$
Introduce
$$n^{k-n} = 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{z^k}{z^{n+1}} \frac{1}{1-z/n} \; dz.$$
Observe that this integral provides an Iverson bracket, as it vanishes
when $k\gt n.$ Therefore we may extend $k$ to infinity.
We get for the sum
$$n! n^n 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{1}{1-z/n} \sum_{k\ge 0} \frac{n-k}{k!} z^k
\; dz
\\ = n! n^n 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{1}{1-z/n} 
\left(n \exp(z) - z \sum_{k\ge 1} \frac{1}{(k-1)!} z^{k-1}\right)
\; dz
\\ = n! n^n 
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{n}{n-z} 
\left(n \exp(z) - z \exp(z)\right)
\; dz
\\ = n! n^{n+1}
\frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\exp(z)
\; dz
=  n! n^{n+1} \frac{1}{n!} = n^{n+1}.$$
This concludes the argument.
A: Here’s a combinatorial argument.
Clearly $n^{n+1}$ is the number of functions from $\{0,1,\ldots,n\}$ to $[n]$. If $f$ is any such function, let
$$k_f=\min\left\{k\in[n]:\exists\ell<k\big(f(k)=f(\ell)\big)\right\}\;.$$
For a given $k\in[n]$, how many of these functions have $k_f=k$?


*

*There are $n^{\underline k}=n(n-1)\ldots(n-k+1)$ ways to choose $k$ distinct values for $f(0),\ldots,f(k-1)$.  

*There are then $k$ ways to choose one of these values for $f(k)$.  

*And finally there are $n^{n-k}$ ways to choose values for $f(i)$ with $k<i\le n$.


Summing over the possible values of $k$ then yields the result:
$$\begin{align*}
n^{n+1}&=\sum_{k=1}^nkn^{\underline k}n^{n-k}\\
&=\sum_{k=0}^nkn^{\underline k}n^{n-k}\\
&=\sum_{k=0}^n(n-k)n^{\underline{n-k}}n^k\\
&=\sum_{k=0}^n\frac{n!}{k!}(n-k)n^k\;.
\end{align*}$$
A: One way is to rewrite the L.H.S. as a telescoping sum: $\displaystyle\sum_{k=0}^{n}\left(\frac{n!~n^{k+1}}{k!}-\frac{n!~n^k}{(k-1)!}\right)$.
