# Math contest: Find number of roots of $F(x)=\frac{n}{2}$ involving a strange integral.

Edit summary: A good answer appeared. CW full answer added, based on given answers. Removing my ugly-looking attempts, as they still remain in the rev. history.

Here's a final-round calculus contest problem in our district in 2009. Test paper isn't available online. I originally proved $F(n/2)<n/2$ but failed to prove $F(n)>n/2$ and the monotonicity of $F(n)$.

Define $$F(x)=\int\limits_0^x \mathrm e^{-t} \left(1+t+\frac{t^2}{2!}+\cdots+\frac{t^n}{n!}\right) \mathrm d t$$ where $n>1, n \in \mathbb N^+$; and an equation: $\displaystyle F(x)=\frac{n}{2}$.

Find the number of roots of this equation within the interval $\displaystyle I=\left(\frac{n}{2},n\right)$.

Tedious Previous Attempts Removed.

-

2
People, please take your time, I regret to say that I should've fallen asleep by now. Thanks again! – FrenzY DT. Oct 21 '12 at 15:00

2
Is the fact that $F'(x)=e^{-x} (1+x+\cdots +\frac{x^{n}}{n!})$ of any use? – dado Oct 21 '12 at 15:15
@dado I just understood what you meant. Exactly! (I thought you were asking if $F(x)$ were of any use. – FrenzY DT. Oct 26 '12 at 2:18

## 3 Answers

### Proving $\displaystyle F(n)>\frac{n}{2}$:

Looks like you've made the life far more complicated than needed. For $t>0$, write $$(1-\frac tn)e^t=\sum_{k\ge 0}\frac 1{k!}(1-\frac kn)t^k<\sum_{k=0}^n \frac{t^k}{k!}$$ (drop the negative coefficients and increase the rest). Rewrite this as $$e^{-t}\sum_{k=0}^n \frac{t^k}{k!}> 1-\frac tn.$$ Now, I hope even a dumb calculus student can integrate the right hand side from $0$ to $n$.

-
How did you foresee this? I never have envisaged that infinite series. Please offer some advice. – FrenzY DT. Oct 24 '12 at 2:28

1
I just know only a few decent functions whose integral from $0$ to $n$ is $n/2$. The constant $1/2$ did not seem to work, so I took the next simplest one, which is linear. Of course, to multiply $e^{-t}$ and the partial sum is a nightmare but we can put the exponent on the other side and, since we want to compare with a (truncated) power series, it makes sense to expand the product $(1-\frac tn)e^t$ into a power series as well, which is not a big deal. The rest is pure luck. If it had failed, I would try something else, but since it worked, I stopped here. – fedja Oct 24 '12 at 2:36
(+1) and checkmarked, because this answer exploits series which is my weak point. – FrenzY DT. Oct 24 '12 at 3:04
Great answer. This gives a nice inequality for the incomplete gamma function. – Albert Steppi Oct 24 '12 at 15:01

### Proof that $\displaystyle F(\frac{n}{2})<\frac{n}{2}$

$$F(x)= \int\limits_0^x \mathrm e^{-t} \left(1+t+\frac{t^2}{2!}+\cdots+\frac{t^n}{n!}\right) \mathrm dt <\int\limits_0^x \mathrm e^{-t}\mathrm e^t\mathrm dt=x \,\,\Rightarrow\,\, F(\frac{n}{2})<\frac{n}{2}.$$

### Proof that $\displaystyle F(n)>\frac{n}{2}$

See accepted answer and comment.

$$(1-\frac tn)e^t = \sum_{k=0}^{+\infty}\frac 1{k!}\underbrace{(1-\frac kn)}_{\in(-\infty,1]}t^k<\sum_{k=0}^n \frac{t^k}{k!} \,\,\Rightarrow\,\, e^{-t}\sum_{k=0}^n \frac{t^k}{k!}> 1-\frac tn \,\,\Rightarrow\,\, F(n)> n-1 \ge \frac{n}{2}.$$

### Proof that $F(n)$ is monotonically increasing on $\displaystyle(\frac{n}{2},n)$

$$F^\prime(x) = \mathrm e^{-x} \sum\limits_{i=0}^n \frac{x^i}{i!} = \frac{\text{Power series with positive coefficients and $x>0$}}{\text{Exponentiation}} > 0.$$

Summing up the previous three proofs, OP's equation has only $1$ root on the interval $\displaystyle \left(\frac{n}{2},n\right)$. $\square$

-

You had the right idea, but this seems to be a fairly difficult problem. My solution depends upon a non-trivial result about the median of the gamma distribution. My answer is probably not that satisfying, since it seems unlikely that participants in a math contest would know this stuff off hand; It took me a fair amount of research to come up with this solution. Hopefully someone else will come up with a more elementary argument.

Edit: I've decided to offer a bounty on this question since I really want to see a simpler solution. I offer 100 points to anyone who is able to prove that $$\int_{0}^{n}e^{-t}\left(1 + t + {t^2\over 2!} + \ldots + {t^{n} \over n!}\right)dt > {n\over 2}$$ for all positive integers $n$, in a simpler manner more consistent with the spirit of a math competition. I know this is a somewhat subjective requirement, what I'm looking for is an argument a bright first year calculus student could come up with without access to the internet or other research materials.

My Solution:

It was a good idea to define $G(x)=F(x)-{n \over 2}$. We can use the Fundamental Theorem of Calculus to compute the derivative of $G(x)$. This yields $$G^{'}(x)=e^{-x}(1+x+{x^2 \over 2!}+{x^3 \over 3!}+\ldots + {x^n \over n!})$$ Claim: $G^{'}(x) > 0$ $\forall x \in [{n \over 2}, n]$

Proof

Since $e^{-x}$ is positive for all $x$, this depends on whether or not $$p_n(x) = 1 + x +\ldots + {x^n \over n!} > 0$$. Since we are dealing with the interval $[{n\over 2}, n]$ for positive $n$, all terms of this sum are positive for $x$ in our interval. Thus $p_n(x)>0$ for $x \in [{n \over 2}, n]$.

Thus we have shown that $G^{'}(x) > 0$ for $x \in [{n \over 2}, n]$. $\square$

This shows that $G(x)$ is monotonically increasing. Now we look at $G({n \over 2})$.

Claim: $G({n \over 2}) < 0$.

Proof.

Since $1 + x + \ldots + {x^n \over n!} < e^x$ for all positive $x \in \mathbb{R}$. $$G({n \over 2}) = \int_{0}^{{n \over 2}}e^{-t}(1 + t +\ldots + {t^n \over n!})dt - {n \over 2}$$

$$< \int_{0}^{{n \over 2}}e^{-t}e^{t}dt - {n \over 2} < {n \over 2} - {n \over 2} = 0$$

$\square$

Next we consider $G(n)$.

Claim: $G(n)>0$.

Proof.

This is the hard part

$$G(n) = \int_{0}^{n}e^{-t}p_n(t)dt - {n \over 2}$$

$$p_n(x) = e^{x} - R_n(x) = e^{x} - \int_{0}^{x}{e^{t} \over n!}(x-t)^ndt$$

where we have applied Taylor's formula with the Cauchy form for the remainder.

Hence

$$G(n) = \int_{0}^n\left(1 - e^{-t}\int_{0}^{t}{e^{u}\over n!}(t - u)^ndu\right) dt - {n\over 2}$$

$$= \int_{0}^n\left(1 - \int_{0}^{t}{e^{u-t}\over n!}(t - u)^ndu\right) dt - {n\over 2}$$

Making the change of variables $v = t - u$ in the inner integral we get $$G(n) = \int_{0}^n\left(1 - {1\over n!}\int_{0}^{t}e^{-v}v^ndv\right) dt - {n\over 2} = \int_{0}^{n}1 - {\gamma(n+1,t) \over n!}dt - {n \over 2}$$

Where $\gamma(s,x)$ is the lower incomplete gamma function. $\gamma(s,x)$ is complementary with $\Gamma(s,x)$, the upper incomplete gamma function. $\gamma(s,x) + \Gamma(s,x) = \Gamma(s)$, the standard gamma function. Applying this fact yields $$G(n) = {1\over n!}\int_{0}^{n}\Gamma(n+1,t)dt - {n \over 2}$$

Since $\Gamma(n+1,t)$ is a decreasing function in $t$ for fixed $n$ we have $$G(n) > n{\Gamma(n+1,n)\over n!} - {n \over 2}$$

The integral is greater than the minimum value of the integrand in the interval in question times the length of the interval.

Now let's take a look at the Gamma Distribution. In particular we want to consider the distribution $Gamma(n+1,1)$ which has cumulative distribution function $$f(x) = {\gamma(n+1,x) \over n!}.$$

Where $x \in (0,\infty)$.

Thus if $X$ is a random variable drawn from this distribution then $$P(X < x) = {\gamma(n+1,x) \over n!}$$ We also have $$P(X > x) = {\Gamma(n+1,x) \over n!}$$ Which follows from the complementary nature of the incomplete gamma functions.

According to this paper, the median $\nu$ of $Gamma(n+1,1)$ satisfies $$n + {2 \over 3} < \nu < n + \ln (2)$$.

In particular this tells us that $n$ is less than the median of the distribution. Thus

$${\Gamma(n+1,n) \over n!} = P(X > n) > {1 \over 2}$$

which tells us that $$G(n) > n{\Gamma(n+1,n) \over n!} - {n \over 2} > {n\over 2} - {n\over 2} = 0$$ $\square$

We have proven that $G(x)$ increases strictly monotonically on $[{n\over 2},n]$, that $G({n\over 2})$ < 0, and that $G(n) > 0$. Hence it follows that $G(x)$ has one and only root in this interval. Thus the equation $$F(x) = {n\over 2}$$ has one and only one root in $[{n\over 2}, n]$.

-

(+1) Thank you for showing me how to finish off the incomplete gamma function. I had also tried this path but stopped at the incomplete $\gamma$/$\Gamma$ function. I also found out that $G'(x)>0$ is extremely easy to prove because $\sum_{i=0}^n \frac{n^i}{i!}>0$ and $\exp\{\text{blah}\cdots\}>0$ when $x>0$. – FrenzY DT. Oct 22 '12 at 5:22
Let's try to find a more elementary solution w/o prob & stats because I can't rely on the median of gamma distribution during the alloted contest time. Hope you will understand. – FrenzY DT. Oct 22 '12 at 5:25
I appreciate your effort. Also that there is another good solution. – FrenzY DT. Oct 24 '12 at 3:05
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 76, "mathjax_display_tex": 25, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9465304017066956, "perplexity_flag": "head"}