# 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?

#### Solutions Collecting From Web of "Non combinatorial proof of formula for $n^n$?"

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*}
\sum_{k=1}^{n}&\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)!}\\
&=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.

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

Suppose we seek to evaluate
$$T_Q = \sum_{k=1}^n \frac{n!}{(n-k)!} \times k\times Q^{n-k}$$

so that our target sum $S_Q$ is $T_Q/Q$ with $Q$ instantiated to
$n.$

This turns into
$$T_Q = \sum_{k=0}^n {n\choose k} \times k! \times k\times Q^{n-k} = S_Q \times Q.$$

Observe that when we multiply two exponential generating functions of
the sequences $\{a_n\}$ and $\{b_n\}$ we get that
$$A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$
i.e. the product of the two generating functions is the generating
function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have
$$A(z) = \sum_{n\ge 0} n!\times n \times \frac{z^n}{n!} = \frac{z}{(1-z)^2}$$

and
$$B(z) = \sum_{n\ge 0} Q^n \frac{z^n}{n!} = \exp(Qz).$$

It follows that
$$n! [z^n] A(z) B(z) = n! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} \frac{z}{(z-1)^2} \exp(Qz) \; dz \\ = n! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} \frac{1}{(z-1)^2} \exp(Qz) \; dz.$$

We evaluate this using the pole at $z=1$ and $z=\infty$ and the fact
that the residues sum to zero. This requires the derivative

$$\left(\frac{1}{z^{n}} \exp(Qz)\right)’ = -\frac{n}{z^{n+1}} \exp(Qz) + \frac{1}{z^n} Q \exp(Qz)$$

which evaluated at one yields
$$\exp(Q) (Q-n).$$

Recall the formula for the residue at infinity
$$\mathrm{Res}_{z=\infty} h(z) = \mathrm{Res}_{z=0} \left[-\frac{1}{z^2} h\left(\frac{1}{z}\right)\right]$$

which in the present case yields
$$- \mathrm{Res}_{z=0} \frac{1}{z^2} z^n \frac{1}{(1/z)-1)^2} \exp(Q/z) = – \mathrm{Res}_{z=0} z^n \frac{1}{(1-z)^2} \exp(Q/z).$$

This is
$$-\sum_{q\ge 0} (q+1) \frac{Q^{n+q+1}}{(n+q+1)!} \\ = n \sum_{q\ge 0} \frac{Q^{n+q+1}}{(n+q+1)!} -\sum_{q\ge 0} (n+q+1) \frac{Q^{n+q+1}}{(n+q+1)!} \\ = n \exp(Q) – n \sum_{k=0}^n \frac{Q^k}{k!} -\sum_{q\ge 0} \frac{Q^{n+q+1}}{(n+q)!} \\ = n \exp(Q) – n \sum_{k=0}^n \frac{Q^k}{k!} -Q\sum_{q\ge 0} \frac{Q^{n+q}}{(n+q)!} \\ = n \exp(Q) – n \sum_{k=0}^n \frac{Q^k}{k!} -Q \exp(Q) + Q \sum_{k=0}^{n-1} \frac{Q^k}{k!}.$$

This shows that
$$\frac{T_Q}{n!} + \exp(Q)(Q-n) + n \exp(Q) – n \sum_{k=0}^n \frac{Q^k}{k!} -Q \exp(Q) + Q \sum_{k=0}^{n-1} \frac{Q^k}{k!} = 0$$

which is
$$\frac{T_Q}{n!} = n \sum_{k=0}^n \frac{Q^k}{k!} – Q \sum_{k=0}^{n-1} \frac{Q^k}{k!}.$$

Now at present we have the special case that $Q=n$
which finally yields
$$\frac{T_n}{n!} = \sum_{k=0}^n \frac{n^{k+1}}{k!} – \sum_{k=0}^{n-1} \frac{n^{k+1}}{k!}$$

or $$\frac{S_n\times n}{n!} = \frac{n^{n+1}}{n!}$$

which is
$$S_n = n^n$$

as claimed.

Addendum. I missed the fact that we can also obtain the formula
for $T_Q/n!$ by a trivial re-indexing operation.

We have $$\frac{T_n}{n!} = \sum_{k=0}^n \frac{1}{(n-k)!} \times k\times n^{n-k}$$

This is
$$\sum_{k=0}^{n} \frac{1}{k!} \times (n-k)\times n^{k} = \sum_{k=0}^{n} \frac{n^{k+1}}{k!} – \sum_{k=0}^{n} k \frac{n^{k}}{k!} \\ = \sum_{k=0}^{n} \frac{n^{k+1}}{k!} – \sum_{k=1}^{n} k \frac{n^{k}}{k!} = \sum_{k=0}^{n} \frac{n^{k+1}}{k!} – \sum_{k=1}^{n} \frac{n^{k}}{(k-1)!} \\ = \sum_{k=0}^{n} \frac{n^{k+1}}{k!} – \sum_{k=0}^{n-1} \frac{n^{k+1}}{k!}.$$

The claim then follows immediately.