Non combinatorial proof of formula for $n^n$?

Question

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?

Answer 1

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.

Answer 2

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$.)