Proof Binomial Coefficient Identity: $\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$ Wolfram show that
$\displaystyle\sum_{k=0}^n\frac{k k!}{n^k}\binom{n}{k}=n$.
click to see
How to prove this identity?
Thank you.
 A: $$\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*}$$
A: Here's a way that is similar to Brian M. Scott but a slightly different take. We prove the equivalent identity
$$
\sum_{k=1}^{n} \frac{k k!}{n^{k+1}} \binom{n}{k} = 1.
$$
Suppose we sample $n+1$ times from a group of $n$ distinct objects. The pigeonhole principle tells us that the probability of picking some object twice is $1$. Now we also can think about the probability that our first duplicate pick will be on the $k+1$th selection where $k = 1, 2, \ldots n$. That is our first $k$ picks are distinct and the $k+1$st is one of the first $k$. Our first choice doesn't matter but we then must pick $k-1$ distinct objects -- this has probability $(n-1)(n-2) \ldots (n-k+1)/n^{k-1} = n!/(n^k (n-k)!)$ followed by a pick of one the first $k$ which has probability $k/n$. Since $k$ ranges over $1$ through $n$ the probability of getting a duplicate somwhere can also be written
$$ 
\sum_{k=1}^n \frac{kn!}{n^{k+1} (n-k)!} = \sum_{k=1}^n \frac{k k!}{n^{k+1}} \binom{n}{k} 
$$
A: 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$.
A: $\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}
