Proof Binomial Coefficient Identity: $\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$

As usual let $[n]=\{1,2,\ldots,n\}$, and let $S=[n]\cup\{0\}$. Let $F$ be the set of functions from $S$ to $[n]$. If $f\in F$, let

$$k(f)=\min\{k\in S:\exists\ell<k\,(f(k)=f(\ell)\}\;,$$

and let $K(f)=\{f(\ell):\ell=0,\ldots,k-1\}$; note that $|K(f)|=k(f)$.

For $k\in S$ let $F_k=\{f\in F:k(f)=k\}$. For a function $f\in F_k$ there are $\binom{n}k$ ways to choose the set $K(f)$ and $k!$ bijections from $\{0,\ldots,k-1\}$ to $K(f)$, and there are $n^{n-k}$ ways to choose $f(\ell)$ for $\ell=k+1,\ldots,n$. Finally, there are $k$ choices for $f(k)$, since it must be one of the $k$ members of $K(f)$. Thus,

$$|F_k|=kk!n^{n-k}\binom{n}k\;,$$

and

$$|F|=\sum_kkk!n^{n-k}\binom{n}k\;.$$

On the other hand, it’s clear that $|F|=n^{n+1}$, so

$$\sum_kkk!n^{n-k}\binom{n}k=n^{n+1}\;,$$

and the desired identity is now obtained by dividing through by $n^n$.

$\newcommand{\bbx}[1]{\,\bbox[8px,border:1px groove navy]{{#1}}\,} \newcommand{\braces}[1]{\left\lbrace\,{#1}\,\right\rbrace} \newcommand{\bracks}[1]{\left\lbrack\,{#1}\,\right\rbrack} \newcommand{\dd}{\mathrm{d}} \newcommand{\ds}[1]{\displaystyle{#1}} \newcommand{\expo}[1]{\,\mathrm{e}^{#1}\,} \newcommand{\ic}{\mathrm{i}} \newcommand{\mc}[1]{\mathcal{#1}} \newcommand{\mrm}[1]{\mathrm{#1}} \newcommand{\pars}[1]{\left(\,{#1}\,\right)} \newcommand{\partiald}[3][]{\frac{\partial^{#1} #2}{\partial #3^{#1}}} \newcommand{\root}[2][]{\,\sqrt[#1]{\,{#2}\,}\,} \newcommand{\totald}[3][]{\frac{\mathrm{d}^{#1} #2}{\mathrm{d} #3^{#1}}} \newcommand{\verts}[1]{\left\vert\,{#1}\,\right\vert}$

$\ds{\sum_{k = 0}^{n}{k\, k! \over n^{k}}{n \choose k} = n:\ {\large ?}}$.

\begin{align} \sum_{k = 0}^{n}{k\, k! \over n^{k}}{n \choose k} & = n!\sum_{k = 0}^{n}{k \over n^{k}}{1 \over \pars{n - k}!} = n!\sum_{k = 0}^{n}{n - k \over n^{n - k}}\,{1 \over \bracks{n - \pars{n - k}}!} \\[5mm] & = {n! \over n^{n - 1}}\sum_{k = 0}^{n}{n^{k} \over k!} - {n! \over n^{n}}\sum_{k = 1}^{n}{n^{k} \over \pars{k - 1}!} = {n! \over n^{n - 1}}\sum_{k = 0}^{n}{n^{k} \over k!} - {n! \over n^{n}}\sum_{k = 0}^{n - 1}{n^{k + 1} \over k!} \\[5mm] & =\require{cancel} \cancel{{n! \over n^{n - 1}}\sum_{k = 0}^{n}{n^{k} \over k!}} - {n! \over n^{n - 1}}\pars{\cancel{\sum_{k = 0}^{n}{n^{k} \over k!}} - {n^{n} \over n!}} = \bbx{\ds{n}} \end{align}

$$\begin{align*} \sum\limits_{k=1}^n\frac{k\cdot k!}{n^k}\binom{n}{k}&=\int\limits_0^\infty e^{-t}t\left(\sum\limits_{k=1}^n\frac{kt^{k-1}}{n^k}\binom{n}{k}\right)dt\\ &=\int\limits_0^\infty e^{-t}t\left(1+\frac{t}{n}\right)^{n-1}dt\\ &=n^2\int\limits_0^\infty e^{-nt}t(1+t)^{n-1}dt\\ &=n^2\left(\int\limits_0^\infty e^{-nt}(1+t)^n dt-\int\limits_0^\infty e^{-nt}(1+t)^{n-1} dt\right)\\ &=n^2\left(\int\limits_0^\infty e^{-nt}(1+t)^n dt-\frac{1}{n}e^{-nt}(1+t)^n|_0^\infty-\int\limits_0^\infty e^{-nt}(1+t)^n dt\right)\\ &=n \end{align*}$$