18
$\begingroup$

What is known about $f(k)=\sum_{n=0}^{k-1} \frac{k^n}{n!}$ for large $k$?

Obviously it is is a partial sum of the series for $e^k$ -- but this partial sum doesn't reach close to $e^k$ itself because we're cutting off the series right at the largest terms. In the full series, the $(k+i-1)$th term is always at least as large as the $(k-i)$th term for $1\le i\le k$, so $f(k)< e^k/2$. Can we estimate more precisely how much smaller than $e^k$ the function is?

It would look very nice and pleasing if, say, $f(k)\sim e^{k-1}$ for large $k$, but I have no real evidence for that hypothesis.

(Inspired by this question and my answer thereto).

$\endgroup$
20
$\begingroup$

This appears as problem #96 in Donald J Newman's excellent book: A Problem Seminar.

The problem statement there is:

Show that

$$ 1 + \frac{n}{1!} + \frac{n^2}{2!} + \dots + \frac{n^n}{n!} \sim \frac{e^n}{2}$$

Where $a_n \sim b_n$ mean $\lim \frac{a_n}{b_n} = 1$.

Thus we can estimate your sum (I have swapped $n$ and $k$) as

$$ 1 + \frac{n}{1!} + \frac{n^2}{2!} + \dots + \frac{n^{n-1}}{(n-1)!} \sim \frac{e^n}{2}$$

as by Stirling's formula, $\dfrac{n^n}{n!e^n} \to 0$.

The solution in the book proceeds as follows:

The remainder term for a the Taylor Series of a function $f$ is

$$ R_n(x) = \int_{0}^{x} \frac{(x-t)^n}{n!} f^{n+1}(t) \ \text{d}t$$

which for our purposes, comes out as

$$\int_{0}^{n} \frac{(n-t)^n}{n!} e^t \ \text{d}t$$

Making the substitution $n-t = x$ gives us the integral

$$ \int_{0}^{n} \frac{x^n}{n!} e^{-x} \ \text{d}x$$

In an earlier problem (#94), he shows that

$$\int_{0}^{\infty} \left(1 + \frac{x}{n}\right)^n e^{-x} \ \text{d}x \sim \sqrt{\frac{\pi n}{2}}$$

which using the substitution $n+x = t$ gives

$$ \int_{n}^{\infty} t^n e^{-t} \ \text{d}t \sim \frac{n^n}{e^n} \sqrt{\frac{\pi n}{2}}$$

Using $\int_{0}^{\infty} x^n e^{-x}\ \text{d}x = n!$ and Stirling's formula now gives the result.

To prove that

$$\int_{0}^{\infty} \left(1 + \frac{x}{n}\right)^n e^{-x} \ \text{d}x \sim \sqrt{\frac{\pi n}{2}}$$

He first makes the substitution $x = \sqrt{n} t$ to obtain

$$ \int_{0}^{\infty} \left(1 + \frac{x}{n}\right)^n e^{-x} \ \text{d}x \ = \sqrt{n} \int_{0}^{\infty} \left(1 + \frac{t}{\sqrt{n}}\right)^n e^{-\sqrt{n} t} \ \text{d}t$$

Now $$\left(1 + \frac{t}{\sqrt{n}}\right)^n e^{-\sqrt{n} t} \le (1+t)e^{-t}$$ and thus by the dominated convergence theorem,

$$ \lim_{n\to \infty} \frac{1}{\sqrt{n}} \int_{0}^{\infty} \left(1 + \frac{x}{n}\right)^n e^{-x} \ \text{d}x $$

$$= \int_{0}^{\infty} \left(\lim_{n \to \infty}\left(1 + \frac{t}{\sqrt{n}}\right)^n e^{-\sqrt{n} t}\right) \ \text{d}t$$

$$ = \int_{0}^{\infty} e^{-t^2/2} \ \text{d}t = \sqrt{\frac{\pi}{2}} $$

$\endgroup$
16
$\begingroup$

$e^{-k} f(k) = P(X_k < k)$ where $X_k$ is a Poisson random variable with parameter $k$. Since the sum of $k$ independent Poisson random variables with parameter $1$ is Poisson with parameter $k$, the Central Limit Theorem says the probability distribution of $Z_k = (X_k - k)/\sqrt{k}$ approaches a standard normal distribution. Thus $P(X_k < k) = P(Z_k < 0) \to 1/2$ as $k \to \infty$.

$\endgroup$

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.