Non combinatorial proof of formula for $n^n$? I came across the below identity:
$$
n^n=\sum_{k=1}^n\frac{n!}{(n-k)!}\cdot k\cdot n^{n-k-1}
$$
A combinatorial proof of this fact is as follows. Consider the collection of lists of length $n$, where each entry is an integer between 1 and $n$ inclusive. Clearly there are $n^n$ such lists. Let the freshness of a list be the largest $k$ for which the first $k$ entries of the list are distinct. You can then show that the number of lists whose freshness is $k$ is given by $\frac{n!}{(n-k)!}\cdot k\cdot n^{n-k-1}$, so summing over $k$ gives all $n^n$ possible lists.
My question: can anyone think of a proof of this which isn't combinatorial? One that only uses algebraic manipulations, induction, or generating functions?
 A: Let
$$ f(n,k) = \cases{ \frac{n!}{(n-k)!} n^{n-k} & $k \le n$ \cr 0 & $k>n$}.$$
Then see that
$$ f(n,k) - f(n,k+1) = \frac{n!}{(n-k)!} k n^{n-k-1} .$$
Now use a telescoping sum.
(Motivation - $f(n,k)$ is the number of sequences whose freshness is at least $k$.)
A: Note: This is just a kind of streamlining of existing answers. The addendum of @MarkoRiedels answer already provides the calculation and it's using as essential step @StephenMontgomery-Smith's hint regarding telescoping.
In fact we don't need any generating functions, since we can show the validity of OPs identity by a few simple transformations.

\begin{align*}
  \color{blue}{\sum_{k=1}^{n}}&\color{blue}{\frac{n!}{(n-k)!}kn^{n-k-1}}\\
  &=n!\sum_{k=1}^{n}\frac{n-(n-k)}{(n-k)!}n^{n-k-1}\tag{1}\\
  &=n!\left(\sum_{k=1}^{n}\frac{n^{n-k}}{(n-k)!}-\sum_{k=1}^{n-1}\frac{n^{n-k-1}}{(n-k-1)!}\right)\tag{2}\\
  &=n!\left(\sum_{k=1}^{n}\frac{n^{n-k}}{(n-k)!}-\sum_{k=2}^{n}\frac{n^{n-k}}{(n-k)!}\right)\tag{3}\\
  &=n!\frac{n^{n-1}}{(n-1)!}\\
  &\color{blue}{=n^n}
  \end{align*}

Comment:


*

*In (1) we use $k=n-(n-k)$

*In (2) observe, that the upper limit of the second sum is $n-1$ since $(n-k)=0$ in case $k=n$

*In (3) we shift the index of the second sum by $1$ to prepare the telescoping.
