TAOCP 1.2.3 Exercise 27

We proceed by induction on $n$.

taocpmathematicsalgorithmsvolume-1math-medium

Section 1.2.3: Sums and Products

Exercise 27. [M20] Generalize the result of exercise 1.2.1–9 by proving that

$$\prod_{j=1}^n (1 - a_j) \ge 1 - \sum_{j=1}^n a_j,$$

assuming that $0 < a_j < 1$.

Verified: yes
Solve time: 41s

Solution

We proceed by induction on $n$.

Base case ($n = 1$): We have

$\prod_{j=1}^1 (1 - a_j) = 1 - a_1,$

and

$1 - \sum_{j=1}^1 a_j = 1 - a_1.$

Thus

$\prod_{j=1}^1 (1 - a_j) = 1 - \sum_{j=1}^1 a_j,$

so the inequality holds with equality.

Induction hypothesis: Assume that for some $n \ge 1$

$\prod_{j=1}^n (1 - a_j) \ge 1 - \sum_{j=1}^n a_j.$

Induction step ($n \to n+1$): Consider

$\prod_{j=1}^{n+1} (1 - a_j) = \left( \prod_{j=1}^{n} (1 - a_j) \right) (1 - a_{n+1}).$

By the induction hypothesis,

$\prod_{j=1}^{n} (1 - a_j) \ge 1 - \sum_{j=1}^{n} a_j.$

Since $0 < a_{n+1} < 1$, we multiply both sides by $1 - a_{n+1} > 0$ to obtain

$\prod_{j=1}^{n+1} (1 - a_j) \ge \left(1 - \sum_{j=1}^{n} a_j \right)(1 - a_{n+1}).$

Expanding the right-hand side yields

$\left(1 - \sum_{j=1}^{n} a_j \right)(1 - a_{n+1}) = 1 - \sum_{j=1}^{n} a_j - a_{n+1} + \left(\sum_{j=1}^{n} a_j\right) a_{n+1} = 1 - \sum_{j=1}^{n+1} a_j + \sum_{j=1}^{n} a_j a_{n+1}.$

Since $a_j a_{n+1} > 0$ for each $j$, it follows that

$1 - \sum_{j=1}^{n+1} a_j + \sum_{j=1}^{n} a_j a_{n+1} \ge 1 - \sum_{j=1}^{n+1} a_j.$

Combining these inequalities, we obtain

$\prod_{j=1}^{n+1} (1 - a_j) \ge 1 - \sum_{j=1}^{n+1} a_j.$

This completes the induction step.

By the principle of mathematical induction, the inequality

$\prod_{j=1}^n (1 - a_j) \ge 1 - \sum_{j=1}^n a_j$

holds for all $n \ge 1$ when $0 < a_j < 1$. ∎