It should be intuitively clear that the principle of induction is valid. It follows from the fact that the list 0, 1, 2, 3, ..., if extended long enough, will eventually include any given natural number. If we start from P(0) and take enough steps of the form P(k) →P(k + 1), we can get P(n) for any given natural number n. However, whenever we deal with infinity, we are courting the possibility of paradox. We will prove the principle of induction rigorously in the next chapter (see Theorem 4.3), but for now we just state it as a theorem:
Let P be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that P(0) ∧ (∀k ∈ N (P(k) → P(k + 1))). Then P(n) is true for all natural numbers n. (That is, the statement ∀n P(n) is true, where the domain of discourse for P is the set of natural numbers.)
Mathematical induction can be applied in many situations: you can prove things about strings of characters by doing induction on the length of the string, things about graphs by doing induction on the number of nodes in the graph, things about grammars by doing induction on the number of productions in the grammar, and so on. We’ll be looking at applications of induction for the rest of this chapter, and treat a form called structural induction in the next chapter.
Although proofs by induction can be very different from one another, they all follow just a few basic structures. A proof based on the preceding theorem always has two parts. First, P(0) is proved. This is called the base case of the induction. Then the statement∀k (P(k) → P(k + 1)) is proved. This statement can be proved by letting k be an arbitrary element of N and proving P(k) → P(k + 1). This in turn can be proved by assuming that P(k) is true and proving that the truth of P(k + 1) follows from that assumption. This case is called the inductive case, and P(k) is called the inductive hypothesis or theinduction hypothesis. Note that the base case is just as important as the inductive case. By itself, the truth of the statement ∀k (P(k) → P(k + 1)) says nothing at all about the truth of any of the individual statements P(n). The chain of implications P(0) → P(1),P(1) → P(2), ..., P(n − 1) → P(n) says nothing about P(n) unless the chain is anchored at the other end by the truth of P(0).