Proof by induction: inequalities
Aoife starts a chain message: she sends it to 2 friends, each of them sends it to 2 new friends, and so on. After $n$ rounds the number of people involved grows like $2^n$. Seán has a different plan: after $n$ rounds he wants $n^2$ people. For a few rounds Seán is ahead or level, but then the doubling takes over. From which round on is $2^n$ bigger than $n^2$, and how can we be sure it stays bigger forever? Checking round after round never finishes, so we need a proof by induction.
How induction works for inequalities
You already know the pattern from identities and divisibility. To prove a statement $P(n)$ for all $n \in \mathbb{N}$ (here $\mathbb{N} = \{1, 2, 3, \dots\}$):
-
Base case: show $P(1)$ is true (or the first value the question gives).
-
Assumption: assume $P(k)$ is true for some $k$.
-
Step: use that assumption to show $P(k+1)$ is true.
-
Conclusion: state it in words.
The only new difficulty with inequalities is the step. In an identity you can turn the left side into the right side. In an inequality you usually build a chain: $\text{something} \;>\; \text{something else} \;\ge\; \text{target}$, and every link must be justified.
Prove by induction that $2^n > n$ for all $n\in\mathbb{N}$.
Prove by induction that $2^n > n$ for all $n\in\mathbb{N}$.
Building the chain
Let us prove $3^n \ge 2n + 1$ for all $n \in \mathbb{N}$.
The recipe is always the same:
-
Write $P(k+1)$'s left side so that the left side of $P(k)$ appears (for powers, $a^{k+1} = a \cdot a^k$; for factorials, $(k+1)! = (k+1)\,k!$; for sums, add the next term).
-
Replace that part using the assumption. This is where the inequality sign gets used.
-
Show the result is at least (or more than) the target. Often this is "something obviously non-negative is left over".
Prove by induction that $3^n \geq 2n + 1$ for all $n \in \mathbb{N}$.
Prove by induction that $3^n \geq 2n + 1$ for all $n \in \mathbb{N}$.
Prove by induction that $n! \geq 2^{n-1}$ for all $n \in \mathbb{N}$.
Prove by induction that $n! \geq 2^{n-1}$ for all $n \in \mathbb{N}$.
Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$, where $x > -1$ is a fixed real number.
Prove by induction that $(1+x)^n \geq 1 + nx$ for all $n \in \mathbb{N}$, where $x > -1$ is a fixed real number.
When the statement starts later
Many inequalities are false for small $n$. Compare $2^n$ and $n^2$:
| $n$ | 1 | 2 | 3 | 4 | 5 | 6 | 7 |
|---|---|---|---|---|---|---|---|
| $2^n$ | 2 | 4 | 8 | 16 | 32 | 64 | 128 |
| $n^2$ | 1 | 4 | 9 | 16 | 25 | 36 | 49 |
$2^n > n^2$ is true for $n = 1$, false for $n = 2, 3, 4$ (equal, then smaller, then equal), and true again from $n = 5$ onwards. The graphs show the same story.
This answers Aoife and Seán: from the fifth round on, the doubling beats the squaring. Induction shows it stays that way for ever. The only change to the method is that the base case is the first value from which the statement stays true for all larger $n$ (here $n = 5$; the isolated true value $n = 1$ cannot be used, because $P(2)$ fails), and the step must work for every $k \ge 5$.
Notice where $k \ge 5$ was used: to show $k^2 - 2k - 1 > 0$. For $k = 3$ this would be $9 - 6 - 1 = 2 > 0$, so the algebra alone would "work", but $P(3)$ is false and the chain cannot start. The base case is what makes the starting value $5$ essential: induction cannot reach back before it.
Factorials grow faster than any exponential, but only from a certain point. Here is an example where you finish the last step yourself.
The same idea works for any pair like $n! > 3^n$ (a bigger starting value) and $3^n > n^3$ (a polynomial chain). In both cases:
-
Find the starting value by checking small cases, and say clearly which values fail.
-
Use the starting value in the step to show the multiplier ($k+1$, or the ratio) is large enough.
Prove by induction that $2^n > n^2$ for all integers $n \geq 5$.
Prove by induction that $2^n > n^2$ for all integers $n \geq 5$.
Prove by induction that $n! > 3^n$ for all integers $n \geq 7$.
Prove by induction that $n! > 3^n$ for all integers $n \geq 7$.
a) Find the smallest positive integer $N$ for which $3^n > n^3$ for all $n \geq N$ appears to hold, by checking small values. b) Prove by induction that $3^n > n^3$ for…
- a) Find the smallest positive integer $N$ for which $3^n > n^3$ for all $n \geq N$ appears to hold, by checking small values.
- b) Prove by induction that $3^n > n^3$ for all integers $n \geq N$.
- c) Explain why the statement is false for $n = 3$.
Inequalities with sums
When the statement is about a sum $S_n = a_1 + a_2 + \dots + a_n$, the step has one natural move: add the next term,
$$S_{k+1} = S_k + a_{k+1}.$$Then use the assumption on $S_k$, and compare what you get with the target for $k + 1$.
Two habits help with harder sum inequalities.
Prove by induction that $$\sum_{r=1}^{n}\frac{1}{r^2} \leq 2 - \frac1n$$ for all $n\in\mathbb{N}$.
Prove by induction that
$$\sum_{r=1}^{n}\frac{1}{r^2} \leq 2 - \frac1n$$for all $n\in\mathbb{N}$.
Prove by induction that $\dfrac{1}{\sqrt1} + \dfrac{1}{\sqrt2} + \dots + \dfrac{1}{\sqrt n} \geq \sqrt n$ for all $n \in \mathbb{N}$.
Prove by induction that $\dfrac{1}{\sqrt1} + \dfrac{1}{\sqrt2} + \dots + \dfrac{1}{\sqrt n} \geq \sqrt n$ for all $n \in \mathbb{N}$.
Summary
-
Structure: base case, assumption $P(k)$, step to $P(k+1)$, conclusion in words.
-
In the step, build a chain of inequalities: use the assumption once, then show the result is at least the target (often by showing a difference is positive).
-
Only multiply an inequality by a positive quantity. Conditions such as $x > -1$ are there to guarantee this.
-
If the statement is false for small $n$ (like $2^n > n^2$, true for $n \ge 5$), check values to find the starting value and use it as the base case. Use $k \ge$ the starting value in the step.
-
For sums, add the next term, apply the assumption, then compare with the target for $k+1$. Work backwards on rough paper, but write the proof forwards.
-
Back to the start: $2^n > n^2$ for all $n \ge 5$, so after the fifth round Aoife's doubling chain always beats Seán's squaring plan.