The principle of mathematical induction is one of the most important proof techniques in all of mathematics. It allows us to show that a property holds for every natural number, reducing an infinite collection of cases to a finite, rigorous, and manageable argument.
The underlying idea is simple: if a property holds at the very beginning, and if whenever it holds for a given natural number it also holds for the next one, then it holds for every natural number.
Table of Contents
- Intuition behind mathematical induction
- Statement of the principle of mathematical induction
- Base case and inductive step
- Why induction works
- Induction starting from an arbitrary value
- Induction and inductive sets
- Example 1: sum of the first natural numbers
- Example 2: an exponential inequality
- The well-ordering principle
- Equivalence between induction and well-ordering
- Strong induction
- Common mistakes in inductive proofs
- Induction and recursive definitions
- Conclusion
Intuition behind mathematical induction
The principle of mathematical induction is often explained through the image of a row of dominoes.
Imagine an infinite line of tiles. To be certain that every tile will fall, we do not need to check each one individually. It suffices to verify two facts:
- the first tile falls;
- every tile, when it falls, knocks down the next one.
If both conditions are satisfied, then every tile in the line will fall.
The same logic applies in mathematics. To prove that a property \(P(n)\) holds for every natural number \(n\), we verify that it holds for the first value and prove that its validity for any given number implies its validity for the next.
Statement of the principle of mathematical induction
Let \(P(n)\) be a property depending on a natural number \(n\). The principle of mathematical induction states that if the following two conditions hold:
\[ P(1) \text{ is true} \]
and
\[ P(n) \Rightarrow P(n+1) \quad \text{for every } n \geq 1, \]
then:
\[ P(n) \text{ is true for every } n \in \mathbb{N},\ n \geq 1. \]
If instead one adopts the convention that the natural numbers begin at \(0\), the base case becomes \(P(0)\) and the inductive step becomes:
\[ P(n) \Rightarrow P(n+1) \quad \text{for every } n \geq 0. \]
Base case and inductive step
A proof by induction consists of two fundamental stages.
1. Base case
We show that the property holds for the first value under consideration, usually \(n = 1\) or \(n = 0\).
This verification is indispensable: without a starting point, the inductive chain cannot begin.
2. Inductive step
We assume that the property holds for some natural number \(n\). This assumption is called the inductive hypothesis.
Starting from it, we prove that the property also holds for \(n + 1\).
In symbolic form:
\[ P(n) \Rightarrow P(n+1). \]
The key point is that we are not assuming the property is true for all natural numbers. We are establishing an implication: if the property holds at a certain point in the chain, then it holds at the next point as well.
Why induction works
Mathematical induction works because the natural numbers are built in an ordered, sequential fashion:
\[ 1, 2, 3, 4, \dots \]
or, starting from \(0\):
\[ 0, 1, 2, 3, \dots \]
Once the first case is verified, the inductive step allows us to pass from the first to the second, from the second to the third, from the third to the fourth, and so on.
In this way, an infinite chain of implications is generated:
\[ P(1) \Rightarrow P(2) \Rightarrow P(3) \Rightarrow P(4) \Rightarrow \dots \]
The power of induction lies precisely here: a finite argument is able to handle infinitely many cases because it exploits the very structure of the natural numbers.
Induction starting from an arbitrary value
The inductive chain need not always start at \(n = 1\) or \(n = 0\). In many situations, a property becomes true only from some integer \(n_0\) onwards.
In this case the principle of induction reads as follows. If:
\[ P(n_0) \text{ is true} \]
and
\[ P(n) \Rightarrow P(n+1) \quad \text{for every } n \geq n_0, \]
then:
\[ P(n) \text{ is true for every } n \geq n_0. \]
For example, let us prove that:
\[ 2^n > n^2 \]
for every \(n \geq 5\).
Base case
For \(n = 5\), we have:
\[ 2^5 = 32 \]
and
\[ 5^2 = 25. \]
Hence:
\[ 2^5 > 5^2. \]
Inductive step
Assume that, for some \(n \geq 5\), the inequality
\[ 2^n > n^2 \]
holds. We must show that:
\[ 2^{n+1} > (n+1)^2. \]
Since:
\[ 2^{n+1} = 2 \cdot 2^n, \]
the inductive hypothesis gives:
\[ 2^{n+1} = 2 \cdot 2^n > 2n^2. \]
We now observe that, for every \(n \geq 5\),
\[ 2n^2 > (n+1)^2. \]
Indeed:
\[ 2n^2 - (n+1)^2 = n^2 - 2n - 1. \]
For \(n \geq 5\), we have:
\[ n^2 - 2n - 1 = (n-1)^2 - 2 \geq 4^2 - 2 = 14 > 0. \]
Therefore:
\[ 2n^2 > (n+1)^2. \]
Combining both inequalities:
\[ 2^{n+1} > 2n^2 > (n+1)^2. \]
Thus:
\[ 2^{n+1} > (n+1)^2. \]
The inductive step is proved. By the principle of induction starting from \(n_0 = 5\), we conclude that:
\[ 2^n > n^2 \]
for every \(n \geq 5\).
The logic is unchanged: the chain of implications simply starts from a different point.
Induction and inductive sets
The principle of induction can also be expressed in set-theoretic terms.
A subset \(A \subseteq \mathbb{N}\) is called inductive if it satisfies two conditions:
\[ 1 \in A \]
and
\[ n \in A \Rightarrow n+1 \in A. \]
In other words, \(A\) contains the first natural number and, together with each number, also contains its successor.
The principle of induction then asserts that:
\[ \text{if } A \subseteq \mathbb{N} \text{ is inductive, then } A = \mathbb{N}. \]
This formulation highlights an important fact: induction is not merely a technique for solving exercises, but a structural property of the set of natural numbers.
Example 1: sum of the first natural numbers
We prove by induction that, for every \(n \geq 1\),
\[ 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}. \]
Base case
For \(n = 1\), the left-hand side is:
\[ 1. \]
The right-hand side is:
\[ \frac{1 \cdot (1+1)}{2} = \frac{2}{2} = 1. \]
The formula holds for \(n = 1\).
Inductive step
Assume the formula holds for some \(n \geq 1\), i.e., assume:
\[ 1 + 2 + 3 + \dots + n = \frac{n(n+1)}{2}. \]
We must show that:
\[ 1 + 2 + 3 + \dots + n + (n+1) = \frac{(n+1)(n+2)}{2}. \]
Starting from the left-hand side:
\[ 1 + 2 + 3 + \dots + n + (n+1). \]
By the inductive hypothesis, we may replace \(1 + 2 + \dots + n\) with \(\frac{n(n+1)}{2}\):
\[ 1 + 2 + \dots + n + (n+1) = \frac{n(n+1)}{2} + (n+1). \]
Factoring out \(n+1\):
\[ \frac{n(n+1)}{2} + (n+1) = (n+1)\!\left(\frac{n}{2} + 1\right). \]
Since:
\[ \frac{n}{2} + 1 = \frac{n+2}{2}, \]
we obtain:
\[ (n+1)\!\left(\frac{n}{2}+1\right) = \frac{(n+1)(n+2)}{2}. \]
Therefore:
\[ 1 + 2 + \dots + n + (n+1) = \frac{(n+1)(n+2)}{2}. \]
The property holds for \(n+1\). By the principle of induction, the formula holds for every \(n \geq 1\).
Example 2: an exponential inequality
We prove that, for every \(n \in \mathbb{N}\) with \(n \geq 0\),
\[ 2^n \geq n + 1. \]
Base case
For \(n = 0\), we have:
\[ 2^0 = 1 \]
and
\[ 0 + 1 = 1. \]
Hence:
\[ 2^0 \geq 0 + 1. \]
The property holds for \(n = 0\).
Inductive step
Assume that, for some \(n \geq 0\),
\[ 2^n \geq n + 1. \]
We must show that:
\[ 2^{n+1} \geq n + 2. \]
Observe that:
\[ 2^{n+1} = 2 \cdot 2^n. \]
Using the inductive hypothesis:
\[ 2 \cdot 2^n \geq 2(n+1). \]
Therefore:
\[ 2^{n+1} \geq 2n + 2. \]
Since \(n \geq 0\), we have:
\[ 2n + 2 \geq n + 2. \]
Consequently:
\[ 2^{n+1} \geq n + 2. \]
The property holds for \(n+1\) as well. By induction:
\[ 2^n \geq n + 1 \]
for every \(n \geq 0\).
The well-ordering principle
The well-ordering principle states that every non-empty subset of \(\mathbb{N}\) has a least element.
In symbols:
\[ A \subseteq \mathbb{N},\quad A \neq \varnothing \quad \Longrightarrow \quad \exists\, m \in A \text{ such that } m \leq a \text{ for every } a \in A. \]
The element \(m\) is called the minimum (or least element) of \(A\).
Note carefully: the minimum is not merely a small element. It is an element of the set that is less than or equal to every other element of the set.
For instance, if:
\[ A = \{5, 8, 13, 21\}, \]
then:
\[ \min A = 5. \]
If instead:
\[ B = \{n \in \mathbb{N} \mid n \geq 10\}, \]
then:
\[ \min B = 10. \]
The well-ordering principle is a characteristic property of the natural numbers. It does not hold, for example, for all non-empty subsets of \(\mathbb{Z}\). Indeed, the set:
\[ \mathbb{Z} = \{\dots, -3, -2, -1, 0, 1, 2, 3, \dots\} \]
has no least element.
Equivalence between induction and well-ordering
The principle of mathematical induction and the well-ordering principle are equivalent: assuming either one, the other can be derived.
This equivalence is significant because it shows that induction is not a mere technical device, but a deep consequence of the ordered structure of the natural numbers.
From well-ordering to mathematical induction
Assume the well-ordering principle holds. We wish to derive the principle of induction.
Let \(P(n)\) be a property of natural numbers. Suppose that:
\[ P(1) \text{ is true} \]
and that:
\[ P(n) \Rightarrow P(n+1) \quad \text{for every } n \geq 1. \]
We must show that \(P(n)\) is true for every \(n \geq 1\).
We argue by contradiction. Suppose there exists at least one natural number for which \(P\) is false. Consider the set of counterexamples:
\[ A = \{n \in \mathbb{N} \mid P(n) \text{ is false}\}. \]
By assumption, \(A \neq \varnothing\). Hence, by the well-ordering principle, \(A\) has a least element, which we denote \(m\).
Since \(P(1)\) is true, the number \(1\) does not belong to \(A\). Therefore \(m \neq 1\), so \(m > 1\).
Then \(m - 1\) is a natural number less than \(m\). Since \(m\) is the least element of \(A\), the number \(m - 1\) cannot belong to \(A\).
Hence \(P(m-1)\) is true.
But by the inductive step:
\[ P(m-1) \Rightarrow P(m). \]
It follows that \(P(m)\) is true.
This is a contradiction, since \(m \in A\) means \(P(m)\) should be false.
We have reached a contradiction. Therefore the set of counterexamples is empty:
\[ A = \varnothing. \]
Hence \(P(n)\) is true for every \(n \geq 1\). The principle of induction is proved.
From mathematical induction to well-ordering
Now assume the principle of induction holds. We wish to derive the well-ordering principle.
Let \(A \subseteq \mathbb{N}\) be a non-empty subset. We must show that \(A\) has a least element.
We argue by contradiction. Suppose \(A\) has no least element.
If \(1 \in A\), then \(1\) would automatically be the least element of \(A\), since no positive natural number is smaller than \(1\). But by assumption \(A\) has no least element. Therefore:
\[ 1 \notin A. \]
Consider the property:
\[ P(n): \quad 1, 2, \dots, n \notin A. \]
That is, \(P(n)\) asserts that none of the first \(n\) natural numbers belongs to \(A\).
Base case
We have already noted that:
\[ 1 \notin A. \]
Therefore \(P(1)\) is true.
Inductive step
Assume \(P(n)\) is true, i.e., assume that:
\[ 1, 2, \dots, n \notin A. \]
We must show that:
\[ 1, 2, \dots, n, n+1 \notin A. \]
By the inductive hypothesis, we already know that \(1, 2, \dots, n\) do not belong to \(A\). It remains to show that \(n+1 \notin A\).
Suppose for contradiction that:
\[ n+1 \in A. \]
Then \(n+1\) would be the least element of \(A\), since none of the preceding natural numbers belongs to \(A\).
But this contradicts the assumption that \(A\) has no least element.
Therefore:
\[ n+1 \notin A. \]
The inductive step is proved.
By the principle of induction, \(P(n)\) is true for every \(n \geq 1\). Hence no natural number belongs to \(A\), that is:
\[ A = \varnothing. \]
But this is impossible, since we assumed \(A \neq \varnothing\).
The contradiction shows that \(A\) must have a least element. The well-ordering principle is proved.
Strong induction
There is a variant of the principle of induction known as strong induction (also called complete induction or course-of-values induction).
In ordinary induction, to prove \(P(n+1)\) one assumes only \(P(n)\).
In strong induction, to prove \(P(n+1)\) one assumes that all preceding instances hold:
\[ P(1), P(2), \dots, P(n). \]
The formal statement is as follows. If:
\[ P(1) \text{ is true} \]
and, for every \(n \geq 1\),
\[ P(1) \land P(2) \land \dots \land P(n) \Rightarrow P(n+1), \]
then:
\[ P(n) \text{ is true for every } n \geq 1. \]
Strong induction is not logically more powerful than ordinary induction: the two forms are equivalent. However, in many proofs, strong induction is more natural and easier to apply.
Example 1: factorisation into prime numbers
A classical application of strong induction is the proof that every natural number greater than \(1\) is either prime or can be written as a product of prime numbers.
Let \(n > 1\). If \(n\) is prime, there is nothing to prove.
If \(n\) is not prime, then there exist two integers \(a\) and \(b\), both greater than \(1\) and less than \(n\), such that:
\[ n = ab. \]
Since \(a < n\) and \(b < n\), the strong induction hypothesis allows us to assume that both \(a\) and \(b\) are either prime or products of primes.
Consequently, \(n = ab\) is also a product of primes.
This example shows why it is useful in certain contexts to draw on not just the immediately preceding case, but all previous cases.
Example 2: the Fibonacci sequence
The Fibonacci sequence is defined by:
\[ F_1 = 1, \quad F_2 = 1, \quad F_n = F_{n-1} + F_{n-2} \quad \text{for every } n \geq 3. \]
We prove by strong induction that, for every \(n \geq 1\),
\[ F_n < 2^n. \]
Base cases
For \(n = 1\):
\[ F_1 = 1 < 2 = 2^1. \]
For \(n = 2\):
\[ F_2 = 1 < 4 = 2^2. \]
Two base cases are needed because the recurrence relation expresses each term using the two preceding terms.
Inductive step
Let \(n \geq 3\). By the strong induction hypothesis, the inequality holds for all indices less than \(n\). In particular:
\[ F_{n-1} < 2^{n-1} \qquad \text{and} \qquad F_{n-2} < 2^{n-2}. \]
Then:
\[ F_n = F_{n-1} + F_{n-2} < 2^{n-1} + 2^{n-2}. \]
Since:
\[ 2^{n-1} + 2^{n-2} = 2^{n-2}(2 + 1) = 3 \cdot 2^{n-2}, \]
and since \(3 < 4\), we obtain:
\[ 3 \cdot 2^{n-2} < 4 \cdot 2^{n-2} = 2^2 \cdot 2^{n-2} = 2^n. \]
Therefore:
\[ F_n < 2^n. \]
By the principle of strong induction, \(F_n < 2^n\) for every \(n \geq 1\).
This example illustrates well why strong induction is the natural choice here: the recurrence \(F_n = F_{n-1} + F_{n-2}\) involves the two preceding terms, not only the immediate predecessor. Using strong induction directly makes the argument more straightforward.
Common mistakes in inductive proofs
1. Forgetting the base case
Without the base case, the inductive step is not enough. Proving only:
\[ P(n) \Rightarrow P(n+1) \]
does not guarantee that the property holds for any natural number at all.
It is like saying that each tile knocks down the next, without ever toppling the first tile.
2. Misusing the inductive hypothesis
The inductive hypothesis must be used exactly in the form in which it was stated.
To prove a property \(P(n+1)\), one must start from \(P(n)\) and transform it correctly into the next case.
3. Proving an incomplete implication
The inductive step must hold for every value of \(n\) in the domain under consideration.
If the argument is valid only for some values of \(n\), the proof is not sound.
The horse paradox
A celebrated example of a flawed inductive proof is the so-called horse paradox.
One wishes to prove the following claim:
\[ P(n): \quad \text{in any set of } n \text{ horses, all horses have the same colour.} \]
For \(n = 1\), the property is true: in a set consisting of a single horse, all horses trivially share the same colour.
Now consider a set of \(n + 1\) horses:
\[ \{c_1, c_2, \dots, c_n, c_{n+1}\}. \]
The first \(n\) horses:
\[ \{c_1, c_2, \dots, c_n\} \]
all have the same colour, by the inductive hypothesis. Likewise, the last \(n\) horses:
\[ \{c_2, c_3, \dots, c_{n+1}\} \]
all have the same colour, again by the inductive hypothesis.
Since the two subsets overlap, it would seem to follow that all \(n+1\) horses share the same colour.
The error occurs in the step from \(n = 1\) to \(n = 2\). In that case the two subsets are:
\[ \{c_1\} \qquad \text{and} \qquad \{c_2\}, \]
which have no element in common. There is therefore no shared horse to link the colour of the first to the colour of the second.
The inductive step fails precisely for \(n = 1\), so the chain of implications breaks down at the very first link, i.e., in the passage from \(P(1)\) to \(P(2)\).
4. Confusing numerical verification with proof
Checking a formula for \(n = 1\), \(n = 2\), \(n = 3\), and \(n = 4\) may suggest that it is true, but it does not constitute a proof.
Induction does not consist of verifying many initial cases, but of establishing a general mechanism for passing from \(n\) to \(n+1\).
Induction and recursive definitions
The principle of induction is closely tied to recursive definitions.
Many mathematical objects are defined by specifying:
- one or more initial values;
- a rule that allows subsequent terms to be constructed.
For example, the factorial is defined by:
\[ 0! = 1 \]
and
\[ (n+1)! = (n+1)\, n!. \]
Recursion builds objects step by step, while induction allows us to prove properties that hold for all objects constructed in this way.
Recursion and induction are therefore two complementary aspects of the structure of the natural numbers: recursion defines, induction proves.
Conclusion
The principle of mathematical induction is far more than a technique for proving formulas. It expresses a fundamental property of the natural numbers: every natural number can be reached from the first one by repeatedly applying the successor operation.
Its power lies in reducing an infinite statement to two finite verifications:
- an initial verification;
- a rule for propagating the result from case \(n\) to case \(n+1\).
Moreover, the equivalence with the well-ordering principle reveals that induction is deeply rooted in the ordered structure of \(\mathbb{N}\).
For this reason, the principle of induction occupies a central role in algebra, number theory, logic, discrete mathematics, theoretical computer science, and many other branches of mathematics.
Ultimately, mathematical induction shows how it is possible to govern the infinite through finite reasoning, provided the logical structure is built with precision.