Proving Inequalities by Induction

Inequality statements behave a little differently from equalities in an induction proof: instead of simplifying both sides down to a single algebraic identity, the inductive step usually chains together the inductive hypothesis with one or more auxiliary true inequalities (such as $2k \ge k+1$ for $k \ge 1$, or $x^2 \ge 0$ for real $x$) to reach the required conclusion for $k+1$.

The general pattern. To prove an inequality $P(n)$ of the form $L(n) \ (\ge \text{ or } >)\ R(n)$ by induction: (i) verify $P(n_0)$ directly at the smallest value $n_0$ where the statement is claimed to hold (often, but not always, $n_0=1$); (ii) assume $P(k)$: $L(k) \ (\ge\text{ or }>)\ R(k)$ for some $k \ge n_0$; (iii) build a chain of inequalities starting from $L(k+1)$, using the inductive hypothesis at some point in the chain, and ending at $R(k+1)$.

Worked illustration. To prove $2^n > n$ for all $n \ge 1$: the base case $n=1$ gives $2^1=2 > 1$, true. Assuming $2^k > k$, we get $2^{k+1} = 2\cdot 2^k > 2k$; and since $k \ge 1$ gives $2k \ge k+1$, chaining the two gives $2^{k+1} > 2k \ge k+1$, i.e. $2^{k+1} > k+1$, which is $P(k+1)$.

When the base case is not $n=1$. Some inequalities are simply false for small $n$ and only become true from some larger starting value $n_0$ onward -- for instance $2^n > n^2$ fails at $n=2,3,4$ (since $4=2^2$, $8<9$, $16=16$) but holds for every $n \ge 5$. In such cases the base case of the induction is taken at $n_0=5$ rather than at $n=1$: you verify $P(5)$ directly, and then prove $P(k) \Rightarrow P(k+1)$ only for $k \ge 5$. The conclusion is then that $P(n)$ holds for all $n \ge 5$, not for all natural numbers $n$ -- induction proves the statement true from wherever its base case is planted onward, and no earlier. …