Induction proofs of inequalities · Mathematics 6th Year HL

$n$	1	2	3	4	5	6
$n!$	1	2	6	24	120	720
$2^n$	2	4	8	16	32	64

The structure of an inequality proof

You already know proof by induction for identities. The four steps are the same for inequalities.

Base case. Show $P(n_0)$ is true for the first value $n_0$.
Assumption. Assume $P(k)$ is true for some $k \geq n_0$.
Inductive step. Using the assumption, prove $P(k+1)$.
Conclusion. State that $P(n)$ is true for all $n \geq n_0$ by induction.

The base case knocks over the first domino. The inductive step says each domino knocks over the next. Together, all of them fall.

The difference with inequalities is in step 3. You cannot "show LHS = RHS". Instead you build a chain:

$$\text{LHS of } P(k+1) \;\;\geq\;\; \text{(use the assumption)} \;\;\geq\;\; \dots \;\;\geq\;\; \text{RHS of } P(k+1).$$

Every link in the chain must be justified. Usually one link uses $P(k)$ and the others are simple algebra.

Practice★☆☆

Let $P(n)$ be the statement $2^n \geq n + 1$. a) Show that $P(1)$ and $P(2)$ are true. b) Assuming $P(k)$ is true, prove that $P(k+1)$ is true.

Let $P(n)$ be the statement $2^n \geq n + 1$.

a) Show that $P(1)$ and $P(2)$ are true.

b) Assuming $P(k)$ is true, prove that $P(k+1)$ is true.

Solve

Practice★☆☆

Prove by induction that $3^n > 2n$ for all $n \in \mathbb{N}$.

Solve

When the base case is not $n = 1$

Look back at the table. $n! > 2^n$ is false for $n = 1, 2, 3$ and true from $n = 4$. A proof by induction for "all $n \geq 4$" must therefore start at $n = 4$.

Why can't you start earlier? The base case must be true. Also, the inductive step usually only works once $k$ is big enough, and that is exactly the case here. The step, where we multiply by $k + 1$, needs $k + 1 > 2$.

(The picture is a sketch of the idea: compare the real values in the exercises.)

Practice★☆☆

Let $P(n)$ be the statement $n! > 2^n$. a) Show that $P(4)$ is true. b) Show that $P(3)$ is false. c) Explain why the base case for a proof by induction must be $n = 4$.

Let $P(n)$ be the statement $n! > 2^n$.

a) Show that $P(4)$ is true.

b) Show that $P(3)$ is false.

c) Explain why the base case for a proof by induction must be $n = 4$.

Solve

Practice★★☆

Prove by induction that $n! > 2^n$ for all integers $n \geq 4$.

Solve

Practice★★☆

Prove by induction that $2^n \geq n^2$ for all integers $n \geq 4$. Check by direct calculation that the inequality fails for $n = 3$.

Solve

Inequalities with a parameter: Bernoulli's inequality

Sometimes the statement contains a second letter. For example, for a real number $x$,

$$(1 + x)^n \geq 1 + nx.$$

This says compound growth is at least as big as "simple" growth. If you invest €100 at 5% a year, the left side with $x = 0.05$ is the compound amount, and $1 + nx$ is what simple interest would give.

The proof is still on $n$. The number $x$ stays fixed. The question is what conditions on $x$ you need. Here is the key step, with the target $(1+x)^{k+1} \geq 1 + (k+1)x$.

Prove that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$, where $x \geq -1$

Base case. $n = 1$: $(1+x)^1 = 1 + x = 1 + 1\cdot x$. True (equality).

Assumption. Assume $(1+x)^k \geq 1 + kx$ for some $k \in \mathbb{N}$.

Inductive step. Multiply both sides of the assumption by $(1 + x)$:

$$(1+x)^{k+1} = (1+x)^k (1+x) \geq (1 + kx)(1+x).$$

This is only valid because $1 + x \geq 0$, which is exactly the condition $x \geq -1$. If $1 + x$ were negative, the inequality would flip.

Expand: $(1+kx)(1+x) = 1 + x + kx + kx^2 = 1 + (k+1)x + kx^2$.

Your turn. Explain why $1 + (k+1)x + kx^2 \geq 1 + (k+1)x$, and write the conclusion.

???

