3.4. Mathematical Induction#

The structure of the natural numbers—0, 1, 2, 3, and on to infinity—makes possible a powerful proof technique known as induction or mathematical induction. Although the idea behind induction is simple, students often struggle with it. Take your time and study this material thoroughly! You will have opportunity to practice in the labs after we discuss induction in the lectures.

../../_images/dominos.png

Let \(P\) be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that we can prove that \(P(0)\) is true. Suppose that we can also prove the statements \(P(0)\rightarrow P(1)\), \(P(1)\rightarrow P(2)\), \(P(2)\rightarrow P(3)\), and so on. The principle of mathematical induction is the observation that we can then conclude that \(P(n)\) is true for all natural numbers \(n\). This should be clear. It’s like a line of dominos, lined up and ready to fall, one after the next.[1]

Since \(P(0)\) and \(P(0)\rightarrow P(1)\) are true, we can apply the rule of modus ponens to conclude that \(P(1)\) is true. Then, since \(P(1)\) and \(P(1)\rightarrow P(2)\) are true, we can conclude by modus ponens that \(P(2)\) is true. From \(P(2)\) and \(P(2)\rightarrow P(3)\), we conclude that \(P(3)\) is true. For any given \(n\) in the set \(\mathbb{N}\), we can continue this chain of deduction for \(n\) steps to prove that \(P(n)\) is true.

