# How to find a meaningful bound on a sequence that is known to go to $0$

I am doing a programming exercise (quite an interesting one, actually) on the sequence $\{I_k\}_{k\in\Bbb{N}}$

$$I_k = \int_0^1 x^ke^{x-1} dx$$

and I am also given a - already proven by me - recurrence formula,

$$I_k = 1 - kI_{k-1}$$

and at some point I must show that the $I_k$ go to $0$. I was trying to do it just with the recurrence formula and the fact that $I_1 = \frac1e$, with induction. I tried proving $I_k < \frac{1}{k+1}$ but in proving it I ended up needing to assume that $\frac{1}{k+1} < I_{k-1}$. So basically I wanted to prove

$$\frac{1}{k+2} < I_k < \frac{1}{k+1} \tag{1}$$

I verified it for $k$ up to $10$ so it does feel like it should be true. With induction, proving $I_k < \frac{1}{k+1}$ assuming (1), is trivial. However, when I try to prove $\frac{1}{k+2} < I_k$ I end up with

$$I_{k-1} < \frac{1}{k}\frac{k+1}{k+2}$$

which made me write

$$I_{k-1} < \frac{1}{k}\frac{k+1}{k+2} < \frac{1}{k}, \text{true, by the induction hypothesis}$$

However, I can't do this. I know $I_{k-1}< \frac{1}{k}$ but that does not let me write what I wrote nor prove what I want to prove. Is there anyone out there able to lend me a hand?

The ideal would be to use induction to prove (1).

If I fail to do that, the second ideal thing would be to use induction to prove that the $I_k$, starting at some $k_0$, are bounded by something that does not increase. It can even be a constant. For example, showing $I_k < 1\ \forall k$ would be good enough for my purposes.

Also, if anyone knows if this sequence (or these integrals) has any name, I would be able to better search for things that could help.

• Wait, I'm lost. You want to prove $(1)$, am I correct? Also, hi, haven't seen you in a while :D And particularly, you are stuck on the lower bound? – Simply Beautiful Art Jun 4 '17 at 19:07
• @SimplyBeautifulArt hey :P You are correct, in my last paragraph I got a bit lost in my thoughts. I made it clearer now. Yes, I conjecture that the lower bound is indeed that, but I failed to prove it. – RGS Jun 4 '17 at 19:12
• @RSerrao Hint: $\,0 \lt x^k e^{x-1} \lt 1\,$ for $\,x \in (0,1)\,$. Then the recurrence gives the upper bound directly. – dxiv Jun 4 '17 at 19:13
• Well, using the recurrence relation you found, one may deduce that: $$I_k=\frac{k!}e\left[1-\frac1e\sum_{n=0}^k\frac1{n!}\right]$$ – Simply Beautiful Art Jun 4 '17 at 19:14
• @SimplyBeautifulArt Maybe, but $\,0 \lt I_{k-1} \lt 1/k\,$ is enough to prove convergence to $\,0\,$. – dxiv Jun 4 '17 at 19:16

## 3 Answers

(Expanding on my previously posted comments.)

I am also given a - already proven by me - recurrence formula,

$$I_k = 1 - kI_{k-1}$$

Once the recurrence relation is determined, the bounds follow directly from just the positivity of the integrand $\,x^k e^{x-1} \gt 0\,$ for $\,x \gt 0\,$, which immediately implies $\,I_k \gt 0\,$ for all $\forall k \in \mathbb{N}\,$. Therefore:

• $1 - kI_{k-1}=I_k \gt 0 \implies k I_{k-1} \lt 1 \implies I_{k-1} \lt \cfrac{1}{k} \quad\quad$

• then, $1 - kI_{k-1}=I_k \lt \cfrac{1}{k+1} \implies k I_{k-1} \gt 1 - \cfrac{1}{k+1}=\cfrac{k}{k+1}\implies I_{k-1} \gt \cfrac{1}{k+1}$

• Once you've got $0 < I_{k-1}< \dfrac 1 k,$ that's enough to prove that $I_k \to 0$ as $k\to\infty.$ If the goal was only to prove that, then you don't need the rest of what you've got here. – Michael Hardy Jun 4 '17 at 20:59
• @MichaelHardy Right, and that's a point I made in the comments. However, there was some discussion about what the question is really asking for, and the above attempts to cover the other interpretations, too. – dxiv Jun 4 '17 at 21:01
• I am accepting your answer because it is the one that uses the integral form of $I_k$ the less. Maybe I didn't make that clear enough on the question, but you addressed my issue the way I most wanted it to be addressed, using the recurrence relation to prove the bounds. – RGS Jun 5 '17 at 7:04

