Closed form of $\sum_{n = 1}^{\infty} \frac{n^{n - k}}{e^{n} \cdot n!}$

Solution 1:

Computing the Sums

Using the Taylor series for the Lambert W function derived in this answer, we see that $$\newcommand{\W}{\operatorname{W}} -\W(-x)=\sum_{n=1}^\infty\frac{n^{n-1}}{n!}x^n\tag1 $$ Define $u(x)=-\W(-x)$, then we have $$ \begin{align} 1&=u(1/e)\tag{2a}\\[3pt] x&=u(x)\,e^{-u(x)}\tag{2b}\\ \frac{\mathrm{d}x}x&=\frac{1-u(x)}{u(x)}\,\mathrm{d}u(x)\tag{2c} \end{align} $$

Define $u_1=u$ and $$ u_{k+1}(x)=\int_0^xu_k(t)\,\frac{\mathrm{d}t}{t}\tag3 $$ Then $$ u_k(x)=\sum_{n=1}^\infty\frac{n^{n-k}}{n!}x^n\tag4 $$ We will show that $$ u_k(x)=P_k(u(x))\tag5 $$ where $P_k(x)$ is a degree $k$ polynomial with no constant term. It is true for $k=1$ with $P_1(x)=x$. Assume it is true for $k$, then $(3)$ and $\text{(2c)}$ imply $$ \begin{align} u_{k+1}(x) &=\int_0^xP_k(u(t))\,\frac{\mathrm{d}t}t\\ &=\int_0^{u(x)}P_k(u)\,\frac{1-u}u\,\mathrm{d}u\\[9pt] &=P_{k+1}(u(x))\tag6 \end{align} $$ Thus, $(5)$ is true for $k+1$.

Equation $(6)$ enables us to compute $$ P_{k+1}(x)=\int_0^xP_k(t)\frac{1-t}t\,\mathrm{d}t\tag7 $$ The initial part of the sequence of polynomials is $$ \begin{align} P_1(x)&=x\\ P_2(x)&=x-\tfrac12x^2\\ P_3(x)&=x-\tfrac34x^2+\tfrac16x^3\\ P_4(x)&=x-\tfrac78x^2+\tfrac{11}{36}x^3-\tfrac1{24}x^4\\ P_5(x)&=x-\tfrac{15}{16}x^2+\tfrac{85}{216}x^3-\tfrac{25}{288}x^4+\tfrac1{120}x^5\\ P_6(x)&=x-\tfrac{31}{32}x^2+\tfrac{575}{1296}x^3-\tfrac{415}{3456}x^4+\tfrac{137}{7200}x^5-\tfrac1{720}x^6\\ P_7(x)&=x-\tfrac{63}{64}x^2+\tfrac{3661}{7776}x^3-\tfrac{5845}{41472}x^4+\tfrac{12019}{432000}x^5-\tfrac{49}{14400}x^6+\tfrac1{5040}x^7\\ P_8(x)&=x{-}\tfrac{127}{128}x^2{+}\tfrac{22631}{46656}x^3{-}\tfrac{76111}{497664}x^4{+}\tfrac{874853}{25920000}x^5{-}\tfrac{13489}{2592000}x^6{+}\tfrac{121}{235200}x^7{-}\tfrac1{40320}x^8 \end{align}\tag8 $$ Applying $\text{(2a)}$, $(4)$, and $(5)$, we get $$ \sum_{n=1}^\infty\frac{n^{n-k}}{e^nn!}=P_k(1)\tag9 $$

Table of Sums $$ \begin{array}{c|c} k&\sum\limits_{n=1}^\infty\frac{n^{n-k}}{e^nn!}\\\hline 1&1\\ 2&\frac12\\ 3&\frac5{12}\\ 4&\frac7{18}\\ 5&\frac{1631}{4320}\\ 6&\frac{96547}{259200}\\ 7&\frac{40291823}{108864000}\\ 8&\frac{16870575007}{45722880000} \end{array}\tag{10} $$

Recursion for the Coefficients of $\boldsymbol{P_k}$

Let $$ P_k(x)=\sum_{j=1}^\infty(-1)^{j-1}a_{k,j}x^j\tag{11} $$ where $a_{k,1}=1$ and $a_{k,j}=0$ for $j\gt k$. Applying $(7)$ to $(11)$ gives $$ \begin{align} a_{k,j} &=\frac{a_{k-1,j}+a_{k-1,j-1}}j\tag{12}\\ &=\frac1{j^k}\sum_{i=j-1}^{k-1}j^ia_{i,j-1}\tag{13} \end{align} $$ $(13)$ follows from $(12)$ after unrolling the recursion.

Properties of the Coefficients

We will show that for some $b_{j,n}$, $$ a_{k,j}=\sum_{n=1}^j(-1)^{n-1}b_{j,n}\left(\frac1n\right)^k\tag{14} $$ Since $a_{k,1}=1$, $(14)$ is true for $j=1$ with $b_{1,1}=1$ and $b_{1,n}=0$ for $n\gt1$.

