25
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ Is the fact that $F'(x)=e^{-x} (1+x+\cdots +\frac{x^{n}}{n!})$ of any use? $\endgroup$
    – user39280
    Oct 21, 2012 at 15:15
  • $\begingroup$ Which district was this? $\endgroup$
    – Ayesha
    Mar 31, 2014 at 20:22
  • $\begingroup$ @ayesha Beijing, P.R.C. $\endgroup$
    – Frenzy Li
    Apr 1, 2014 at 1:39

4 Answers 4

23
+100
$\begingroup$

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

$\endgroup$
4
  • $\begingroup$ How did you foresee this? I never have envisaged that infinite series. Please offer some advice. $\endgroup$
    – Frenzy Li
    Oct 24, 2012 at 2:28
  • 4
    $\begingroup$ 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. $\endgroup$
    – fedja
    Oct 24, 2012 at 2:36
  • $\begingroup$ (+1) and checkmarked, because this answer exploits series which is my weak point. $\endgroup$
    – Frenzy Li
    Oct 24, 2012 at 3:04
  • 1
    $\begingroup$ Great answer. This gives a nice inequality for the incomplete gamma function. $\endgroup$ Oct 24, 2012 at 15:01
7
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ (+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$. $\endgroup$
    – Frenzy Li
    Oct 22, 2012 at 5:22
  • $\begingroup$ 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. $\endgroup$
    – Frenzy Li
    Oct 22, 2012 at 5:25
  • $\begingroup$ I appreciate your effort. Also that there is another good solution. $\endgroup$
    – Frenzy Li
    Oct 24, 2012 at 3:05
2
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

Another way to show this result could be the one using integration by parts: it is indeed an easy computation (using integration by parts) the one which leads to $$F(n) = n(1-e^{-n})-e^{-n}\sum_{j=1}^n\frac{n^j}{j!}.$$ I've written it in this way so that you can imagine how to get this result. Now let me use that $$\sum_{j=1}^n\frac{n^j}{j!}=e^n-\sum_{j=n+1}^{+\infty}\frac{n^j}{j!}$$ so that we can substitute it in the previous expression to get $$F(n) = n(1-e^{-n}) - 1 + \sum_{j=n+1}^{+\infty}\frac{n^j}{j!}>n(1-e^{-n}) - 1.$$ Thus finally $$F(n)-\frac{n}{2}>n\biggl(\frac{1}{2}-e^{-n}\biggr)-1$$ If $n\geq 4$ we get $$F(n)-\frac{n}{2} > \frac{n}{4}-1\geq 0$$ The other cases can be checked directly, moreover from these computations you can also deduce monotonicity of F(n).

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .