Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
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? –  user39280 Oct 21 '12 at 15:15
    
Which district was this? –  Ayesha Mar 31 at 20:22
    
@ayesha Beijing, P.R.C. –  FrenzY DT. Apr 1 at 1:39
    
I really like this problem - do you know where I might find more of these? –  Ayesha Jun 28 at 18:50
add comment

3 Answers

up vote 17 down vote accepted
+100

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

share|improve this answer
    
How did you foresee this? I never have envisaged that infinite series. Please offer some advice. –  FrenzY DT. Oct 24 '12 at 2:28
2  
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
add comment

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$

share|improve this answer
add comment

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

share|improve this answer
    
(+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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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