Induction

Section 3.4 Induction

Guiding Questions.

In this section, we’ll seek to answer the questions:

What is the principle of mathematical induction? What the crucial steps in a proof by induction?

🔗
What is strong induction? How is it different than induction?

🔗

To this point, our proof techniques have been deductive in nature; beginning from accepted axioms and definitions, we apply logical inference to reason from hypotheses to conclusions. In the natural and social sciences, inductive reasoning is more common. Data is gathered, and general conclusions are drawn from the data. It might sound strange, then, to talk about a mathematical induction, but make no mistake —the technique we’ll explore in this section is still deductive reasoning. However, the process we describe begins with the verification of our theorem in a particular case (hence the name). In fact, mathematical induction offers a way of iteratively proving statements about infinite subsets of the natural numbers. It is there that we begin our journey.

🔗

Definition 3.4.1.

The collection of natural numbers is denoted by \(\N\text{,}\) and is the set

\begin{equation*} \N = \set{1, 2, 3, \ldots}\text{.} \end{equation*}

🔗

By \(\N_0\) we mean the set of whole numbers, \(\N_0 = \set{0, 1, 2, 3, \ldots}\text{.}\)

🔗

From the natural numbers, we can build the set of integers.

🔗

Definition 3.4.2.

The set of integers consists of the positive and negative natural numbers, together with zero, and is denoted by \(\Z\text{:}\)

\begin{equation*} \Z = \set{\ldots, -3, -2, -1, 0, 1, 2, 3, \ldots}\text{.} \end{equation*}

🔗

Before formally defining induction, let’s consider an example.

🔗

Theorem.

For all natural numbers \(n \ge 1\text{,}\)

\begin{equation*} 1+ 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\text{.} \end{equation*}

🔗

Proof. Base case: When \(n = 1\text{,}\) the equation \(1 = \frac{1\cdot (1+1)}{2}\) is true.

🔗

Inductive Hypothesis: Assume for some \(k\ge 1\) that the equation

\begin{equation} 1+ 2 + 3 + \cdots + k = \frac{k(k+1)}{2}\tag{3.4.1} \end{equation}

is true.

🔗

Inductive Step: Our goal is to show that \(P(k+1)\) is true. That is, we wish to establish that

\begin{equation} 1+ 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)((k+1)+1)}{2}\text{.}\tag{3.4.2} \end{equation}

🔗

We begin on the left-hand side of (3.4.1), where we may apply the inductive hypothesis to see that

\begin{equation} 1+ 2 + 3 + \cdots + k + (k+1) = \left[\frac{k(k+1)}{2}\right] + (k+1)\text{.}\tag{3.4.3} \end{equation}

Through the use of straightforward algebra, the right-hand side of (3.4.3) becomes

\begin{equation} \frac{k(k+1)}{2} + \frac{2(k+1)}{2} = \frac{k(k+1) + 2(k+1)}{2} = \frac{(k+1)(k+2)}{2}\text{.}\tag{3.4.4} \end{equation}

🔗

Putting (3.4.3) and (3.4.4) together, we obtain

\begin{equation*} 1+ 2 + 3 + \cdots + k + (k+1) = \frac{(k+1)((k+1)+1)}{2}\text{,} \end{equation*}

which is exactly the goal we stated in (3.4.2).

🔗

Let’s consider what just happened.

🔗

We began with a statement about the natural numbers: “For all natural numbers \(n \ge 1\text{...}\)”. Thus, our proof needs to be valid for all natural numbers.

🔗
We first established that the theorem was true for the first natural number \(n=1\text{.}\)

🔗
In the inductive hypothesis, we assumed the statement was true for some natural number \(k\ge 1\text{.}\) This is reasonable since it is true for \(k=1\text{.}\) The choice of \(k\) is not necessary, but does emphasize that we are still in the proof-writing stage. If we’d stated the inductive hypothesis using \(n\text{,}\) one could confuse the inductive hypothesis with the actual theorem statement and think that we’d finished.

