PROOF BY INDUCTION · HL
Inequalities
Prove an inequality holds for all n from a starting value.
Section 1 of 7
The method
Every proof by induction follows the same four lines.
Prove for $n = 1$ (or the first value stated)
Assume for $n = k$
Prove for $n = k+1$
Conclusion: Since true for the base and $n = k+1$ then true for all $n$.
Section 2 of 7
$2^{n} > n$
Prove $2^{n} > n$, $n \in \mathbb{N}$.
$n = 1$:
$2 > 1$ True
$n = k$:
$2^{k} > k$
$n = k+1$:
$2^{k+1} > k+1$
$2(2^{k}) > k+1$
$2^{k} + 2^{k} > k+1$
$2^{k} > k$ Assume
$2^{k} > 1$ Must
Section 3 of 7
$n! > 2^{n}$ for $n \ge 4$
Prove $n! > 2^{n}$ for $n \ge 4$.
$n = 4$:
$4! > 2^{4}$ ($24 > 16$)
$n = k$:
$k! > 2^{k}$
$n = k+1$:
$(k+1)! > 2^{k+1}$
$(k+1)\,k! > 2(2^{k})$
$k+1 > 2$ $k! > 2^{k}$
Since true for $n = 4$ and $n = k+1$ then true for all $n$.
Section 4 of 7
$(a+b)^{n} \ge a^{n} + b^{n}$
Prove $(a+b)^{n} \ge a^{n} + b^{n}$.
$n = 1$:
$a + b \ge a + b$
$n = k$:
$(a+b)^{k} \ge a^{k} + b^{k}$ (assumption)
$n = k+1$:
$(a+b)^{k+1} \ge a^{k+1} + b^{k+1}$
$(a+b)(a+b)^{k} \ge a(a^{k}) + b(b^{k})$
$a(a+b)^{k} + b(a+b)^{k} \ge a(a^{k}) + b(b^{k})$
$a(a+b)^{k} \ge a(a^{k})$ $b(a+b)^{k} \ge b(b^{k})$
Section 5 of 7
$3^{n} > 2n + 1$ for $n > 1$
Prove $3^{n} > 2n + 1$, $n > 1$.
$n = 2$:
$3^{2} > 2(2) + 1$ ($9 > 5$)
$n = k$:
$3^{k} > 2k + 1$ (assumption)
$n = k+1$:
$3^{k+1} > 2(k+1) + 1$
$3(3^{k}) > 2k + 2 + 1$
$(2+1)3^{k} > 2k + 1 + 2$
$2(3^{k}) + 3^{k} > 2k + 1 + 2$
$2(3^{k}) > 2$ $3^{k} > 2k + 1$
Section 6 of 7
$4^{n} \ge 3n^{2} + 1$
Prove $4^{n} \ge 3n^{2} + 1$, $n \in \mathbb{N}$.
$n = 1$
$n = k$:
$4^{k} \ge 3k^{2} + 1$ (assumption)
$n = k+1$:
$4^{k+1} \ge 3(k+1)^{2} + 1$
$4(4^{k}) \ge 3(k^{2} + 2k + 1) + 1$
$(3+1)(4^{k}) \ge 3k^{2} + 6k + 3 + 1$
$3(4^{k}) + 4^{k} \ge 3k^{2} + 1 + 6k + 3$
$4^{k} \ge 3k^{2} + 1$
$3(4^{k}) \ge 3(2k + 1)$
$4^{k} \ge 2k + 1$ must be
Geometric $\ge$ Arithmetic: $4, 16, 64 \;\ge\; 3, 5, 7$.
Section 7 of 7
$\dfrac{1}{(1+r)^{n}} \le \dfrac{1}{1+nr}$
Prove $\dfrac{1}{(1+r)^{n}} \le \dfrac{1}{1+nr}$, $r > 0$, $n \in \mathbb{N}$.
Idea: a bigger denominator gives a smaller fraction. e.g. $\dfrac{1}{3} < \dfrac{1}{2}$ since $3 > 2$.
$n = 1$
$n = k$:
$\dfrac{1}{(1+r)^{k}} \le \dfrac{1}{1+kr}$ (assumption)
$n = k+1$:
$\dfrac{1}{(1+r)^{k+1}} \le \dfrac{1}{1+(k+1)r}$
$\dfrac{1}{(1+r)(1+r)^{k}} \le \dfrac{1}{1+kr+r}$
$(1+r)(1+r)^{k} \ge 1 + kr + r$
$(1+r)^{k} + r(1+r)^{k} \ge 1 + kr + r$
$(1+r)^{k} \ge 1 + kr$
Conclusion: $r(1+r)^{k} \ge r$ since $r > 0$.
SUM
The lot in one box
The four steps
1.Prove for the base ($n = 1$, or the first value stated like $n = 4$).
2.Assume for $n = k$.
3.Prove for $n = k+1$ — split off the assumed inequality, then show the leftover piece "must be" true.
4.Conclusion: Since true for the base and $n = k+1$ then true for all $n$.
5.For fractions: flip to compare denominators (bigger denominator $\Rightarrow$ smaller fraction).
End of lesson
Induction — Inequalities · HL · Mathslive.ie