Skip to content

Mathematical Induction

On the terminology

The proof method or proof technique of mathematical induction is designed for proving statements about the natural numbers1 or, equivalently positive integers2. In this text, the set of natural numbers or the set of positive integers is defined as being the set \(\mathbb{N} = \mathbb{Z}^{+} = \{1, 2, 3, \dots \}\).

Although the terminology suggests otherwise, mathematical induction is actually a deductive process3. As we will see in the next two sections, induction and deduction are both forms of reasoning, but they are very different from one another.

Induction (not the mathematical proof method)

When using induction one distills a general principle or rule based on observations of specific instances, where in order not to be coincidental, the assumption has to be made based on a sufficiently large number of specific instances. For example, by observing that thousands of prime numbers are odd, one may conclude that all the prime numbers are odd - where in fact this is a false conclusion, since \(2\) is an even prime number (actually it is the only even prime number). And one such counterexample is enough to disproof the assumption that all the prime numbers are odd. In mathematics, inductive reasoning in this broader sense is actually not used as a proof method. It's used to formulate assumptions and conjectures instead. Conjectures of this type are suggested by observation, indicated by particular instances4. Hence, as George Pólya states it, the role of inductive evidence in mathematical investigation is similar to its role in physical research5.

Deduction

On the other hand, when deducing, one infers a conclusion starting from general principles by using logic. For example the conclusion that the sum of two even integers is always even may be proved as follows:

Let \(m\) and \(k\) be two even integers. An even integer is a number that is divisible by \(2\) without remainder. Let therefore \(m = 2n\) and \(k = 2j\), where \(n\) and \(j\) are some integers. Now, by adding \(m\) and \(k\) we get \(m + k = 2n + 2j\) (by substitution). By basic algebra we then can factor out \(2\) from the expression \(2n + 2j\), which gives \(2(n + j)\). Now, let \(T = (n + j)\). Sums of integers are also integers, hence, given the fact that \(n\) and \(j\) are integers, \(T\) is also an integer. Again, by substitution we get \(m + k = 2T\), which means that the sum of \(m\) and \(k\) is even. \(\square\)

With this proof we have shown that the initial statement, that the sum of two even integers is always even, is valid. Once proved, a statement cannot be disproved by let's say, a counterexample, as was the case with the inductive reasoning described in the section Induction (not the mathematical proof method).

The terminology becomes clearer with an addition

To distinguish the proof method used in mathematics from the looser concept of induction described in Induction (not the mathematical proof method), it is often called mathematical induction or complete induction6. Actually it was Augustus de Morgan who gave the process the name complete induction7. In his book on formal logic he states that: "Complete induction is demonstration, and strictly syllogistic in its character"8. With this additions a clearer distinction is made between the looser concept of induction and the mathematical proof method. But be aware of the fact, that within the mathematical literature variations of the main proof method may be called differently. For example, complete induction is sometimes used to denote the variation of the mathematical induction with the usage of a stronger hypothesis and is therefore also called strong induction9 or strong mathematical induction10. In order to distinguish the basic form of mathematical induction from strong mathematical induction, the former is sometimes referred to as weak induction11. In the present text, we will only refer to mathematical induction in its basic variation and simply call it mathematical induction.

Historical Notes

Mathematical induction has been implicitly used already in Euclid‘s proof of the infinitude of the prime numbers12, but entered algebra explicitly only in the late sixteenth century with the work Arithmetica of 1575 of Francesco Maurolico13. In 1654 Blaise Pascal in his Traité du Triangle Arithmétique14 gave a clear description15, where he used it to prove properties of the binomial coefficients16.

Mathematical or complete induction appears also in logically equivalent forms, such as the well-ordering principle17, which states that every nonempty subset of \(\mathbb{Z}^{+}\) has a smallest element; that is, if \(S\) is a nonempty subset of \(\mathbb{Z}^{+}\), then there exists \(a \in S\) such that \(a \leqslant x\) for all \(x \in S\)18. We will come back to the well-ordering principle shortly.

The actual proof technique of mathematical induction

The key idea

Suppose that we want to prove that every positive integer, that is \(1, 2, 3, \dots\), has the same property we call \(P\); we obviously can't check them all, one-by-one, because there are infinitely many positive integers19. What do we do instead? Mathematical induction enables us to carry out such a task in only a finite number of steps20. We can show that the first positive integer \(1\) has the property \(P\), and that whenever we add \(1\) to a number that has property \(P\), the resulting number we get also has property \(P\)21. In this way we actually have proved infinitely many theorems22. With the above mentioned well-ordering principle one can derive the first principle of finite induction, which provides a basis for mathematical induction23.

Theorem 1 (first principle of finite induction)

