# A series problem by Knuth

I came across the following problem, known as Knuth's Series which originally was an American Mathematical Monthly problem.

Prove that $$\sum_{n=1}^\infty \left(\frac{n^n}{n!e^n}-\frac{1}{\sqrt{2\pi n}}\right)=-\frac{2}{3}-\frac{\zeta\left(\frac{1}{2}\right)}{\sqrt{2\pi}}.$$

It seems interesting. We are trying to compute a particular sum of the error term in Stirlings approximation. The immediate simple approaches don't seem to work.

Attempt: Why $\zeta\left(\frac{1}{2}\right)$: By partial summation we know that $$\sum_{n=1}^M \frac{1}{n^s}= \frac{M^{1-s}}{1-s}+\zeta(s)+O\left(M^{-s}\right)$$ for $s>0$, $s\neq 1$. This tells us where the $\frac{\zeta\left(\frac{1}{2}\right)}{\sqrt{2\pi}}$ comes from since

$$\sum_{n=1}^M \frac{1}{\sqrt{2\pi n}}=\sqrt{\frac{2M}{\pi}}+\frac{\zeta\left(\frac{1}{2}\right)}{\sqrt{2\pi}}+o(1).$$

Now all that remains is to prove that $$\sum_{n=1}^M \frac{n^n}{n!e^n}=\sqrt{\frac{2M}{\pi}} -\frac{2}{3}+o(1).$$

I am kinda stuck here, as this series seems strange to deal with. Thanks!

-
Did you mean $\sum_{n=1}^M \frac{1}{n^s}= \frac{M^{1-s}}{1-s}+\zeta(s)+O\left(M^{-s}\right)$ by any chance? =) –  Patrick Da Silva Aug 29 '11 at 15:36
@Patrick Da Silva: Indeed! Switched the $n$ and $M$ by accident –  Eric Naslund Aug 29 '11 at 15:37

Here is a series of hints to summarise the approach that appeared in the American Math Monthly. I have divided them by horizontal bars so hopefully it can ensure you only read one at a time. Unfortunately, this particular solution does not appear to be very general.

Prove the following separately first: $$\sum_{k=1}^{\infty} \biggl( \frac{k^k}{k!e^k} - \frac{ (1/2)_{k-1} }{\sqrt{2} (k-1)!} \biggr) = \frac{-2}{3}$$ $$\sum_{k=1}^{\infty} \biggl( \frac{1}{\sqrt{2\pi k}} - \frac{ (1/2)_{k-1} }{\sqrt{2} (k-1)!} \biggr) = \frac{ \zeta (1/2) }{\sqrt{2\pi}}$$ where the rising factorial is defined: $(a)_0 = 1 \mbox{ and } (a)_m = a(a+1)(a+2) \cdots (a+m-1)$

Abel's theorem comes in handy: If $\sum_{k=0}^{\infty} a_k$ converges, then $$\sum_{k=0}^{\infty} a_k = \lim_{x\to 1^{-} } \sum_{k=0}^{\infty} a_k x^k$$

Some power series (both for $|z| < 1$) : $$\mathrm{W}(z) = \sum_{k=1}^{\infty} \frac{k^{k-1} z^k}{k!e^k}$$ $$\sum_{k=1}^{\infty} \frac{ (1/2)_{k-1} }{(k-1)!} z^{k-1} = \frac{1}{\sqrt{1-z}}$$ where $\mathrm{W}(z)$ satisfies $\mathrm{W} \exp(-\mathrm{W}) = z/e$ (See Lambert W Function), and the second series comes from Newton's Binomial Expansion.

-
Seeing the $n^n$ factor in the given series made me suspect Lambert will somehow be turning up. Nice! –  Ｊ. Ｍ. Aug 29 '11 at 15:52
It seems this identity $W(z)=W\exp(-W)$ is the key to solving the problem. Also, originally I had hoped to use the fact that $$\binom{2n}{n}/4^n \sim \frac{1}{\sqrt{2\pi n}},$$ and it seems exactly this fact was used here, as $\frac{1}{\sqrt{1-z}}$ is the generating series for the above coefficients. (I guess the coefficients you have above are really just central binomial coefficients in disguise.) –  Eric Naslund Aug 29 '11 at 17:56