Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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).

share|improve this question

2 Answers 2

up vote 12 down vote accepted

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}} $$

share|improve this answer

$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$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.