Let \(S\) be a set of positive integers (\(S \subseteq \mathbb{Z}^{+}\)) with the following properties:

  1. The integer 1 belongs to \(S\), that is \(1 \in S\).
  2. For each \(k \in S\) with \(k \geqslant 1\), the next integer \(k + 1\) must also be in \(S\).

If these two properties are met, then \(S\) is the set of all positive integers24, that is \(S=\mathbb{Z}^{+}\).

Now, if for some property \(P\) we have \(S = \{x \in \mathbb{Z}^{+}| P(x)\}\), we get the principle of mathematical induction based on the first principle of finite induction25:

Theorem 2 (principle of mathematical induction)

If \(\{P(i)\}\) is a set of statements such that:

  1. \(P(1)\) is true (\(\textit{basis step}\)) and
  2. for each \(i \geqslant 1\), if \(P(i)\) is true (induction hypothesis) then \(P(i + 1)\) is also true (induction step),

and hence \(P(k)\) is true for all positive integers \(k\)26.

Let \(S\) be the set of all integers \(n \geqslant 1\) such that \(P(n)\) is true, and let \(T\) be the set of all integers \(k > 1\) such that \(P(k)\) is false. We suppose that \(T\) is not empty (\(T \neq \emptyset\)).

Then by the above mentioned well-ordering principle, \(T\) must have a smallest element, which we denote by \(k_{0}\). Because \(1\) is in \(S\), certainly \(k_{0} > 1\), and so \(0 < k_{0} - 1 < k_{0}\); where the choice of \(k_{0}\) as the smallest positive integer in \(T\) implies that \(k_{0}-1\) is not an element of \(T\), or equivalently, that \(k_{0} -1\) belongs to \(S\) (\(k_{0}-1 \in S\))27. But this means that \(P(k_{0}-1)\) is true, since \(k_{0}-1 \geqslant 1\). Knowing that \(P(k_{0} - 1)\) is true and that if \(P(k_{0}-1)\) is true, due to \(k_{0}-1 \geqslant 1\), also \(P(k_{0}-1 + 1) = P(k_{0})\) must be true. But eventually the conclusion that \(P(k_{0})\) is true contradicts our initial assumption that \(k_{0}\) was in \(T\), and hence \(k_{0} \notin T\). Therefore we must conclude that \(T\) is indeed empty (\(T = \emptyset\)). Where the set \(S\) on the other hand has the following properties: \(S = \{n \in \mathbb{Z}^{+} \;|\; n \geqslant 1\}\) and \(P(n)\) is true for all positive integers \(n\)28.\(\square\)

A classical example

For all positive integers \(n \in \mathbb{Z}^{+}\),

\((1)\) \(\quad\) \(\sum_{i = 1}^{n} i= \frac{n(n+1)}{2}\).

Proof. We assume that the equation \((1)\) has the property \(P(n)\). As we have seen in theorem \(2\), we first have to show that \(P(n)\) is true for \(n = 1\). We will do this computationally, by replacing \(n\) with \(1\) in the equation \((1)\) getting \(P(1)\). The left-hand side (LHS) of \(P(1)\) is then:

\((2)\) \(\qquad\) \(\sum_{i = 1}^{1} i = 1\).

The right-hand side (RHS) of \(P(1)\) will be

\((3)\) \(\qquad\) \(\frac{1(1+1)}{2} = \frac{1 \cdot 2}{2} = \frac{2}{2} = 1\).

Now, because LHS \(=\) RHS, we conclude that \(P(1)\) is true.

We now suppose that if \(P(k)\) is true for an arbitrary but fixed integer \(k \geqslant 1\) such that

\((4)\) \(\qquad\) \(\sum_{i=1}^{k} i = \frac{k(k+1)}{2}\), \(\qquad\)(induction hypothesis)

then \(P(k + 1)\) also is true (induction step). We prove this by replacing \(k\) in the equation \((4)\) with \((k + 1)\) and we get

\((5)\) \(\qquad\) \(\sum_{i=1}^{k} i + (k + 1) = \sum_{i = 1}^{k + 1} i = \frac{(k + 1)[(k + 1) + 1]}{2}\).

Now, by basic algebra this gives:

\((6)\) \(\qquad\) \(\sum_{i=1}^{k + 1} i = \frac{(k + 1)(k + 2)}{2}\).

Similarly, as we already did within the basis step, we have to show now that the LHS and the RHS of \(P(k + 1)\) are equal to each other. Starting from \(P(k)\), the equation \((4)\), we get the LHS of \(P(k + 1)\), that is:

\((7)\) \(\qquad\) \(\underbrace{(1 + 2 + 3 + \cdots + k)} + \underbrace{(k + 1)} =\)

\((8)\) \(\qquad\) \(= \qquad \frac{k(k+1)}{2} \qquad + \quad (k + 1),\)

which by basic algebra leads us to

\((9)\) \(\qquad\) \(= \frac{k(k+1)}{2} + \frac{2(k+1)}{2},\)