🔗
In the inductive step, we use the inductive hypothesis that the statement is true for the natural number \(k\) to prove that this means that the statement is true for \(k+1\text{.}\) Symbolically, we prove the implication \(P(k) \Rightarrow P(k+1)\text{.}\)

🔗
Since we know the statement is true when \(k=1\text{,}\) the inductive step tells us that it’s true for \(k=2\text{.}\) Again, by the inductive step, the statement is true for \(k=3\text{.}\) And thus for \(k=4\text{.}\) And so on, for all \(k\in\N\text{.}\)

🔗

Mathematical induction is like climbing an infinite staircase. The base case tells us that we can take a first step on the staircase (\(k_0\)). In the inductive hypothesis, we assume we can take some step (\(k\)). In the inductive step, we prove that this allows us to take the \((k+1)\)st step.

🔗

Thus, if we can take step \(k_0\text{,}\) we can (by the inductive step) take step \(k_0 + 1\text{.}\) And since we can take step \(k_0 + 1\text{,}\) we can (again by the inductive step) take step \(k_0 + 2\text{.}\) And so on, as far up the natural numbers as you’d want to go.

🔗

Formally, we have the the following.

🔗

Principle of Mathematical Induction.

Let \(P(m)\) be a statement about the natural number \(m\)

Sample statements could include “\(m\) is really interesting” or “\(3m^2 + m + 2\) is even”.

. Let \(k_0\in \N\) be the smallest natural number for which the statement \(P(k_0)\) is true (the base case). Further, suppose that for for all \(n\ge k_0\text{,}\) if \(P(n)\) is true (the inductive hypothesis), then \(P(n+1)\) is true (the inductive step). Then \(P(m)\) is true for all natural numbers \(m\ge k_0\)

🔗

We now have some opportunities to practice induction.

🔗

Problem 3.4.3.

For all \(n\in\N\text{,}\)

🔗

\begin{equation*} 2 + 5 + 8 + \cdots + (3n-1) = \frac{n(3n+1)}{2}. \end{equation*}

🔗

Problem 3.4.4.

For all \(n\in\N\text{,}\)

🔗

\begin{equation*} 1 + 5 + 9 + \cdots + (4n-3) = n(2n-1). \end{equation*}

🔗

Problem 3.4.5.

For all \(n\in\N\text{,}\)

🔗

\begin{equation*} 1^3 + 2^3 + 3^3 + \cdots + n^3 = \left[ \frac{n(n+1)}{2} \right]^2. \end{equation*}

🔗

Problem 3.4.6.

For all \(n\in\N\text{,}\) \(3 | 4^n - 1\text{.}\)

🔗

Definition 3.4.7.

Let \(n\in\N\text{.}\) The complete graph on \(n\) vertices is the graph for which there is an edge between any pair of vertices. We denote the complete graph on \(n\) vertices by \(K_n\text{.}\)

🔗

Problem 3.4.8.

Choose at least three values of \(n\) satisfying \(n\ge 2\) and draw \(K_n\text{.}\) Conjecture a formula in terms of \(n\) for the number of edges in \(K_n\text{.}\) Use induction to prove that your formula is correct.

🔗

It is worth investigating the base case a bit more. First, we note that induction can still be used even if we do not start at \(n=1\text{.}\)

🔗

Problem 3.4.9.

If \(n\in\N\) and \(n\ge 4\text{,}\) then \(3^n \gt 2n^2 + 3n\text{.}\)

🔗

Problem 3.4.10.

Let \(P_1, P_2, \ldots, P_n\) be statements, where \(n\ge 2\text{.}\) Then

🔗

\begin{equation*} \neg (P_1 \land P_2 \land \cdots \land P_n) \equiv \neg P_1 \lor \neg P_2 \lor \cdots \lor \neg P_n. \end{equation*}

🔗

