Recurrence and Numerical Stability for the Integral of x^n e^x
Define $I(n) = \int_0^1 x^n e^x \, dx, \quad n = 0, 1, 2, \ldots$
- Derive a recurrence relating $I(n)$ to $I(n-1)$.
- How does $I(n)$ behave as $n$ grows large?
- Suppose you compute $I(n)$ numerically by iterating the recurrence forward, starting from the exact value $I(0)$. How will the computed values compare to the true values as $n$ increases, and why?
Hints
- Integration by parts on $\int_0^1 x^n e^x dx$ gives a one-term recurrence. Keep $e^x$ as the part you integrate.
- Bound $e^x$ between $ and $e$ on $[0,1]$ to see that $I(n)$ decays like/n$. Then track how a small error in $I(n-1)$ feeds into $I(n)$.
- Write $\varepsilon_n = -n\,\varepsilon_{n-1}$ for the error. After $n$ steps the error is multiplied by $n!$ -- the forward recurrence is unstable. Running it backward divides errors by $n$ and is stable.
Worked Solution
How to Think About It: First get the recurrence with one integration by parts -- the $e^x$ stays put while the power on $x$ drops by one. Then think about size: on $[0,1]$ the factor $x^n$ is squashed toward zero everywhere except near $x=1$, so $I(n)$ must shrink toward $0$ as $n$ grows. The subtle part is the numerical question: the forward recurrence has a subtraction in it, and subtracting two comparable numbers to get a tiny result is exactly where floating-point error explodes.
Derivation of the recurrence: Integrate by parts with $u = x^n$, $dv = e^x dx$: $I(n) = \left[ x^n e^x \right]_0^1 - \int_0^1 n x^{n-1} e^x \, dx = e - n\, I(n-1).$ So $\boxed{I(n) = e - n\, I(n-1)}, \qquad I(0) = \int_0^1 e^x dx = e - 1.$
Size of $I(n)$: On $[0,1]$ we have
\le e^x \le e$, so $\frac{1}{n+1} = \int_0^1 x^n dx \le I(n) \le e \int_0^1 x^n dx = \frac{e}{n+1}.$ Thus $I(n) \to 0$ like/n$. More precisely, the mass concentrates near $x=1$ where $e^x \approx e$, giving $I(n) \approx e/(n+1)$ for large $n$.Numerical stability (the real point): Look at how an error propagates. If $\hat I(n-1) = I(n-1) + \varepsilon_{n-1}$, then $\hat I(n) = e - n\,\hat I(n-1) = I(n) - n\,\varepsilon_{n-1},$ so $\varepsilon_n = -n\,\varepsilon_{n-1}$, which means $|\varepsilon_n| = n!\,|\varepsilon_0|$. A tiny rounding error in $I(0)$ (or in $e$) is multiplied by $n!$ after $n$ steps. Meanwhile the true value is shrinking like
/n$. The relative error therefore blows up super-exponentially: after roughly a dozen steps the computed $I(n)$ is pure noise (and will even go negative, which is impossible for a positive integrand).The fix: Run the recurrence backward. Solving for $I(n-1) = (e - I(n))/n$ contracts errors by a factor
/n$ each step. Start from a crude guess for some large $N$ (e.g. $I(N) \approx e/(N+1)$, or even $0$) and iterate down; the result rapidly converges to the true values.Answer: $I(n) = e - n\,I(n-1)$ with $I(0) = e-1$; $I(n) \to 0$ like $e/(n+1)$. Forward iteration is numerically unstable -- errors grow like $n!$ while the answer shrinks, so the computed values diverge from the truth (eventually going negative). Iterating the recurrence backward is stable.
Intuition
This is a classic numerical-analysis cautionary tale dressed up as a calculus question. The math identity $I(n) = e - n\,I(n-1)$ is exact and looks harmless, but the multiplier $n$ in front of the previous term acts as an error amplifier. Whenever a recurrence multiplies the propagated quantity by something larger than
$, rounding error compounds; here it compounds factorially. The deeper lesson is direction: the same recurrence that is catastrophically unstable forward is beautifully stable backward, because the amplification factor inverts to/n < 1$.For an HFT firm this is not academic. Filters, recursive estimators, and PnL accumulators all run recurrences over millions of steps. A scheme that quietly amplifies floating-point error by even a small factor per step will produce garbage downstream, and the failure is silent until your numbers go obviously wrong (like a positive quantity turning negative). Knowing to check the error-propagation factor -- and to reverse the recursion when it exceeds
$ -- is exactly the numerical maturity they are probing for.