The Numbers Behind Induction
Earlier in this course, natural numbers indexed finite sets, sequences, and lists. The diagonal argument, for instance, compared the \(n\)th entry of a sequence with the \(n\)th object in a list. We now examine the structure that makes such indexing possible: the natural numbers begin at a first value, and each value has a next value.
There are two common conventions about whether zero is a natural number. To keep both uses clear, write \(\mathbb N_0=\{0,1,2,\ldots\}\) for the natural numbers including zero, and \(\mathbb N_+=\{1,2,3,\ldots\}\) for the positive natural numbers. Sequence indices in earlier material can be read using the convention adopted there; the distinction does not affect arguments about countability. In this tutorial, induction will be stated on \(\mathbb N_0\), since the inclusion of zero makes recursive definitions especially convenient.
The next value after \(n\) is its successor, denoted \(S(n)\). In ordinary numerical notation, \(S(n)=n+1\). The successor viewpoint is more basic than the notation: it describes how the natural numbers are arranged, without presupposing how addition works.
- \(0\) is a natural number.
- The successor of every natural number is a natural number.
- No natural number has successor \(0\).
- If \(S(m)=S(n)\), then \(m=n\).
- If a set \(A\subseteq\mathbb N_0\) contains \(0\) and contains \(S(n)\) whenever it contains \(n\), then \(A=\mathbb N_0\).
The axioms rule out two possible irregularities. Successors cannot merge, since \(S(m)=S(n)\) forces \(m=n\); and zero cannot be the successor of another natural number. The induction axiom rules out missing natural numbers beyond the values obtained by starting at zero and repeatedly taking successors.
Mathematical Induction
The induction axiom gives a practical proof method. To prove a statement \(P(n)\) for every \(n\in\mathbb N_0\), first prove \(P(0)\). Then prove that whenever \(P(n)\) holds, \(P(S(n))\) holds as well. The set of values for which \(P\) is true then contains zero and is closed under successors, so the induction axiom says it contains every natural number.
Proof. Define \(A=\{n\in\mathbb N_0:P(n)\}\). The base case gives \(0\in A\). The inductive step says that if \(n\in A\), then \(S(n)\in A\), so \(A\) is closed under successors. By the induction axiom, \(A=\mathbb N_0\). Thus \(P(n)\) holds for every \(n\in\mathbb N_0\). \(\square\)
The statement \(P(n)\) is called the inductive hypothesis when it is assumed temporarily in the step of the proof. That assumption is not circular: the base case establishes the first instance, and the step proves that each established instance gives the next one.
Worked Example: The Sum of the First \(n\) Positive Integers
For \(n\in\mathbb N_0\), the sum of the positive integers from \(1\) to \(n\) is \(\frac{n(n+1)}{2}\); when \(n=0\), the sum is empty and has value zero. We prove this formula by induction.
At \(n=0\), both sides equal zero: \[ 0=\frac{0(0+1)}{2}. \] Now assume the formula holds for \(n\). The sum through \(n+1\) is the sum through \(n\), plus \(n+1\). Therefore \[ \frac{n(n+1)}{2}+(n+1) =\frac{n(n+1)+2(n+1)}{2} =\frac{(n+1)(n+2)}{2}. \] This is exactly the claimed formula with \(n+1\) in place of \(n\). Induction proves the formula for every \(n\in\mathbb N_0\).
This example illustrates two essential parts of the method. The inductive step must use the hypothesis for \(n\) to establish the claim for its successor, and its conclusion must be precisely the same statement with the index advanced by one.
Recursive Definitions
The same successor structure allows us to define values one at a time. For example, addition on \(\mathbb N_0\) can be specified recursively by
These rules say how to add zero and how to add the next natural number once the previous sum is known. Multiplication and powers can likewise be specified recursively:
In ordinary notation, \(S(n)=n+1\), so these definitions yield the familiar meanings of addition, multiplication, and exponentiation. The recursive equations are useful in proofs because they identify exactly what changes when an index advances by one.
Worked Example: Adding Zero on the Left
The recursive rule \(m+0=m\) immediately gives \(n+0=n\). It does not, by itself, state that \(0+n=n\), because in the definition the second argument is the one that advances. We prove the left-hand identity separately by induction on \(n\).
For the base case, \(0+0=0\) by the recursive rule. Suppose \(0+n=n\). Then \[ 0+S(n)=S(0+n)=S(n), \] where the first equality is the recursive definition of addition and the second uses the inductive hypothesis. Thus the identity holds at \(S(n)\). Induction gives \(0+n=n\) for every \(n\in\mathbb N_0\).
The proof also illustrates a general point about recursive definitions: the side of an operation on which the recursive rule is given matters. A rule for \(m+S(n)\) directly advances the second argument; it is not a proof of a statement about advancing the first argument.
Strong Induction
Sometimes a claim about \(n\) is easier to prove using all the earlier cases, not only the case \(n-1\). Strong induction permits this. Its additional-looking assumption does not make it a stronger principle than ordinary induction; it follows from ordinary induction.
Proof. Define \(Q(n)\) to be the statement that \(P(k)\) holds for every \(k\leq n\). We use ordinary induction to prove \(Q(n)\) for all \(n\). For \(n=0\), the assumption of the theorem applied to \(0\) says \(P(0)\): there are no natural numbers \(k<0\), so the condition on all such \(k\) is satisfied. Hence \(Q(0)\) holds.
Now suppose \(Q(n)\) holds. It gives \(P(k)\) for every \(k\leq n\). In particular, \(P(k)\) holds for every \(k<S(n)\), since the natural numbers less than \(S(n)\) are exactly those less than or equal to \(n\). The hypothesis of the theorem therefore gives \(P(S(n))\). Together with \(Q(n)\), this means \(P(k)\) holds for every \(k\leq S(n)\), so \(Q(S(n))\) holds. By ordinary induction, \(Q(n)\) holds for every \(n\), and therefore \(P(n)\) holds for every \(n\). \(\square\)
The proof uses the usual order of the natural numbers: each number is followed immediately by its successor. Strong induction is especially useful when an object at stage \(n\) may depend on several smaller stages, as happens in recursive constructions and divisibility arguments.
Worked Example: A Bound for Powers of Two
We prove \(2^n\geq n+1\) for every \(n\in\mathbb N_0\). At \(n=0\), \(2^0=1=0+1\). Suppose \(2^n\geq n+1\). Then \[ 2^{n+1}=2\cdot 2^n\geq 2(n+1). \] Since \(2(n+1)-(n+2)=n\geq0\), we have \(2(n+1)\geq n+2\). Consequently \(2^{n+1}\geq n+2\), which is the desired inequality at the successor. Induction proves the bound.
The inductive step has two separate comparisons: the hypothesis gives the first, and the nonnegativity of \(n\) gives the second. Making both explicit prevents a gap in the argument.
Worked Example: A Recursively Defined Sequence
Define \(a_0=2\) and \(a_{n+1}=3a_n+1\). The first values are \(a_0=2\), \(a_1=7\), and \(a_2=22\). We claim that \[ a_n=\frac{5\cdot 3^n-1}{2}. \] At \(n=0\), the right side is \((5-1)/2=2=a_0\). Suppose the formula holds at \(n\). Then \[ a_{n+1}=3a_n+1 =3\left(\frac{5\cdot3^n-1}{2}\right)+1 =\frac{15\cdot3^n-3+2}{2} =\frac{5\cdot3^{n+1}-1}{2}. \] This is the proposed formula at \(n+1\). Induction proves it for every \(n\in\mathbb N_0\). For example, at \(n=2\), it gives \((5\cdot9-1)/2=22\), agreeing with the recursive calculation.
Choosing the Right Induction Argument
A base case is necessary, but it is not enough on its own. Checking a claim for \(n=0\), \(n=1\), and several later values provides evidence; it does not prove the claim for all natural numbers. The inductive step supplies the missing argument by showing that no first failure can occur: if the claim holds at one stage, it must hold at the next.
For a statement that begins at \(1\), the same method uses \(P(1)\) as the base case and proves \(P(n)\Rightarrow P(n+1)\) for \(n\geq1\). Alternatively, one can state it on \(\mathbb N_0\) and adjust the claim so that its first relevant case is included. The base case must match the domain of the claim.
Strong induction is a useful choice when the inductive argument needs more than the immediately preceding case. Ordinary induction remains available: strong induction is justified by the theorem above. Conversely, ordinary induction is often simpler when \(P(n)\) follows directly from \(P(n-1)\), as in the formula for the recursively defined sequence.
Check Your Understanding
Use the successor structure and the induction methods in this tutorial to answer the following questions.
- Which Peano axiom rules out a natural number whose successor is zero?
- In an induction proof, what must the inductive step establish?
- Why does the recursive rule for \(m+S(n)\) not by itself prove \(0+n=n\)?
- In the strong induction proof, what statement is \(Q(n)\) chosen to express?
- For a claim stated only for positive natural numbers, what is an appropriate base case?
- Why do several successful numerical checks not prove a claim for every natural number?