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

• of course, the $(n-k)$ is telescoping ... – reuns May 30 '16 at 1:03

Can you show $$\sum_{k=0}^m\frac{n!}{k!}(n-k)n^k=\frac{n!}{m!}n^{m+1}$$

• Wow. It looks like I was on the right trick when I looking for induction, only on the wrong variable. This answer is as quick and dirty as it gets. Thank you very much, @Michael! – triple_sec May 29 '16 at 22:51

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

• Good one, thank you very much! – triple_sec May 29 '16 at 23:53

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.

• I’m a little ashamed to admit that I know next to nothing about contour integration on $\mathbb C$... I appreciate your input, though. – triple_sec May 30 '16 at 20:36

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*}

• (+1). Nice work. (Verified it.) Having these very different methods on one and the same page always makes for an instructive contrast. – Marko Riedel May 30 '16 at 20:12
• @Marko: I agree, especially in an area like this one in which there really are lots of reasonable ways to attack problems. – Brian M. Scott May 30 '16 at 20:15
• @BrianM.Scott Good one, thank you very much. One minor point: I’m wondering if $k\in[n+1](=\{1,\ldots,n+1\})$ should be replaced with $k\in\{0,\ldots,n\}$ in the definition of $k_f$ for the sake of full transparency. – triple_sec May 30 '16 at 20:34
• @triple_sec: It's not actually wrong, since $[n+1]$ includes all of the possible values, but it's unnecessarily confusing, and it was supposed to be $[n]$, the exact set of possible values. ($0$ can't actually occur.) Thanks for catching it. – Brian M. Scott May 30 '16 at 23:08