Prove $(1 - a)^n \geq 1 - na$ for $0 < a < 1$

Question

This is exercise problem from "The Art of Computer Programming - Fundamental Algorithm".

Prove by induction that if $0 < a < 1$, then $(1 - a)^n \geq 1 - na$

Here is my attempt:

• If n = 1, then $1 - a \geq 1 - a$ is true.
• We may assume by induction that $(1 - a)^n \geq 1 - na$ holds, then $$(1 - a)^{2n} \geq (1 - na)^2 = 1 - 2na + n^2a^2\geq 1 -2na$$ so by induction, the property holds for any integer n.

---

Is my proof correct?

Answer 1

You should have written:

• if $n=0$, then $1 \geq 1$
• assume it holds for all $k \le n $, then we'll prove it for $n+1$ $$(1 - a)^n \geq 1 - na$$ $$(1-a)^{n+1} = (1 - a)^n \cdot (1-a) \geq (1 - na)(1 - a) = 1 - (n + 1)a + na^2 \geq 1-(n+1)a$$ so it holds for every $n \geq 0 \Rightarrow \forall n \in \Bbb{N}$

Answer 2

Since your induction step goes from $n$ to $2n$, your proof only shows that the result holds for $n= 1,2,4,8,16,\dots$. Usually, you'll want to go from $n$ to $n + 1$ in the induction step: We'll then have something like

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