8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ of course, the $(n-k)$ is telescoping ... $\endgroup$
    – reuns
    Commented May 30, 2016 at 1:03

4 Answers 4

10
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Good one, thank you very much! $\endgroup$
    – triple_sec
    Commented May 29, 2016 at 23:53
6
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ 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! $\endgroup$
    – triple_sec
    Commented May 29, 2016 at 22:51
6
$\begingroup$

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.

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

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

$\endgroup$
4
  • $\begingroup$ (+1). Nice work. (Verified it.) Having these very different methods on one and the same page always makes for an instructive contrast. $\endgroup$ Commented May 30, 2016 at 20:12
  • $\begingroup$ @Marko: I agree, especially in an area like this one in which there really are lots of reasonable ways to attack problems. $\endgroup$ Commented May 30, 2016 at 20:15
  • $\begingroup$ @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. $\endgroup$
    – triple_sec
    Commented May 30, 2016 at 20:34
  • 1
    $\begingroup$ @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. $\endgroup$ Commented May 30, 2016 at 23:08

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .