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
    $\begingroup$ of course, the $(n-k)$ is telescoping ... $\endgroup$ – reuns May 30 '16 at 1:03
6
$\begingroup$

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

$\endgroup$
  • 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 May 29 '16 at 22:51
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
    $\begingroup$ Good one, thank you very much! $\endgroup$ – triple_sec May 29 '16 at 23:53
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$
  • $\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 May 30 '16 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$
  • $\begingroup$ (+1). Nice work. (Verified it.) Having these very different methods on one and the same page always makes for an instructive contrast. $\endgroup$ – Marko Riedel May 30 '16 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$ – Brian M. Scott May 30 '16 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 May 30 '16 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$ – Brian M. Scott May 30 '16 at 23:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.