When applying induction, we don’t actually prove each of the implications \(P(0)\rightarrow P(1)\), \(P(1)\rightarrow P(2)\), and so on, individually. That would require an infinite amount of work. The whole point of induction is to avoid any infinitely long process. Instead, we prove \(\forall k\,(P(k)\rightarrow P(k+1))\) (where the domain of discourse for the predicate \(P\) is \(\mathbb{N}\). The statement \(\forall k\,(P(k)\rightarrow P(k+1))\) summarizes all the infinitely many implications in a single statement. Stated formally, the principle of mathematical induction says that if we can prove the statement \(P(0)\wedge \big(\forall k\,(P(k)\rightarrow P(k+1)\big)\), then we can deduce that \(\forall n\,P(n)\) (again, with \(\mathbb{N}\) as the domain of discourse).

Video

Khan Academy offers a video with a clear explanation of mathematical induction: www.khanacademy.org/math/algebra-home/alg-series-and-induction/alg-induction/v/proof-by-induction. We highly recommend that you watch it to also hear this information from another perspective.

3.4.1. How to write a proof by induction#

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)\rightarrow 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:

Theorem 3.3

Let \(P\) be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that \(P(0)\wedge \big(\forall k\in\mathbb{N}\,(P(k)\rightarrow P(k+1))\big)\).[2] Then \(P(n)\) is true for all natural numbers \(n\). (That is, the statement \(\forall 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 \(\forall k\,(P(k)\rightarrow P(k+1))\) is proved. This statement can be proved by letting \(k\) be an arbitrary element of \(\mathbb{N}\) and proving \(P(k)\rightarrow 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 the induction hypothesis. Note that the base case is just as important as the inductive case. By itself, the truth of the statement \(\forall k\,(P(k)\rightarrow P(k+1))\) says nothing at all about the truth of any of the individual statements \(P(n)\). The chain of implications \(P(0)\rightarrow P(1)\), \(P(1)\rightarrow P(2)\), … , \(P(n-1)\rightarrow P(n)\) says nothing about \(P(n)\) unless the chain is anchored at the other end by the truth of \(P(0)\).

3.4.2. Examples#

Let’s look at a few examples.

Theorem 3.4

The number \(2^{2n}-1\) is divisible by 3 for all natural numbers \(n\).

Proof. Here, \(P(n)\) is the statement that \(2^{2n}-1\) is divisible by 3.

Base case: When \(n=0\), \(2^{2n}-1 = 2^0-1=1-1=0\) and \(0\) is divisible by 3 (since \(0=3\cdot 0\).) Therefore the statement holds when \(n=0\).

Inductive case: We want to show that if the statement is true for \(n=k\) (where \(k\) is an arbitrary natural number), then it is true for \(n=k+1\) also. That is, we must prove the implication \(P(k) \rightarrow P(k+1)\). So we assume \(P(k)\), that is, we assume that \(2^{2k}\) is divisible by 3. This means that \(2^{2k} -1 = 3m\) for some integer \(m\). We want to prove \(P(k+1)\), that is, that \(2^{2(k+1)}-1\) is also divisible by 3:

\[\begin{split}\begin{align*} 2^{2(k+1)}-1 &= 2^{2k+2}-1 &\\ &= 2^{2k}\cdot2^2 - 1 &\text{properties of exponents}\\ &= 4\cdot 2^{2k} -1 \\ &= 4\cdot 2^{2k} -4 + 4 -1 \\ &= 4(2^{2k} -1) + 3 &\text{algebra} \\ &= 4(3m) + 3 & \text{the inductive hypothesis}\\ &= 3(4m+1) & \text{algebra} \end{align*}\end{split}\]

and from the last line we see that \(2^{2k+1}\) is in fact divisible by 3. (The third step—subtracting and adding 4—was done to enable us to use our inductive hypothesis.)

Altogether, we have proved that \(P(0)\) holds and that, for all \(k\), \(P(k) \rightarrow P(k+1)\) is true. Therefore, by the principle of induction, \(P(n)\) is true for all \(n\) in \(\mathbb{N}\), i.e. \(2^{2n}-1\) is divisible by 3 for all \(n\) in \(\mathbb{N}\).

□

The principle of mathematical induction gives a method for proving \(P(n)\) for all \(n\) in the set \(\mathbb{N}\). It should be clear that if \(M\) is any natural number, a similar method can be used to show that \(P(n)\) is true for all natural numbers \(n\) that satisfy \(n\ge M\). Just start the induction with a base case of \(n=M\) instead of with a base case of \(n=0\). We leave the proof of this extension of the principle of induction as an exercise. We can use the extended principle of induction to prove a result that was first mentioned in Section 2.1.

Theorem 3.5

Suppose that a compound proposition contains exactly \(n\) propositional variables, where \(n\ge 1\). Then there are exactly \(2^n\) different ways of assigning truth values to the \(n\) variables.

Proof. Let \(P(n)\) be the statement ‘’There are exactly \(2^n\) different ways of assigning truth values to \(n\) propositional variables.’’ We will use induction to prove the \(P(n)\) is true for all \(n\ge1\).

Base case: First, we prove the statement \(P(1)\). If there is exactly one variable, then there are exactly two ways of assigning a truth value to that variable. Namely, the variable can be either true or false. Since \(2=2^1\), \(P(1)\) is true.

Inductive case: Suppose that \(P(k)\) is already known to be true. We want to prove that, under this assumption, \(P(k+1)\) is also true. Suppose that \(p_1\), \(p_2\), … , \(p_{k+1}\) are \(k+1\) propositional variables. Since we are assuming that \(P(k)\) is true, we know that there are \(2^k\) ways of assigning truth values to \(p_1\), \(p_2\), … , \(p_k\). But each assignment of truth values to \(p_1\), \(p_2\), … , \(p_k\) can be extended to the complete list \(p_1\), \(p_2\), … , \(p_k\), \(p_{k+1}\) in two ways. Namely, \(p_{k+1}\) can be assigned the value true or the value false. It follows that there are \(2\cdot 2^k\) ways of assigning truth values to \(p_1\), \(p_2\), … , \(p_{k+1}\). Since \(2\cdot2^k=2^{k+1}\), this finishes the proof.

□

3.4.3. More examples#

The sum of an arbitrary number of terms is written using the symbol \(\sum\). (This symbol is the Greek letter sigma, which is equivalent to the Latin letter S and stands for ‘sum’.) Thus, we have

\[\begin{split}\begin{align*} &\sum_{i=1}^5 i^2 = 1^2+2^2+3^2+4^2+5^2\\ &\sum_{k=3}^7 a_k = a_3+a_4+a_5+a_6+a_7\\ &\sum_{n=0}^N \frac{1}{n+1} = \frac{1}{0+1}+\frac{1}{1+1}+\frac{1}{2+1}+\cdots+\frac{1}{N+1}\\ \end{align*}\end{split}\]

This notation for a sum, using the \(\sum\) operator, is called summation notation. A similar notation for products uses the symbol \(\prod\). (This is the Greek letter pi, which is equivalent to the Latin letter P and stands for ‘product’.) For example,

\[\begin{split}\begin{align*} &\prod_{k=2}^5 (3k+2) = (3\cdot 2+2)(3\cdot 3+2)(3\cdot 4+2)(3\cdot 5+2)\\ &\prod_{i=1}^n \frac{1}{i} = \frac{1}{1}\cdot \frac{1}{2}\cdots \frac{1}{n}\cdot \end{align*}\end{split}\]

Induction can be used to prove many formulas that use these notations. Here are two examples:

Theorem 3.6

\(\displaystyle \sum_{i=1}^n\, i=\frac{n(n+1)}{2}\) for any integer \(n\) greater than zero.

We’ll prove this theorem in class. Can you do it yourself?

Person

../../_images/gauss.jpg

The summation of Theorem 3.6 is often attributed to mathematician and physicist Carl Friedrich Gauss (1777–1855). Gauss has been exceptionally influential in a variety of fields; he is called ‘’the greatest mathematician since antiquity’’. For example, you might have heard of the Gaussian probability distribution, or perhaps of the Gauss unit for magnetic flux (although we now commonly use the Tesla for that, with 1 Tesla equalling 10\(^5\) Gauss). His brilliance was already apparent in primary school when he allegedly used the ‘Gauss sum’ from Theorem 3.6 to solve the maths homework the teacher had set the class—to great astonishment of the teacher. You will see this summation again in the course Algorithms & Data Structures when analysing the runtime of algorithms containing loops.

Source: en.wikipedia.org/wiki/Carl_Friedrich_Gauss.

Theorem 3.7

\(\displaystyle \sum_{i=1}^n\,i2^{i-1}=(n-1)\cdot2^n+1\) for any natural number \(n>0\).

Proof. Let \(P(n)\) be the statement \(\displaystyle \sum_{i=1}^n\,i2^{i-1}=(n-1)\cdot2^n+1\). We use induction to show that \(P(n)\) is true for all \(n>0\)

Base case: Consider the case \(n=1\). \(P(1)\) is the statement that \(\displaystyle \sum_{i=1}^1\,i2^{i-1}=(1-1)\cdot2^1+1\). Since each side of this equation is equal to one, this is true.

Inductive case: Let \(k \geq 1\) be arbitrary, and assume that \(P(k)\) is true. We want to show that \(P(k+1)\) is true. \(P(k+1)\) is the statement \(\displaystyle \sum_{i=1}^{k+1}\,i2^{i-1}=((k+1)-1)\cdot2^{k+1}+1\). But, we can compute that

\[\begin{split}\begin{align*} \sum_{i=1}^{k+1}\,i2^{i-1} &= \left(\sum_{i=1}^k\,i2^{i-1}\right)+(k+1)2^{(k+1)-1}\\ &= \left((k-1)\cdot2^k+1\right)+(k+1)2^k &\text{(inductive hypothesis)}\\ &= \big((k-1)+(k+1)\big)2^k+1\\ &= (k\cdot2)\cdot2^k+1\\ &= k2^{k+1}+1 \end{align*}\end{split}\]

which is what we wanted to show. This completes the induction.

□

For example, these theorems show that \(\displaystyle\sum_{i=1}^{100}i = 1+2+3+4+\cdots+100 =\) \(\frac{100(100+1)}{2} = 5050\) and that \(1\cdot2^0+2\cdot2^1+3\cdot2^2+4\cdot2^3+5\cdot2^4 = (5-1)2^5+1=129\), as well as infinitely many other such sums.

3.5. Strong Mathematical Induction#

There is a second form of the principle of mathematical induction which is useful in some cases. To apply the first form of induction, we assume \(P(k)\) for an arbitrary natural number \(k\) and show that \(P(k+1)\) follows from that assumption. In the second form of induction, the assumption is that \(P(x)\) holds for all \(x\) between 0 and \(k\) inclusive, and we show that \(P(k+1)\) follows from this. This gives us a lot more to work with when deducing \(P(k+1)\). We will need this second, stronger form of induction in the next two sections. A proof will be given in the next chapter.

Theorem 3.8

Let \(P\) be a one-place predicate whose domain of discourse includes the natural numbers. Suppose that \(P(0)\) is true and that

\[(P(0)\wedge P(1)\wedge\cdots\wedge P(k))\rightarrow P(k+1)\]

is true for each natural number \(k\geq 0\).
Then \(P(n)\) is true for every natural number \(n\).

For example, we can use this theorem to prove that every integer greater than one can be written as a product of prime numbers (where a number that is itself prime is considered to be a product of one prime number). The proof illustrates an important point about applications of this theorem: When proving \(P(k+1)\), you don’t necessarily have to use the assumptions that \(P(0)\), \(P(1)\), … , and \(P(k)\) are true. If \(P(k+1)\) is proved by any means—possibly including the assumptions—then the statement \((P(0)\wedge P(1)\wedge\cdots\wedge P(k))\rightarrow P(k+1)\) has been shown to be true. It follows from this observation that several numbers, not just zero, can be ‘base cases’ in the sense that \(P(x+1)\) can be proved independently of \(P(0)\) through \(P(x)\). In this sense, 0, 1, and every prime number are base cases in the following theorem.

Theorem 3.9

Every natural number greater than one can be written as a product of prime numbers.

Proof. Let \(P(n)\) be the statement ‘’if \(n>1\), then \(n\) can be written as a product of prime numbers’’. We will prove that \(P(n)\) is true for all \(n\) by applying the second form of the principle of induction.

Note that \(P(0)\) and \(P(1)\) are both automatically true, since \(n=0\) and \(n=1\) do not satisfy the condition that \(n>1\), and \(P(2)\) is true since 2 is the product of the single prime number 2. Suppose that \(k\) is an arbitrary natural number with \(k>1\), and suppose that \(P(0)\), \(P(1)\), … , \(P(k)\) are already known to be true; we want to show that \(P(k+1)\) is true.
In the case where \(k+1\) is a prime number, then \(k+1\) is a product of one prime number, so \(P(k+1)\) is true.

Consider the case where \(k+1\) is not prime. Then, according to the definition of prime number, it is possible to write \(k+1=ab\) where \(a\) and \(b\) are numbers in the range from 2 to \(k\) inclusive. Since \(P(0)\) through \(P(k)\) are known to be true, \(a\) and \(b\) can each be written as a product of prime numbers. Since \(k+1=ab\), \(k+1\) can also be written as a product of prime numbers. We have shown that \(P(k+1)\) follows from \(P(0)\wedge P(1)\wedge\cdots\wedge P(k)\), and this completes the induction.

□

Video

In two of the pencasts of this course, we treat two flawed induction proofs and examine what mistakes have been made. You can find them here: youtu.be/m0EIgQyukdQ and youtu.be/2c-zw-ENNss.

3.5.1. Exercises#