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

22
+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$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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