Show that $a_n \underset{(+\infty)}{\sim} n$ with $a_n$ solution of $e^{-x}\sum_{k=0}^{n}\frac{x^k}{k!}=\frac{1}{2}$

Question

Let $n$ be a natual and $f_n$ defined as: $$ f_n (x ) = e^{-x}\sum_{k=0}^{n}\frac{x^k}{k!} $$

Let $a_n$ be the unique positive solution of $f_n (x )=\frac{1}{2}$, I'm asked to show that $a_n \underset{(+\infty)}{\sim}n$. What I know is that $$ \lim\limits_{n \rightarrow +\infty} f_n (n ) = \lim\limits_{n \rightarrow +\infty} e^{-n}\sum_{k=0}^{n}\frac{n^k}{k!} = \lim\limits_{n \rightarrow +\infty}f_n (a_n ) = \frac{1}{2} $$ which makes the result intuitive. Because we have $f_n (n ) \underset{(+\infty)}{\sim}f_n (a_n )$ with $f_n$ only passing through $\frac{1}{2}$ once. However, I struggle to find how to use this to find that $a_n \underset{(+\infty)}{\sim}n$. Any hint would be appreciated.

Answer 1

Let $N_x$ denote a random variable having the Poisson distribution with rate $x$. Then

\begin{align*} f_n(x) = \mathbf{P}(N_x \leq n). \end{align*}

Moreover, by realizing the family $(N_x)_{x\geq 0}$ as a Poisson point process on $[0, \infty)$ with unit intensity, it follows that $f_n(x)$ is strictly decreasing in $x$. In light of this, it suffices to show:

Lemma. We have

1. $\lim_{n\to\infty} f_n(\alpha n) = 1$ for any $0 < \alpha < 1$, and
2. $\lim_{n\to\infty} f_n(\beta n) = 0$ for any $\beta > 1$.

Let's see why this implies the desired conclusion. Assuming the lemma, for any $0 < \alpha < 1 < \beta$, we have $f_n(\alpha n) > \frac{1}{2} > f_n(\beta n)$ and thus $\alpha n < a_n < \beta n$ for any sufficiently large $n$. So,

$$ \alpha \leq \liminf_{n\to\infty} \frac{a_n}{n} \leq \limsup_{n\to\infty} \frac{a_n}{n} \leq \beta $$

holds. However, both the above liminf and limsup are independent of the choice of $\alpha$ and $\beta$, hence the conclusion follows by letting $\alpha \uparrow 1$ and $\beta \downarrow 1$.

---

Proof of Lemma. By the central limit theorem, we know that $\frac{N_x - x}{\sqrt{x}}$ converges in distribution to a standard normal variable $Z \sim \mathcal{N}(0, 1)$. So, for any $t > 0$,

\begin{align*} f_n(t n) = \mathbf{P}(N_{t n} \leq n) = \mathbf{P}\left( \frac{N_{t n} - t n}{\sqrt{t n}} \leq C_t \sqrt{n} \right), \end{align*}

where $C_t = \frac{1}{\sqrt{t}} - \sqrt{t}$.

1. If $t < 1$, then $C_t > 0$ and hence $f_n(t n) \to \mathbf{P}(Z \leq \infty) = 1$.

2. If $t > 1$, then $C_t < 0$ and hence $f_n(t n) \to \mathbf{P}(Z \leq -\infty) = 0$.

This completes the proof of Lemma. $\square$

---

Remark. This argument can be quickly adapted to yield a stronger statement about the asymptotic behavior of $(a_n)$:

$$ a_n = n + o(\sqrt{n}) $$

Answer 2

Not a full answer but way to much for a comment :

Let $n$ be a natural number and $f_n$ defined as: $$ f_n\left(x\right) = e^{-x}\sum_{k=0}^{n}\frac{x^k}{k!} $$

Now clearly a truncated taylor series for $\exp(x)$ is less than $\exp(x)$ for $x>0$.

So

$$f_n(x) < 1$$ Taylor's theorem with error term gives us

$$\exp(x) = 1 + x + x^2/2! + ... + x^n/n! + R_n(x)$$

