Mathematical induction
An excerpt from Proof and the Art of Mathematics
This is a free extended excerpt from chapter 4 of my book Proof and the Art of Mathematics, an introduction to the art and craft of proof-writing, for aspiring mathematicians who want to learn how to write proofs.
Proof and the Art of Mathematics teaches the art of proof-writing in the diverse contexts of a variety of mathematical subjects, but always with mathematical theorems and statements that carry their own inherent interest and fascination—compelling mathematical results with interesting, elementary proofs.
The principle of mathematical induction lies at the core of number theory and mathematics generally, serving as a powerful unifying central principle in axiomatic developments of the subject, the main engine used to prove essentially all of the fundamental facts of arithmetic and more. So let us explore this core principle a little more fully. We have already begun to use it informally in the previous chapters.
The least-number principle
The core idea of induction is expressed by the following axiomatic principle:
Least-number principle. If there is a natural number with a certain property, then there is a smallest number with that property.
Equivalently, every nonempty set A of natural numbers has a least element. This principle asserts that the natural numbers are well-ordered, for a well-order is one for which every nonempty set has a least member.
The reader may have noticed that we made use of this principle in several previous arguments. We used it, for example, in chapter 1 in the revised proof that √2 is irrational, when we chose the numerator to be as small as possible, and we also used it in the proof that every rational number can be placed into lowest terms. We used the least-number principle again in the geometric proof that √2 is irrational, when we took the integer-sided squares to be as small as possible for which one had double the area of another, and we used it when proving the Euclidean algorithm and when proving the fundamental theorem of arithmetic. So although this chapter is titled, “Mathematical Induction,” in fact we have already been making inductive arguments in the earlier chapters without saying so.
One should not think of mathematical induction as an obscure proof method used only to prove certain curious recursive sums. Rather, mathematical induction is a fundamental principle, a bedrock idea upon which all the basic facts of number theory rest. In the axiomatic developments of number theory from first principles, such as in the Peano or Dedekind axiomatizations, for example, the principle of mathematical induction is used in almost every fundamental proof.
Common induction
In mathematical practice, elementary applications of induction often make use of certain idiosyncratic formulations of the least-number principle. Perhaps the most common formulation of the induction principle in elementary arguments is the following:
Theorem (Common induction principle). Suppose that A is a set of natural numbers for which 0 ∈ A, and furthermore, whenever n ∈ A, then also n + 1 ∈ A. Then every natural number is in A.
Another way to express the principle is that if 0 has a certain property, and the property is necessarily propagated from each natural number n to the next number n + 1, then indeed every natural number has the property.
The notation x ∈ A appearing in the principle here means that x is an element of the set A. The claim that 0 ∈ A is commonly referred to as the anchor of the induction, and the implication n ∈ A ⇒ n + 1 ∈ A is called the induction step. Because of the anchor, we know 0 is in the set. By applying the induction step to that case, we see that 1 also is in the set. And by applying the induction step to that case, we see that 2 is in the set, and so on. Each number in the set causes the next number to be in the set. Like a train of dominoes, every number falls in turn into the set.
The first domino is pushed, and each falling domino causes the next to fall; in the end, of course, every domino falls. This image might help us see the fundamental correctness of the common induction principle; we shall nevertheless later prove the principle, using the least-number principle, and this is why I have stated the common induction principle as a theorem rather than as an axiom.
Alternative formulations of the common induction principle allow you to anchor the induction at a number other than 0. For example, if A is a set of integers for which 1 ∈ A, and furthermore, whenever n ∈ A then also n + 1 ∈ A, then every positive integer n ≥ 1 is in A. We could also anchor the induction at 5, or at -3, or whatever, and conclude that all numbers from this anchor and above n ≥ 5 are in the set. You will be asked to prove this in the exercises. The principle of mathematical induction is robust and takes many useful forms.
Several proofs using induction
Before proving the common induction principle, let us first get a little practice using it. Consider the triangular numbers, which are the numbers of the form 1 + 2 + 3 + ··· + n. These numbers are called triangular because this many objects can be arranged in the form of a triangle, as pictured here, where one adds one more layer each time as n increases.
Theorem. The sum of the first n positive integers is n(n + 1)/2, for any positive integer n. In other words,
Thus, the nth triangular number is n(n + 1)/2.
Proof. We prove the theorem by common induction. The statement is true at the anchor n = 1, since 1 = 1(1 + 1)/2, so the number 1 is in the set of numbers for which the statement is true. Consider now the induction step. We assume that the statement is true for a number n and consider n + 1. Since the statement was true for the number n, we know that 1 + 2 + ··· + n = n(n + 1)/2. If we now add n + 1 to both sides of this equation and apply some elementary algebra, we see that
This is exactly what it means for the statement to be true in the case of n + 1, so we have proved that if the statement is true for n, then it is also true for n + 1. Therefore, we conclude by the principle of induction that the statement is true for all positive integers. ☐
We could have anchored the induction at n = 0 rather than n = 1, because the statement is also true for n = 0, as the sum of the first zero many positive integers is zero, which is equal to 0 · 1/2. In light of this, instead of stating the theorem as “for every positive integer n,” we could have stated the theorem as “for any natural number n.”
Theorem. The sum of the first n odd numbers is n2, for any natural number n. In other words,
Proof. Let us prove the theorem by common induction. The statement is easy to see when n = 1, since 1 = 12. But again, we may actually take n = 0 as the base case in the original statement, since the sum of the first zero many odd numbers is 0, since there are not any, and 02 = 0 as well, so it is true for n = 0. (Perhaps the case n = 0 is a little confusing in the case of the displayed equation, however, since perhaps it is not clear what the left side is supposed to indicate when n = 0. To my way of thinking, though, the only sensible interpretation of the left-side expression when n = 0 is that there are no terms in it at all, giving a sum of 0, which is indeed precisely what we want.) For the induction step, assume that the statement is true for a number n, and consider n + 1. Since the statement is true for n, we know that 1 + 3 + 5 + ··· + (2n - 1) = n2. If we add 2(n + 1) - 1 to both sides, which is the same as 2n + 1, we get 1 + 3 + 5 + ··· + (2n + 1) = n2 + 2n + 1, and this further simplifies to (n + 1)2. Thus, the statement is true for n + 1. So we have proved that the statement is true at the anchor, and the truth propagates from each number n to n + 1. So by the principle of induction, we conclude that the statement is true for every positive integer. ☐
We shall have an alternative proof of the theorem in a later chapter, entitled Proofs Without Words.
Theorem. The sum of the powers of 2 up to 2n is 1 less than the next power of 2. In other words,
Proof. We prove the theorem by common induction. The statement is true for n = 0, since 1 = 21 - 1. Assume that the statement is true for a number n, and consider n + 1. Since the statement was true for n, we have
By adding 2n+1 to both sides, we get
which is equal to
which is what is desired for the case of n + 1. So the statement is true for all n by induction. ☐
The Fibonacci sequence is the sequence
Can you see the pattern? The sequence starts out with zero and one and then each next number is the sum of the previous two. We can therefore describe the sequence by the following recursive rules:
Theorem. The Fibonacci numbers obey the following identity:
Proof. We prove the theorem by common induction. The statement is true for n = 0, since (f0)2 = 0 = 0 · 1 = f0 f1. Assume that the statement is true for a number n, and consider n + 1. Since the statement is true for n, we have
Let us add (fn+1)2 to both sides, concluding that
which is equal to
By applying the recursive definition, this is equal to fn+2 fn+1. So we have established that
and so the statement is true for n + 1. Thus, by induction, it is true for all natural numbers n. ☐
An alternative visual proof of this identity will be given in the chapter on proofs without words.
Theorem. The number 6n - 1 is a multiple of 5 for every natural number n.
Proof. We prove the theorem by common induction. The statement is true when n = 0. Suppose by induction that the statement is true for a number n, and consider n + 1. Since 6n - 1 is a multiple of 5, we have 6n - 1 = 5k for some integer k. In other words, 6n = 5k + 1. Multiplying both sides by 6, we see that 6n+1 = 6(5k + 1) = 30k + 6, and consequently, 6n+1 - 1 = 30k + 5 = 5(6k + 1), which is a multiple of 5. So the statement is true for n + 1, and we have thereby proved by induction that the statement holds for all natural numbers. ☐
The previous theorem can also be easily proved with modular arithmetic, for those who are familiar with it, because 6 modulo 5 is 1, and so the expression 6n - 1 is equivalent to 1n - 1 mod 5, which is 0 mod 5. Thus, 6n - 1 is a multiple of 5.
Theorem. The number n3 - n is a multiple of 6, for every natural number n.
Proof. We prove the theorem by common induction. The statement is true when n = 0, since 03 - 0 = 0, and this is a multiple of 6. Suppose by induction that the statement is true for a number n. So n3 - n is a multiple of 6. Observe that
The number n(n + 1) is always even, since either n or n + 1 is even (as with the arguments of chapter 2), and so 3n(n + 1) is a multiple of 6. So the next number (n + 1)3 - (n + 1) arises from the previous number n3 - n by adding a multiple of 6. So if the previous number was a multiple of 6, then so will be the next number. So the statement is true for n + 1, and we have thereby proved by induction that the statement is true for all natural numbers. ☐
This statement was also proved without induction in the exercises of chapter 2.
Theorem. The inequality n2 < 3n holds for every natural number.
Proof. We prove the theorem by common induction. First, the statement is easy to verify in the cases n = 0, n = 1, and n = 2, as the reader may easily check. Assume by induction that the statement is true for a number n, and consider n + 1. Since we have verified the claim up to 2 already, we may also assume that 2 ≤ n. Since the statement is true for this number n, we know that n2 < 3n. Using the fact that 2 ≤ n, we may argue with the following chain of inequalities:
And so the statement is true for n + 1. Thus, by mathematical induction, it holds for all natural numbers. ☐
I should like to call attention to the fact that in the proof of the theorem we made at first what might appear to be three different anchor cases, considering not only n = 0 but also n = 1 and n = 2. Why did we do this? Could we have skipped that part? Although with common induction one generally needs only one anchor, in this particular argument we actually needed those extra cases, because the argument we gave in the induction-step part of the proof began to work only once 2 ≤ n. One way to think about it is that we just established the cases n = 0 and n = 1 separately, but the real anchor was n = 2, since the induction step of the argument works only for 2 ≤ n.
Proving the induction principle
So we have stated the common induction principle, and we have used it in a few arguments. But can we prove the principle itself? Yes, in fact it is easy to prove the common induction principle from the least-number principle.
Proof of common induction principle. We prove the common induction principle using the least-number principle. Assume that A is an inductive set of natural numbers, which means that 0 ∈ A and whenever n ∈ A, then also n + 1 ∈ A. We want to prove that every number is in A. If not, then there must be some numbers not in A, and by the least-number principle there must therefore be a smallest number that is not in A. Let us call this number m. The assumption on A ensures that m ≠ 0. Consequently, m ≥ 1, and so m - 1 is a natural number. Since m - 1 is smaller than m and m is the smallest number not in A, it must be that m - 1 is in A. Therefore, by the induction assumption on A, it follows that (m - 1) + 1 is also in A. But this is m itself, and so m is in A after all, contradicting our earlier assumption that it was not. So A must contain every natural number. ☐
Strong induction
Although the common induction principle is indeed quite common, there are sometimes situations where one wants to prove something by induction, but the induction implication goes naturally not from n to n + 1 but, rather, from some other smaller number to n + 1, or from several smaller numbers. In these cases, the following stronger formulation of the induction principle is useful.
Theorem (Strong induction principle). Assume that A is a set of natural numbers with the property that, for every natural number n, if every number smaller than n is in A, then n itself is in A. Then every natural number is in A.
One thing to notice about the strong induction formulation is that it has no anchor case! How can this induction principle be correct? But it is correct, I assure you, and the reason has to do with what is called vacuous truth. Specifically, in the case n = 0, there are no natural numbers smaller than n, and so it is vacuously true that all such numbers are in A, since this assertion can have no counterexample. So the strong induction assumption vacuously implies that 0 ∈ A, and the induction engine is thereby started.
Proof. This argument is similar to the proof of the common induction principle from the least-number principle. Namely, assume that A satisfies the strong induction property mentioned in the strong induction principle. If not every natural number is in A, then there would be some least natural number n that is not in A. But in this case, every number smaller than n would be in A and so n itself would have to be in A after all, by the strong induction assumption on A. This contradicts our assumption on n, and so there cannot be any natural numbers not in A. In other words, every natural number must be in A, as desired. ☐
Several of our informal uses of mathematical induction that we gave in chapter 3 had essentially used strong induction. For example, to prove that every positive integer has a prime factorization, you suppose that every number smaller than n has such a factorization and then observe that either n is prime, in which case it is its own factorization, or else n = ab for smaller numbers a,b < n, which by the induction assumption have prime factorizations, which can be put together to make a prime factorization of n. In this argument, you see, we did not move from n to n + 1 but, rather, reduced the problem on n to instances of the problem for smaller numbers a and b. Several of the other results in chapter 3 can similarly be set out as proofs by strong induction.
Let us now give a few more applications of the principle of induction. Consider the case of binary representation of numbers. Perhaps you know that the number 6 is represented in binary as 110, since 6 = 4 + 2, and the number 19 is represented as 10011, since 19 = 16 + 2 + 1. Perhaps you know that every natural number has a binary representation. But how could we prove this? Furthermore, how do we know that different binary representations always represent different numbers?
Theorem. Every natural number can be expressed as the sum of a unique set of distinct powers of 2.
Proof. Assume by strong induction that the statement is true for all numbers smaller than n. Since 0 is the empty sum, we may assume that n ≥ 1. Let 2k be the largest power of 2 that fits inside n, so that 2k ≤ n. Since n - 2k is smaller than n, it has a unique representation as a sum of distinct powers of 2. Note that 2k cannot appear in the sum for n - 2k, since otherwise n would be at least 2k + 2k = 2k+1, but we had chosen 2k to be the largest power of 2 that fits inside n. Thus, by adding 2k to the sum for n - 2k, we obtain n as a sum of distinct powers of 2, establishing the existence claim of the theorem. For uniqueness, note that 2k must occur in any representation of n as a sum of distinct powers of 2, since no larger powers ever occur by the choice of k, and if we use only smaller powers, then even if we use all of them the sum will be at most 1 + 2 + 4 + ··· + 2k-1, which by an earlier theorem is less than 2k and so therefore cannot sum to n. So 2k is used in every representation of n as a sum of powers of 2, and the uniqueness claim therefore follows from the uniqueness of the representation of n - 2k. ☐
Corollary. Every natural number has a unique binary representation.
Proof. Every natural number has a unique binary representation, since the binary representation is simply a convenient compact notation for indicating which powers of 2 one is including in the sum, and by the previous theorem this collection is unique. ☐
For example, the binary number 101101 is a compact notation for the sum
which is 45 in decimal notation.
Continue reading more about this topic in the book itself: