Proof of a result in numerical analysis, error bound.

Question

I would like to proove the Lemma 3.1. in this book.

My attempt... I want to split the lemma into several parts.

Part 1:

$$\prod_{j=1}^{n} (1 + \epsilon_j) = 1 + \sum_{j=1}^n \epsilon_j + O(|u|) = 1 + \theta_n,$$ where $$\theta_n = \sum_{j=1}^n \epsilon_j + O(|u|).$$

For the bound i observe that

$$1 + \theta_n = \prod_{j=1}^n (1 + \epsilon_j) \leq (1 + |u|)^n = \sum_{j=0}^n {n \choose j} |u|^j = 1 + \sum_{j=1}^n {n \choose j} |u|^j \leq 1 +\sum_{j=1}^n n^j|u|^j $$ $$ \leq 1 + \sum_{j=1}^{+\infty}(n|u|)^j = 1 + n|u| \sum_{j=0}^{+\infty}(n|u|)^j = 1 + \frac{n|u|}{1 - n|u|} \Rightarrow \theta_n \leq \frac{n|u|}{1 - n|u|}$$

(I assumed implicitly that $n|u| < 1$ )

Part 2:

I would like to prove that

$$\prod_{j=1}^{n} (1 + \epsilon_j)^{-1} = 1 + \theta_n',$$

but I'm not sure how to do that since I would be tempted to use the Taylor expansion instead of binomial expansion, but I wonder if there's an easier way to do that.

Part 3:

Combine part 1 and part 2 using algebraic manipulation to achieve the result of the lemma (assuming I've understood the part 2 it should be easy... maybe).

Any clue on part 2?

Answer 1

That might help: From

$$\prod_{j=1}^{n} (1 + \epsilon_j)^{-1} = 1 + \theta_n',$$

you get

$$\prod_{j=1}^{n} (1 + \epsilon_j) = \frac{1}{1 + \theta_n'}$$

so from the previous part

$$\frac{1}{1 + \theta_n'}-1\leq \frac{n|u|}{1-n|u|}$$

Answer 2

By Newton's binomial theorem: \begin{align} &1+\theta_n'=\prod_{j=1}^{n} (1 + \epsilon_j)^{-1} \leq (1 -|u|)^{-n} = 1+ \sum_{k=1}^\infty {-n \choose k} (-1)^k |u|^k \\ = & 1+ \sum_{k=1}^\infty {n+k-1 \choose k} |u|^k \\ \leq & 1+ \sum_{k=1}^\infty n^k |u|^k = 1+\frac{n|u|}{1-n|u|}, \end{align} because \begin{align} &{n+k-1 \choose k} \leq n^k \\ \iff & (n+k-1)! \leq n^k \cdot k! (n-1)!\\ \iff & (n+k-1)(n+k-2)\ldots (n+1)n \leq n^k \cdot k!. \end{align} Thus, $\theta_n' \leq \frac{n|u|}{1-n|u|}$, from which and part 1 you can obtain Lemma 3.1.