where for $x>0$ we get $0 < R_n(x) < \exp(x) \frac{x^{n+1}}{(n+1)!} $.

So we get for $x>0$ (using O-notation)

$$ f_n(x) < 1 = \exp(-x) \exp(x) = \frac{1 + x + x^2/2! + ...}{\exp(x)} + O(\frac{x^{n+1}}{(n+1)!})$$

We conclude

$$1 = \exp(-x) \exp(x) = f_n(x) + O(\frac{x^{n+1}}{(n+1)!})$$

If we can show that $f_n(n)$ is about equal to this $O(\frac{x^{n+1}}{(n+1)!})$

then both must equal about $1/2$ and thereby proving the conjecture.

---

We could do this in steps

1. show that $\int_1^{\infty} \frac{x^t}{t!} = \exp(x) + o(1)$.

2. show that $\int_1^{n} \frac{x^t}{t!} = \exp(x) - \frac{x^{n+1}}{(n+1)!} + o(1)$

however that seems like a hard or long way ; those integrals have no closed forms, so we need truncated series or asymptotics again or something clever.

---

We reconsider the problem

$$1 = f_n(x) + \frac{R_n(x)}{\exp(x)}$$

And we notice $R_n(x) = \sum_{k>n} \frac{x^{k+1}}{(k+1)!}$.

We use Stirling's approximation for $x^v/v!$ ;

$$\frac{x^v}{\sqrt{2 \pi v} (v/e)^v}$$

So we get

$$\frac{R_n(x)}{\exp(x)} = \sum_{k>n} \frac{x^{k+1}}{\sqrt{2 \pi (k+1)} (k+1)^{k+1}}$$.

We simply further

$$\frac{R_n(x)}{\exp(x)} = \sum_{k>n} \frac{(x/(k+1))^{k+1}}{\sqrt{2 \pi (k+1)}}$$.

Now for $n$ close to $x$ and close to the first $k$ value $> n$ we have

$$ \sum_{k>n} \frac{(n/(k+1))^{k+1}}{\sqrt{2 \pi (k+1)}} < \sum_{k=n+1}^{n+3} \frac{1}{\sqrt{2 \pi (k+1)}}$$. What seems to go to small values as $n$ increases ?

Therefore I believe that actually $f_n(n) > \frac{1}{2}$, but it might be that "somewhere around" $p = n$ we might have $f_n(p) = 1/2$

I believe my approximation is good enough to conclude that.

I want to point out that

$$(1 + x/v)^v$$ is close to $\exp(x)$ for large $v$.

When $v = x$ however

$$(1+1)^v = 2^v$$

, pretty far from the exponential function.

I think the polynomial of degree $v$ for $(1+x/v)^v$ is comparable to the taylor polynomial of degree $v$ so that the taylor polynomial of degree $n = x$ for $\exp(x)$ is also closer to $2^x$ than to the exponential.

I think an analogue thing is happening here.

Ofcourse one can put in more effort and use better approximations and methods but I think the conclusion remains the same.

Maybe this answer contains a mistake or the approximations are not sharp enough, but I do not think so.

---

EDIT

If I understand the other answers correctly, I made a mistake.

However I think it is valid to say I have shown that $a_n / n$ tends to $1$.

This should follow from say $a_n / n = 2$ or $1/2$ then

$ \sum_{k>n} \frac{( 2 n/(k+1))^{k+1}}{\sqrt{2 \pi (k+1)}} = \sum_{k>n} \frac{2^{k+1} (n/(k+1))^{k+1}}{\sqrt{2 \pi (k+1)}} $ what clearly goes to infinity.

or

$ \sum_{k>n} \frac{( (1/2) n/(k+1))^{k+1}}{\sqrt{2 \pi (k+1)}} = \sum_{k>n} \frac{(1/2)^{k+1} (n/(k+1))^{k+1}}{\sqrt{2 \pi (k+1)}} $ what clearly goes to zero.

so $ n/2 < a_n < 2 n $.

I am uncertain if I can improve it alot without using the methods of other answers.