\((10)\) \(\qquad\) \(= \frac{k^{2} + k}{2} + \frac{2k + 2}{2},\)

\((11)\) \(\qquad\) \(= \frac{k^{2} + 3k + 2}{2}\).

The RHS of \(P(k + 1)\) is

\((12)\) \(\qquad\) \(\frac{(k+1)(k+2)}{2} = \frac{k^{2} + 3k + 2}{2}\),

and we get LHS \(=\) RHS.

Hence, \(P(k + 1)\) is true for all \(k \geqslant 1\), that is, the equation \((1)\) holds also for \(n = (k + 1)\). We therefore can conclude that by the principle of mathematical induction, \((1)\) is true for all integers \(n \geqslant 1\). \(\square\)

Final Remarks

We have shown that \(P(k + 1)\) follows immediately form \(P(k)\) and that it is true for all \(k \geqslant 1\). By knowing that \(P(1)\) is true, we can conclude that also \(P(2)\) is true. Because we know that \(P(2)\) is true, we know that \(P(3)\) is true, and so on. Therefore \(P(n)\) is true for all integers \(n \geqslant 1\), and we must conclude that the theorem that states that for every integer \(n \geqslant 1\),

\((13)\) \(\qquad\) \(\sum_{i=1}^{n} i = \frac{n(n+1)}{2}\)

is true.

  1. D. J. Velleman, How to prove it: a structured approach, third edition, New York 2019, p. 273. ↩

  2. D. M. Burton, Elementary number theory, fifth edition, Boston 2002, p. 1. ↩

  3. S. S. Epp, Discrete mathematics: with applications, fifth edition, Australia 2020, p. 275. ↩

  4. G. Pólya, Mathematics and plausible reasoning, Vol. 1, Induction and analogy in mathematics, Princeton, New Jersey 1954, p. 5. ↩

  5. J. Stillwell, The story of proof: logic and the history of mathematics, Princeton, New Jersey 2022, p. vii. ↩

  6. J. Stillwell, The story of proof: logic and the history of mathematics, Princeton, New Jersey 2022, p. 186. ↩

  7. S. S. Epp, Discrete mathematics: with applications, fifth edition, Australia 2020, p. 275. ↩

  8. A. De Morgan, Formal logic: the calculus of inference, necessary and probable, Honolulu, Hawaii 2003, p. 211. ↩

  9. E. Gosset, Discrete mathematics with proof, Prentice Hall, Upper Saddle River, New Jersey 2003, p. 125. ↩

  10. S. S. Epp, Discrete mathematics: with applications, fifth edition, Australia 2020, p. 301. ↩

  11. E. Gosset, Discrete mathematics with proof, Prentice Hall, Upper Saddle River, New Jersey 2003, p. 118. ↩

  12. J. Stillwell, The story of proof: logic and the history of mathematics, Princeton, New Jersey 2022, p. 31 and 186. ↩

  13. M. Kline, Mathematical thought from ancient to modern times, New York 1990, p. 272. ↩

  14. T. Gowers, The Princeton companion to mathematics, Princeton 2008, p. 741. ↩

  15. S. S. Epp, Discrete mathematics: with applications, fifth edition, Australia 2020, p. 277. ↩

  16. J. Stillwell, The story of proof: logic and the history of mathematics, Princeton, New Jersey 2022, p. 186. ↩

  17. J. Stillwell, The story of proof: logic and the history of mathematics, Princeton, New Jersey 2022, p. 186-187. ↩

  18. R. J. Bond and W. J. Kean, An introduction to abstract mathematics, Pacific Grove, California 1999, p. 155. ↩

  19. D. J. Velleman, How to prove it: a structured approach, third edition, New York 2019, p. 273. ↩

  20. L. J. Gerstein, Introduction to mathematical structures and proofs, New York, Sadbury, Massachussets 1996, p. 102. ↩

  21. D. J. Velleman, How to prove it: a structured approach, third edition, New York 2019, p. 273. ↩

  22. L. J. Gerstein, Introduction to mathematical structures and proofs, New York, Sadbury, Massachussets 1996, p. 102. ↩

  23. D. M. Burton, Elementary number theory, fifth edition, Boston 2002, p. 2. ↩

  24. D. M. Burton, Elementary number theory, fifth edition, Boston 2002, p. 2. ↩

  25. L. J. Gerstein, Introduction to mathematical structures and proofs, New York, Sadbury, Massachussets 1996, p. 104. ↩

  26. E. Gosset, Discrete mathematics with proof, Prentice Hall, Upper Saddle River, New Jersey 2003, p. 117. ↩

  27. D. M. Burton, Elementary number theory, fifth edition, Boston 2002, p. 2. ↩

  28. E. Gosset, Discrete mathematics with proof, Prentice Hall, Upper Saddle River, New Jersey 2003, p. 117. ↩