We now see the fundamental importance of the base case.

🔗

Problem 3.4.11.

Let \(P(n)\) be the statement

🔗

\begin{equation*} 1 + 2 + \cdots + n = \frac{n^2 + n + 1}{2}. \end{equation*}

Prove that \(P(k)\Rightarrow P(k+1)\text{.}\)

🔗
Is \(P(1)\) true? Is \(P(2)\) true? What of \(P(3)\) or \(P(4)\text{?}\) Explain why this shows that the base case is a crucial ingredient in the inductive process.

🔗

🔗

We consider one more important example of induction gone wrong.

🔗

Theorem 3.4.12.

Every cat is the same color.

🔗

Proof.

We begin by restating the theorem as follows: “In any collection of \(n\) cats, every cat has the same color.” Since there are finitely many cats in the world, we need only take \(n\) to be large enough to establish the theorem.

🔗

Clearly a collection of \(n=1\) cats consists only of cats of the same color, so we’ve established the base case.

🔗

For the inductive hypothesis, assume that for some \(k\ge 1\text{,}\) in any collection of \(k\) cats consists of cats of the same color.

🔗

Now consider a collection of \(k+1\) cats. Kindly ask them to line up so we can identify them by their place in line

We can wait while they wander around and decide to (finally) do it.

. Call them \(c_1, c_2, \ldots, c_{k}, c_{k+1}\text{.}\)

🔗

First, open a can of food so that \(c_{k+1}\) is occupied, and note that since \(c_1, c_2, \ldots, c_{k}\) comprise a collection of \(k\) cats, the inductive hypothesis tells us that they must all be the same color.

🔗

After \(c_{k+1}\) has finished its food, distract \(c_1\) with a laser pointer. Note again that \(c_2, c_3, \ldots, c_{k}, c_{k+1}\) form a collection of \(k\) cats and so, by the inductive hypothesis, we must admit that they have the same color.

🔗

Since \(c_1\) has the same color as \(c_2\text{,}\) which in turn had the same color as \(c_{k+1}\text{,}\) we must admit that every cat in our collection of \(k+1\) cats has the same color as all the others.

🔗

Thus, every cat has the same color.

🔗

Problem 3.4.13.

Carefully and precisely describe what went wrong in the proof of Theorem 3.4.12.

🔗

The version of induction above is often sufficient for our needs. However, its inductive hypothesis has one main weakness: to establish \(P(k+1)\text{,}\) you are only allowed to assume \(P(k)\) (in addition to any previously-established theorems). The following version of induction, often called strong induction, gives us a bit more.

🔗

Strong Mathematical Induction.

Let \(P(m)\) be a statement about the natural number \(m\text{.}\) Let \(k_0\in \N\) be such that the statement \(P(k_0)\) is true (the base case), and suppose there is an \(n\ge k_0\) such that for all \(k\) satisfying \(k_0 \le k \le n\text{,}\) \(P(k)\) is true (the inductive hypothesis). Then \(P(n+1)\) is true, and thus \(P(m)\) is true for all \(m\ge k_0\) (the inductive step).

🔗

Activity 3.4.14.

Compare weak induction and strong induction. What is the crucial difference? Do you think that strong induction be used whenever weak induction applies? What about vice versa?

🔗

To see how this might affect your proof-writing and test your answers to the previous questions, rewrite Problem 3.4.5 using strong induction. What do you notice?

🔗

There are some arguments that require strong induction.

🔗

Theorem 3.4.15.

Every natural number \(n\ge 2\) is divisible by a prime.

🔗

Activity 3.4.16.

Why is strong induction required for Theorem 3.4.15? Where would an argument using weak induction run into trouble?

🔗

We conclude by observing that, since strong induction applies whenever weak induction does (and, indeed, with only minor changes to a given weak inductive argument), we will typically use strong induction in place of induction, and will often refer to it simply as “induction”.

🔗

Prev Top Next