Section 7.1 Proof by induction
Proof by induction is a powerful recursive proof technique where the truth of a statement \(P(n)\text{,}\) quantified over the integers, is proven by assuming \(P(n-1)\) is true. The analogy is to knocking over dominoes. In order to knock over dominoes, the first domino tile must be pushed over; then, the fall of each tile must force the fall of the following tile. So, proof by induction works like this:
Theorem 7.1.1. Proof by mathematical induction.
Fix some integer \(n_0\text{.}\) The statement \(P(n)\) is true for all integers \(n \ge n_0\) if:
\(P(n_0)\) is true. The statement \(P(n_0)\) is called the base case.
If \(P(k)\) is true for some integer \(k \ge n_0\text{,}\) then \(P(k+1)\) is true. The statement \(P(k)\) is called the inductive hypothesis, and the proof of \(P(k)\to P(k+1)\) is called the inductive step.
Wait, how does this imply \(P(n)\) is true for all \(n \ge n_0\text{?}\) To see an example, suppose that \(n_0=1\text{.}\) In our base case, we will prove \(P(1)\) is true. Then, the inductive step shows that \(P(k) \to P(k+1)\) for any \(k \ge 1\text{.}\) That includes \(1\text{,}\) so \(P(1)\) implies \(P(2)\text{.}\) In turn, \(P(2)\) implies \(P(3)\text{,}\) and \(P(3)\) implies \(P(4)\text{,}\) and so on, so that \(P(n)\) is proven for all integers at least as big as \(1\text{.}\)
Proof by induction can be used any time that the object or statement in question can be expressed recursively. In this chapter, we will pursue induction in two settings: sums, using the recursive property of summation; and inequalities, which allow us to prove big-O relationships.