It is not clear to me whether the question suggests induction or requires it. If induction is merely suggested, then here is an answer which declines the suggestion!

Majorize via $$0 \le x^ke^{x-1} \le x^k\:\ \mbox{for all}\ x\in[0,1].$$ By this, we have that $$0 \le I_k = \int_0^1 x^k e^{x-1}\,dx \le \int_0^1 x^k \, dx = \frac 1 {k+1} \to 0 \text{ as } k\to\infty.$$ which I believe does what you want.

(This would fail, of course, if you needed $\sum_k I_k$ to be bounded—but that isn't a fault of the proof but rather of the series. In any case, you have not asked for boundedness in $\sum_k I_k$.)

• A professional engineer rather than a professional mathematician, I am not very handy with notation like $\forall x\in[0,1]$. An engineer would normally write $0 \le x \le 1$ and, if necessary, write "for all" out in words. If my notation is imperfect, corrections would be appreciated. – thb Jun 4 '17 at 19:48
• Write whatever is legible. If that means more words, so be it. I'd phrase it as "for all $x \in [0,1]$" or "for all $x$ with $0 \leq x \leq 1$", without really preferring one over the other; I tend to avoid the $\forall$ symbol except in formal logic, because it's just a bit less readable. – Patrick Stevens Jun 4 '17 at 21:05
• @thb : I would write this as follows: $$0 \le \int_0^1 x^k e^{x-1}\,dx \le \int_0^1 x^k \, dx = \frac 1 {k+1} \to 0 \text{ as } k\to\infty.$$ – Michael Hardy Jun 4 '17 at 21:08
• @thb : I wonder why you write $x^k e^{x-1} \le x^k e^1$ when you could just go with $x^k e^{x-1} \le x^k. \qquad$ – Michael Hardy Jun 4 '17 at 21:12
• @MichaelHardy: corrected, thanks. – thb Jun 4 '17 at 21:40

$$I_k = \int_0^1 x^ke^{x-1} \, dx$$

Directly from the integral:

$$\frac1{e} \lt e^{x-1} \lt 1$$ so $$\frac1{e(k+1)} \lt I_k \lt \frac1{k+1}.$$

Since $e^{x-1} > x$ (because $e^z > 1+z$), $I_k > \int_0^1 x^kx \,dx =\frac1{k+2}$. This is what you wanted.

Trying to be more precise:

Interpolating at $0$ and $1$, since $(e^{x-1})'' > 0$, $e^{x-1} \lt (1-\frac1{e})x+\frac1{e}$, so

\begin{align} I_k &\lt \int_0^1 x^k \left(\left(1-\frac1 e\right)x+\frac 1 e\right) \, dx\\ &=\left(1-\frac 1 e\right)\frac1{k+2}+\frac1{e(k+1)}\\ &=\frac1{k+2}+\frac1{e(k+1)(k+2)} \end{align}

so that $0 \lt I_k-\frac1{k+2} \lt \frac1{e(k+1)(k+2)}$.

Let $d(x) =(1-\frac1{e})x+\frac1{e}-e^{x-1} =(1-\frac1{e})x+\frac1{e}(1-e^{x})$. $d(0) = d(1) = 0$ and $d'(x) =(1-\frac1{e})-e^{x-1} =0$ when

\begin{align} x &=x_0\\ &=1+\ln(1-\frac1{e})\\ &=1+\ln(e-1)-1\\ &=\ln(e-1)\\ &\approx 0.54132\\ \end{align}

where $d(x_0) = \frac1{e}(2 - e + (e - 1) \ln(e - 1)) \approx 0.077941$.

Therefore $e^{x-1} \ge d(x)-d(x_0)$ so $I_k \ge \frac1{k+1}-(1-\frac1{e})\frac1{(k+1)(k+2)}-d(x_0)$.

That's enough for now.

• Thank you for your answer. I did enjoy the way you manipulated the integral to provide me with a lower bound, and in particular with the lower bound I could not prove. – RGS Jun 5 '17 at 7:01