Because $kx^2 \geq 0$ (a square is never negative and $k > 0$). So $(1+x)^{k+1} \geq 1 + (k+1)x$, which is $P(k+1)$. By induction the inequality holds for all $n \in \mathbb{N}$ and all $x \geq -1$.

A condition on $x$ is not decoration. Say clearly in your proof the line where it is used. If $x > 0$ is given, the same proof works, because then $1 + x > 0$ and every term is positive.

Practice★★☆

Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$, where $x > 0$.

Solve

Practice★★★

Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$ and all real $x \geq -1$. Explain where in your proof the condition $x \geq -1$ is used. Hence…

Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$ and all real $x \geq -1$. Explain where in your proof the condition $x \geq -1$ is used. Hence show that $(0.99)^{50} \geq 0.5$.

Solve

Harder chains: sums and fast-growing powers

Two tricks cover most of the harder questions.

Trick 1: inequalities for sums

When the left side is a sum $S_n$, then $S_{k+1} = S_k + (\text{new term})$. Apply the assumption to $S_k$, add the new term, and compare with the target. You often end with an inequality in $k$ alone, which you can check by rearranging.

Prove that $\dfrac{1}{1^2} + \dfrac{1}{2^2} + \dots + \dfrac{1}{n^2} \leq 2 - \dfrac{1}{n}$ for all $n \in \mathbb{N}$

Base case. $n = 1$: left side $= 1$, right side $= 2 - 1 = 1$. So $1 \leq 1$ is true.

Assumption. Assume $\sum_{i=1}^{k} \frac{1}{i^2} \leq 2 - \frac{1}{k}$.

Inductive step. Add the new term to both sides:

$$\sum_{i=1}^{k+1} \frac{1}{i^2} \leq 2 - \frac{1}{k} + \frac{1}{(k+1)^2}.$$

The target is $2 - \frac{1}{k+1}$. So we must show $-\frac{1}{k} + \frac{1}{(k+1)^2} \leq -\frac{1}{k+1}$.

Rearrange: this is $\frac{1}{(k+1)^2} + \frac{1}{k+1} \leq \frac{1}{k}$. The left side is $\frac{1 + (k+1)}{(k+1)^2} = \frac{k+2}{(k+1)^2}$. Multiply both sides by the positive number $k(k+1)^2$: we need $k(k+2) \leq (k+1)^2$, i.e. $k^2 + 2k \leq k^2 + 2k + 1$. True.

Conclusion. By induction, the inequality holds for all $n \in \mathbb{N}$.

Trick 2: comparing a power with a polynomial

To prove $2^n > n^3$ (for large $n$) you multiply by 2 and then need $2k^3 \geq (k+1)^3$. Rewrite $(k+1)^3 = k^3\left(1 + \tfrac{1}{k}\right)^3$. For $k \geq 10$, $\left(1 + \tfrac1k\right)^3 \leq (1.1)^3 = 1.331 < 2$. So $(k+1)^3 < 2k^3$, and the growth factor of 2 per step beats the growth factor of the polynomial.

If a question asks "for which $n$ does the statement hold?", use a table for small $n$ to find the starting value, then induction for all larger $n$, then state clearly which values are left over.

Practice★★★

Prove by induction that $\frac{1}{\sqrt{1}} + \frac{1}{\sqrt{2}} + \dots + \frac{1}{\sqrt{n}} \geq \sqrt{n}$ for all $n \in \mathbb{N}$.

Solve

Practice★★★

a) Prove by induction that $2^n > n^3$ for all integers $n \geq 10$. b) Find, with justification, the values of $n \in \mathbb{N}$ for which $2^n \leq n^3$.

a) Prove by induction that $2^n > n^3$ for all integers $n \geq 10$.

b) Find, with justification, the values of $n \in \mathbb{N}$ for which $2^n \leq n^3$.

Solve

Back to the start: does $n!$ beat $2^n$ for every $n \geq 4$? Yes. We checked $n = 4$ ($24 > 16$), and whenever $k! > 2^k$ with $k \geq 4$, multiplying by $k + 1 \geq 5 > 2$ gives $(k+1)! > 2^{k+1}$. So the factorial keeps winning forever.

Summary

Let's practice! 3 medium exercises in this section

★★☆ Prove by induction that $n! > 2^n$ for all integers $n \geq 4$.★★☆ Prove by induction that $2^n \geq n^2$ for all integers $n \geq 4$. Check by direct…★★☆ Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$, where $x > 0$.