Suppose that $(14)$ is true for $j-1$. Applying $(13)$ to $(14)$ yields $$ \begin{align} a_{k,j} &=\frac1{j^k}\sum_{i=j-1}^{k-1}j^ia_{i,j-1}\\ &=\frac1{j^k}\sum_{i=j-1}^{k-1}\sum_{n=1}^{j-1}(-1)^{n-1}b_{j-1,n}\left(\frac jn\right)^i\\ &=\frac1{j^k}\sum_{n=1}^{j-1}(-1)^{n-1}b_{j-1,n}\frac{\left(\frac jn\right)^k-\left(\frac jn\right)^{j-1}}{\frac jn-1}\\ &=\sum_{n=1}^{j-1}(-1)^{n-1}\underbrace{\,\frac{nb_{j-1,n}}{j-n}\vphantom{\sum_{n=1}^{j-1}}\,}_{b_{j,n}}\left(\frac1n\right)^k\underbrace{-\sum_{n=1}^{j-1}(-1)^{n-1}\frac{nb_{j-1,n}}{j-n}\left(\frac jn\right)^{j-1}}_{(-1)^{j-1}b_{j,j}}\left(\frac1j\right)^k\tag{15} \end{align} $$ which is of the form of $(14)$ with $$ b_{j,n}=\frac{nb_{j-1,n}}{j-n}\tag{16} $$ for $n\lt j$ and $$ b_{j,j}=-\sum_{n=1}^{j-1}(-1)^{j-n}b_{j,n}\left(\frac jn\right)^{j-1}\tag{17} $$ Thus, $(14)$ is true for $j$.

Computing $\boldsymbol{b_{j,n}}$

Equation $(14)$, $(16)$, and $(17)$ allow us to give formulas for $a_{k,j}$ for each $j$: $$ \begin{align} a_{k,1}&=1\vphantom{\left(\frac11\right)^k}\\ a_{k,2}&=1-2\left(\frac12\right)^k\\ a_{k,3}&=\frac12-4\left(\frac12\right)^k+\frac92\left(\frac13\right)^k\\ a_{k,4}&=\frac16-4\left(\frac12\right)^k+\frac{27}2\left(\frac13\right)^k-\frac{32}3\left(\frac14\right)^k\\ a_{k,5}&=\frac1{24}-\frac83\left(\frac12\right)^k+\frac{81}4\left(\frac13\right)^k-\frac{128}3\left(\frac14\right)^k+\frac{625}{24}\left(\frac15\right)^k\\ a_{k,6}&=\frac1{120}{-}\frac43\left(\frac12\right)^k{+}\frac{81}4\left(\frac13\right)^k{-}\frac{256}3\left(\frac14\right)^k{+}\frac{3125}{24}\left(\frac15\right)^k{-}\frac{324}5\left(\frac16\right)^k \end{align}\tag{18} $$ Looking at $b_{j,j}$ in $(18)$, a good guess appears to be $$ b_{j,j}=\frac{j^j}{j!}\tag{19} $$ Combining $(16)$ and $(19)$, we get $$ b_{j,n}=\binom{j}{n}\frac{n^j}{j!}\tag{20} $$ which satisfies $(16)$ and $(17)$, validating the guess made for $(19)$.

Computing $\boldsymbol{a_{k,j}}$

Putting together $(14)$ and $(20)$ gives $$ a_{k,j}=\sum_{n=1}^j(-1)^{n-1}\binom{j}{n}\frac{n^j}{j!}\left(\frac1n\right)^k\tag{21} $$ Note that for $j\gt k$, the sum in $(21)$ is an order $j$ difference of a degree $j-k$ polynomial, hence $a_{k,j}=0$, which shows that $(21)$ is valid even for $j\gt k$.

Simpler Formula for the Sums

