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

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

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

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$