12
$\begingroup$

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?

$\endgroup$
11
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ (+1). Thank you for the kind remark. I was quite off base applying residue calculus to this problem. $\endgroup$ – Marko Riedel Jul 16 '15 at 17:58
  • $\begingroup$ @MarkoRiedel: You're welcome! $\endgroup$ – Markus Scheuer Jul 16 '15 at 19:04
7
$\begingroup$

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

$\endgroup$
  • $\begingroup$ Very nice! I wonder if this was what Mathematica's method was $\endgroup$ – Mike Earnest Jul 15 '15 at 4:10

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.