TAOCP 1.2.1 Exercise 9

Exercise 9. [20] Prove by induction that if $0 < a < 1$, then $(1 - a)^n \ge 1 - na$.

Verified: yes
Solve time: 1m28s

We prove by induction on $n$.

For the base case $n=1$,

$$ (1-a)^1 = 1-a = 1-1\cdot a, $$

so the statement is true.

Now assume that for some integer $n \ge 1$,

$$ (1-a)^n \ge 1-na. $$

This is the induction hypothesis.

We must show that

$$ (1-a)^{n+1} \ge 1-(n+1)a. $$

Starting from the left-hand side,

$$ (1-a)^{n+1}=(1-a)^n(1-a). $$

By the induction hypothesis,

$$ (1-a)^{n+1} \ge (1-na)(1-a). $$

Expanding the product gives

$$ (1-na)(1-a)=1-a-na+n a^2. $$

Combining terms,

$$ 1-a-na+n a^2 = 1-(n+1)a+n a^2. $$

Since $0<a<1$, we have $a^2>0$, hence

$$ n a^2 \ge 0. $$

Therefore,

$$ 1-(n+1)a+n a^2 \ge 1-(n+1)a. $$

It follows that

$$ (1-a)^{n+1} \ge 1-(n+1)a. $$

Thus, by induction,

$$ (1-a)^n \ge 1-na $$

for all integers $n \ge 1$.