Applying $(9)$ and $(11)$ to $(21)$ yields $$ \begin{align} \sum_{n=1}^\infty\frac{n^{n-k}}{e^nn!} &=\sum_{j=1}^k(-1)^{j-1}a_{k,j}\\ &=\bbox[5px,border:2px solid #C0A000]{\sum_{j=1}^k\sum_{n=1}^j(-1)^{j-n}\binom{j}{n}\frac{n^j}{j!}\left(\frac1n\right)^k}\tag{22} \end{align} $$ For each $k$, the sum in $(22)$ has $\frac{k^2+k}2$ terms. This is as close to a closed formula for the sums as I have found.

Verification of the Formula

As noted after equation $(21)$, the inner sum in $(22)$ for $j\gt k$ is $0$. That is, $$ \begin{align} \sum_{j=1}^k\sum_{n=1}^j(-1)^{j-n}\binom{j}{n}\frac{n^j}{j!}\left(\frac1n\right)^k &=\sum_{j=1}^\infty\sum_{n=1}^j(-1)^{j-n}\binom{j}{n}\frac{n^j}{j!}\left(\frac1n\right)^k\tag{23}\\ &=\sum_{n=1}^\infty\sum_{j=n}^\infty(-1)^{j-n}\frac1{n!}\frac{n^{j-k}}{(j-n)!}\tag{24}\\ &=\sum_{n=1}^\infty\sum_{j=0}^\infty(-1)^j\frac1{n!}\frac{n^{j+n-k}}{j!}\tag{25}\\ &=\sum_{n=1}^\infty\frac{n^{n-k}}{e^nn!}\tag{26} \end{align} $$ Explanation
$(23)$: extend the sum in $j$ since the inner sums vanish for $j\gt k$
$(24)$: switch order of summation and simplify the summand
$(25)$: substitute $j\mapsto j+n$
$(26)$: evaluate the sum in $j$

Solution 2:

For each $k \geq 1$ we define $T_k$ by

$$T_k(z) := \sum_{n\geq 1} \frac{n^{n-k}}{n!}z^n.$$

We make several observations.

1. $T_1(z) = -W(-z)$ from the Taylor series of the Lambert $W$-function, which is

   $$ W(z) = \sum_{n \geq 1} (-n)^{n-1} \frac{z^n}{n!}. $$

   In particular, we get

   $$T_1(we^{-w}) = w $$

   for all $w \leq 1$. As a special case, we get $T_1(e^{-1}) = 1$.

2. $T_k'(z) = T_{k-1}(z)/z$. In particular,

   $$ \frac{\mathrm{d}}{\mathrm{d}w} T_k(w e^{-w}) = \frac{1-w}{w}T_{k-1}(w e^{-w}). $$

From this, we can compute $T_2$ as follows:

\begin{align*} T_2(we^{-w}) = \int \frac{1-w}{w}T_{1}(w e^{-w}) \, \mathrm{d}w = w - \frac{w^2}{2}. \end{align*}

In particular,

$$ \sum_{n\geq 1} \frac{n^{n-2}}{n! e^n} = T_2(e^{-1}) = \frac{1}{2}. $$

A similar argument shows that each $T_k(we^{-w})$ is a degree $k$ polynomial over $\mathbb{Q}$ without constant term, which can be computed recursively in $k$. For instance, we have

$$ \begin{array}{|c|ccccccc|} \hline k & 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ \hline T_k(e^{-1}) & 1 & \dfrac{1}{2} & \dfrac{5}{12} & \dfrac{7}{18} & \dfrac{1631}{4320} & \dfrac{96547}{259200} & \dfrac{40291823}{108864000} \\ \hline \end{array} $$

Addendum - closed form of $P_n$.

As above, let $P_n$ be the polynomial such that $T_n(z) = P_n(T_1(z))$. Then we claim that the following generating function identity holds.

$$ \sum_{n=1}^{\infty} P_n(z)t^n = - \sum_{n=1}^{\infty} \prod_{i=1}^{n} \frac{tz}{t-i}. \tag{*} $$

Once we prove this, we can find the coefficient of $z^k$ in $P_n(z)$ as

$$ [z^k] P_n(z) = - [t^n] \frac{t^k}{(t-1)(t-2)\cdots(t-k)} = \frac{1}{k!} \sum_{j=1}^{k} (-1)^{k-j} \binom{k}{j} \frac{1}{j^{n-k}}. $$

Consequently, we get

$$ P_n(z) = \sum_{k=1}^{n} \Bigg( \sum_{j=1}^{k} (-1)^{k-j} \binom{k}{j} \frac{1}{j^{n-k}} \Bigg) \frac{z^k}{k!}. $$

We conclude with the proof of $\text{(*)}$.

Proof of $\text{(*)}$. Using partial fraction decomposition, we find that

\begin{align*} - \frac{t^k}{(t-1)\cdots(t-k)} &= -1 - \sum_{j=1}^{k} (-1)^{k-j} \frac{j^k}{(j-1)!(k-j)!} \frac{1}{t-j} \\ &= -1 + \sum_{j=1}^{k} \frac{(-1)^{k-j}}{j!(k-j)!} j^k \sum_{n=0}^{\infty} \frac{t^n}{j^n}. \end{align*}

Multiplying $z^k$ and summing over $k = 1, 2, \cdots$, we get

\begin{align*} - \sum_{k=1}^{\infty} \frac{t^k z^k}{(t-1)\cdots(t-k)} &= -\frac{z}{1-z} + \sum_{k=1}^{\infty} z^k \sum_{j=1}^{k} \frac{(-1)^{k-j}}{j!(k-j)!} j^k \sum_{n=0}^{\infty} \frac{t^n}{j^n} \\ &= -\frac{z}{1-z} + \sum_{n=0}^{\infty} \sum_{j=1}^{\infty} \frac{t^n}{j! j^n} \sum_{k=j}^{\infty} z^k \frac{(-1)^{k-j}}{(k-j)!} j^k \\ \\ &= -\frac{z}{1-z} + \sum_{n=0}^{\infty} \sum_{j=1}^{\infty} \frac{t^n}{j!} j^{j-n} (ze^{-z})^j \\ &= -\frac{z}{1-z} + \sum_{n=0}^{\infty} T_n(ze^{-z}) t^n. \end{align*}

Now the desired equality follows by noting that

$$ T_0(ze^{-z}) = \frac{z}{1-z} \qquad \text{and} \qquad T_n(ze^{-z}) = P_n(z) $$

for $n \geq 1$.