In this chapter, we introduce mathematical induction, which is a proof technique that is useful for proving statements of the form “For all natural numbers \(n\text{,}\)\(P(n)\)”, or more generally “For all integers \(n\geq a\text{,}\)\(P(n)\)”, where \(P(n)\) is some predicate. Loosely speaking, a predicate \(P(n)\) is some statement about \(n\text{.}\) For example, “\(n\) is prime” is a predicate.
“Proof” of (a). If \(n=1\text{,}\) then \(1=\frac{1(1+1)}{2}\text{.}\) If \(n=2\text{,}\) then \(1+2=3=\frac{2(2+1)}{2}\text{.}\) If \(n=3\text{,}\) then \(1+2+3=6=\frac{3(3+1)}{2}\text{,}\) and so on.
“Proof” of (b). If \(n=1\text{,}\) then \(n^{2}+n+41=43\text{,}\) which is prime. If \(n=2\text{,}\) then \(n^{2}+n+41=47\text{,}\) which is prime. If \(n=3\text{,}\) then \(n^{2}+n+41=53\text{,}\) which is prime, and so on.
Are these actual proofs? No! In fact, the second claim is not even true. If \(n=41\text{,}\) then \(n^{2}+n+41=41^{2}+41+41=41(41+1+1)\text{,}\) which is not prime since it has 41 as a factor. It turns out that the first claim is true, but what we wrote cannot be a proof since the same type of reasoning when applied to the second claim seems to prove something that is not actually true. We need a rigorous way of capturing “and so on” and a way to verify whether it really is “and so on.”
The Principle of Mathematical Induction (or PMI for short) provides us with a process for proving statements of the form “For all natural numbers \(n\text{,}\)\(P(n)\text{,}\)” where \(P(n)\) is some predicate involving \(n\text{.}\) Hypothesis (i) above is called the base step (or base case) while (ii) is called the inductive step.
Intuitively, here is what the Principle of Mathematical Induction is saying. Think of the statements \(P(1), P(2), P(3),\ldots\) as being rungs of a ladder. The base step indicates that we can step onto the first rung of the ladder while the inductive step tells us that if we are on a rung of the ladder we can always move up to the next rung. The Principle of Mathematical Induction asserts that if we can achieve these two things, then we can climb the entire infinite ladder. Do you agree that this seems reasonable?
You should not confuse mathematical induction with inductive reasoning associated with the natural sciences. Inductive reasoning is a scientific method whereby one induces general principles from observations. On the other hand, mathematical induction is a deductive form of reasoning used to establish the validity of a proposition.
Base step: [Verify that \(P(1)\) is true. This often, but not always, amounts to plugging \(n=1\) into two sides of some claimed equation and verifying that both sides are actually equal.]
Inductive step: [Your goal is to prove “For all \(k\in\mathbb{N}\text{,}\) if \(P(k)\) is true, then \(P(k+1)\) is true.”] Let \(k\in\mathbb{N}\) and assume that \(P(k)\) is true. [Do something to derive that \(P(k+1)\) is true.] Therefore, \(P(k+1)\) is true.
Consider a grid of squares that is \(2^n\) squares wide by \(2^n\) squares long, where \(n\in\mathbb{N}\text{.}\) One of the squares has been cut out, but you do not know which one! You have a bunch of L-shapes made up of \(3\) squares. Prove that you can perfectly cover this chessboard with the L-shapes (with no overlap) for any \(n\in\mathbb{N}\text{.}\)Figure 8.1 depicts one possible covering for the case involving \(n=2\) and a fixed cut-out square.
Mathematical induction can actually be used to prove a broader family of results; namely, those of the form “For all integers \(n\geq a\text{,}\)\(P(n)\)”, where \(a \in \mathbb{Z}\text{.}\)Theorem 8.1 handles the special case when \(a = 1\text{.}\) The ladder analogy from earlier holds for this more general situation, too.
Base step: [Verify that \(P(a)\) is true. This often, but not always, amounts to plugging \(n=a\) into two sides of some claimed equation and verifying that both sides are actually equal.]
Inductive step: [Your goal is to prove “For all \(k\geq a\text{,}\) if \(P(k)\) is true, then \(P(k+1)\) is true.”] Let \(k \geq a\) be an integer and assume that \(P(k)\) is true. [Do something to derive that \(P(k+1)\) is true.] Therefore, \(P(k+1)\) is true.
There is another formulation of induction, where the inductive step begins with a set of assumptions rather than one single assumption. This method is sometimes called complete induction or strong induction.
For all \(k \in \mathbb{N}\) with \(m\leq k\text{,}\) if \(P(j)\) is true for all \(j\in \mathbb{N}\) such that \(m\leq j \leq k\text{,}\) then \(P(k+1)\) is true.
Note the difference between ordinary induction (Theorems 8.1 and Theorem 8.7) and complete induction. For the induction step of complete induction, we are not only assuming that \(P(k)\) is true, but rather that \(P(j)\) is true for all \(j\) from \(m\) to \(k\text{.}\) Despite the name, complete induction is not any stronger or more powerful than ordinary induction. It is worth pointing out that anytime ordinary induction is an appropriate proof technique, so is complete induction. So, when should we use complete induction?
In the inductive step, you need to reach \(P(k+1)\text{,}\) and you should ask yourself which of the previous cases you need to get there. If all you need is the statement \(P(k)\text{,}\) then ordinary induction is the way to go. If, for example, two preceding cases, \(P(k - 1)\) and \(P(k)\text{,}\) are necessary to reach \(P(k + 1)\text{,}\) then complete induction is appropriate. In the extreme, if one needs the full range of preceding cases (i.e., all statements \(P(1), P(2),\ldots,P(k)\)), then again complete induction should be utilized.
Note that in situations where complete induction is appropriate, it might be the case that you need to verify more than one case in the base step. The number of base cases to be checked depends on how far one needs to “look back” in the induction step.
Inductive step: [Your goal is to prove “For all \(k\in\mathbb{N}\) with \(m\leq k\text{,}\) if \(P(j)\) is true for all \(j\in \mathbb{N}\) such that \(m\leq j \leq k\text{,}\) then \(P(k+1)\) is true.”] Let \(k \in \mathbb{N}\) with \(m\leq k\) and suppose \(P(j)\) is true for all \(m\leq j \leq k\text{.}\)[Do something to derive that \(P(k+1)\) is true.] Therefore, \(P(k+1)\) is true.
The Fibonacci sequence is given by \(f_1=1\text{,}\)\(f_2=1\text{,}\) and \(f_n=f_{n-1}+f_{n-2}\) for all natural numbers \(n \geq 3\text{.}\) Prove that \(f_n\lt 2^n\) for all \(n\in\mathbb{N}\text{.}\)
Recall that Theorem 8.7 generalized Theorem 8.1 and allowed us to handle situations where the base case was something other than \(P(1)\text{.}\) We can generalize complete induction in the same way, but we will not write this down as a formal theorem.
Consider a grid of squares that is \(2\) squares wide and \(n\) squares long. Using \(n\) dominoes that are \(1\) square by \(2\) squares, there are many ways to perfectly cover this grid with no overlap. How many? Prove your answer.
One final thing worth mentioning is that we did not write down a rigorous proof of the Principle of Inclusion and Exclusion, which we encountered in Chapter 7. However, this omission could be remedied using induction. That is, using induction, we could prove that for all \(n\in\mathbb{N}\) and finite sets \(A_1,\ldots,A_n\text{,}\) we have
which is the General Sum Principle that we encountered in Theorem 1.14. The inductive step is a bit “messy”, so we will omit it, but if you are interested, you can find a complete proof here.
