Mathematical induction, or proof by induction, is a method of mathematical proof typically used to establish that a given statement is true for all natural numbers. It can also be used in more general settings as will be described below. An induction variant is used in computer science to prove that expressions which can be evaluated are equivalent, and this is known as structural induction.
The simplest and most common form of mathematical induction proves that a statement holds for all natural numbers n and consists of two steps:
- Showing that the statement holds when n = 0.
- Showing that if the statement holds for n = m, then the same statement also holds for n = m + 1.
- The first domino will fall.
- Whenever a domino falls, its next neighbor will also fall.
Table of contents |
2 Generalizations 3 Proof or reformulation of mathematical induction |
Example
Suppose we wish to prove the statement:
Proof
Check it is true for n = 0. Clearly, the sum of the first 0 natural numbers is 0, and 0.(0 + 1) / 2 = 0. So the statement is true for n = 0. We could define the statement as P(n), and thus we have that P(0) holds.Now we have to show that if the statement holds when n = m, then it also holds when n = m + 1. This can be done as follows.
Assume the statement is true for n = m, i.e.,
- We have P( 0 ), and thus P( 1 ) follows
- With P( 1 ), P( 2 ) follows
- ... etc
Generalizations
This type of proof can be generalized in several ways. For instance, if we want to prove a statement not for all natural numbers but only for all numbers greater than or equal to a certain number b then the following steps are sufficient:
- Showing that the statement holds when n = b.
- Showing that if the statement holds for n = m then the same statement also holds for n = m + 1.
Another generalization allows that in the second step we not only assume that the statement holds for n = m but also for all n smaller than or equal to m. This leads to the following two steps:
- Showing that the statement holds when n = 0.
- Showing that if the statement holds for all n ≤ m then the same statement also holds for n = m + 1.
The last two steps can be reformulated as one step:
- Showing that if the statement holds for all n < m then the same statement also holds for n = m.
This form of induction, when applied to ordinals (which form a well-ordered and hence well-founded class), is called transfinite induction. It is an important proof technique in set theory, topology and other fields.
Proofs by transfinite induction typically need to distinguish three cases:
- m is a minimal element, i.e. there is no element smaller than m
- m has a direct predecessor, i.e. the set of elements which are smaller than m has a largest element
- m has no direct predecessor, i.e. m is a so-called limit-ordinal
Proof or reformulation of mathematical induction
The principle of mathematical induction is usually stated as an axiom of natural numbers, see Peano axioms. However, it can be proved in some logical systems; for instance, if the following axiom:- The set of natural numbers is well-ordered
Note that the additional axiom is indeed an alternative formulation of principle of mathematical induction. That is, the two are equivalent. See proof of mathematical induction.