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

Solution 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.

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