Revisiting Inductive Proofs

Section 14.1 Revisiting Inductive Proofs

Induction is a powerful method for showing a property is true for all nonnegative integers. Induction plays a central role in discrete mathematics and computer science. In fact, its use is a defining characteristic of discrete --as opposed to continuous-- mathematics.

This section begins with a review of inductive proofs from Mathematics for Computer Science (Lehman, Leighton, and Meyer)

eng.libretexts.org/Bookshelves/Computer_Science/Programming_and_Computation_Fundamentals/Mathematics_for_Computer_Science_(Lehman_Leighton_and_Meyer)

Subsection 14.1.1 Ordinary Induction

Suppose there is a professor who brings a bottomless bag of assorted miniature candy bars to her large class. She offers to share the candy in the following way. First, she lines the students up in order. Next she states two rules:

The student at the beginning of the line gets a candy bar.
If a student gets a candy bar, then the following student in line also gets a candy bar.

Let’s number the students by their order in line, starting the count with 0, as usual in computer science. Now we can understand the second rule as a short description of a whole sequence of statements:

If student 0 gets a candy bar, then student 1 also gets one.
If student 1 gets a candy bar, then student 2 also gets one.
If student 2 gets a candy bar, then student 3 also gets one.

Of course, this sequence has a more concise mathematical description:

\begin{gather*} \text{If student }n \text{ gets a candy bar, then student } n+1 \text{ gets a candy bar,}\\ \text{for all nonnegative integers,} n. \end{gather*}

So suppose you are student 17. By these rules, are you entitled to a miniature candy bar? Well, student 0 gets a candy bar by the first rule. Therefore, by the second rule, student 1 also gets one, which means student 2 gets one, which means student 3 gets one as well, and so on. By 17 applications of the professor’s second rule, you get your candy bar! Of course the rules really guarantee a candy bar to every student, no matter how far back in line they may be.

The reasoning that led us to conclude that every student gets a candy bar is essentially all there is to induction.

Definition 14.1.1. The Induction Principle.

Let \(P\) be a proposition over a universe Definition 4.5.1 (or predicate) on the nonnegative integers. If

\(P(0)\) is true, and
\(P(n) \Rightarrow P(n+1)\) for all nonnegative integers, \(n\) (remember from Definition 4.3.11 , \(\Rightarrow\) means IMPLIES ),

then

\(P(m)\) is true for all nonnegative integers, \(m\text{.}\)

We’ll refer to the induction method described above as ordinary induction when we need to distinguish it in this chapter. Formulated as a formal argument as in Chapter 5, this would be

Theorem 14.1.2. Induction Rule.

\begin{align*} & P(0)\\ & \forall n, P(n)\Rightarrow p(n+1)\\ \hline \\ \therefore & \forall m \in \N, P(m) \end{align*}

This Induction Rule works for the same intuitive reason that all the students get candy bars, and we hope the explanation using candy bars makes it clear why the soundness of ordinary induction can be taken for granted. In fact, the rule is so obvious that it’s hard to see what more basic principle could be used to justify it. What’s not so obvious is how much mileage we get by using it.

Example 14.1.3. A Familiar Example.

Below is the formula for the sum of the nonnegative integers up to \(n\text{.}\) The formula holds for all nonnegative integers, so it is the kind of statement to which induction applies directly.

Theorem 14.1.4.

For all \(n \in \N\)

\begin{equation} \sum_{i = 1}^n i = 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2}\tag{14.1.1} \end{equation}

Solution.

To prove the theorem by induction, define predicate \(P(n)\) to be Theorem 14.1.4. Now the theorem can be restated as the claim that \(P(n)\) is true for all \(n \in \N\text{.}\) This is great, because the Induction Principle lets us reach precisely that conclusion, provided we establish two simpler facts:

\(P(0)\) is true.
\(P(n) \Rightarrow P(n+1)\) for all nonnegative integers, \(n\text{,}\)

So now our job is reduced to proving these two statements.

Basis step: The first statement follows because of the convention that a sum of zero terms is equal to 0. So \(P(0)\) is the true assertion that a sum of zero terms is equal to \(\frac{0(0+1)}{2} =0\text{.}\)

Inductive step:The second statement is more complicated. But remember a basic plan for proving the validity of any implication: assume the statement on the left and then prove the statement on the right. In this case, we assume \(P(n)\) namely, Theorem 14.1.4, in order to prove \(P(n+1)\text{,}\) which is the equation:

\begin{equation} \sum_{i = 1}^{n+1} i = 1 + 2 + 3 + \cdots + n + (n+1) = \frac{(n+1)(n+2)}{2}\tag{14.1.2} \end{equation}

These two equations are quite similar; in fact, adding \((n +1)\) to both sides of equation (14.1.1) and simplifying the right side gives the equation (14.1.2):

\begin{align*} 1 + 2 + 3 + \cdots + n +(n+1) \amp = \frac{n(n+1)}{2} +(n+1)\\ \amp = \frac{(n+1)(n+2)}{2} \end{align*}

Thus, if \(P(n)\)> is true, then so is \(P(n+1)\text{.}\) This argument is valid for every nonnegative integer \(n\text{,}\) so this establishes the second fact required by the induction proof. Therefore, the Induction Principle says that the predicate \(P(M)\) is true for all nonnegative integers, \(m\text{.}\) The theorem is proved.

Subsection 14.1.2 A Template for Inductive Proofs

The proof of Theorem 14.1.4 was relatively simple, but even the most complicated induction proof follows exactly the same template. There are five components:

Define an appropriate predicate: "Let \(P(n)\) be the statement "For every \(n\in \N, \dots \)"
Prove that \(P(0)\) is true. This is usually easy, as in the example above. This part of the proof is called the base case or basis step.
Define an appropriate inductive hypothesis. The predicate \(P(k)\text{,}\) setting \(n\) to some arbitrary \(k \in \N\) is called the inductive hypothesis. The eventual conclusion of the induction argument will be that \(P(n)\) is true for all nonnegative \(n\text{.}\) A clearly stated induction hypothesis is often the most important part of an induction proof, and its omission is the largest source of confused proofs by students. In the simplest cases, the induction hypothesis can be lifted straight from the proposition you are trying to prove, as we did with equation (14.1.1). Sometimes the induction hypothesis will involve several variables, in which case you should indicate which variable serves as \(n\) (usually \(k\) is used for this).
Prove that \(P(k)\) implies \(P(k+1)\) for every nonnegative integer \(k\text{.}\) This is called the inductive step. The basic plan is always the same: assume that \(P(k)\) is true and then use this assumption to prove that \(P(k+1)\) is true. These two statements should be fairly similar, but bridging the gap may require some ingenuity. Whatever argument you give must be valid for every nonnegative integer \(k\text{,}\) since the goal is to prove that all the following implications are true:

\begin{equation*} P(0) \rightarrow P(1), P(1) \rightarrow P(2). P(2) \rightarrow P(3). \dots \end{equation*}
Invoke induction. State a conclusion, for example: Given these facts, the induction principle allows us to conclude that \(P(n)\) is true for all nonnegative \(n \in \N\text{.}\) This is the logical capstone to the whole argument.

Always be sure to explicitly label the base case and the inductive step (which encompasses steps 4 and 5 above). Doing so will make your proofs clearer and will decrease the chance that you forget a key step—like checking the base case.

The proof of Theorem 14.1.4 given above is perfectly valid; however, it contains a lot of extraneous explanation that you won’t usually see in induction proofs. The writeup below is closer to what you might see in print and should be prepared to produce yourself.

Example 14.1.5. A Clean Writeup.

Let \(P(n)\) be the statement: for every \(n \in \N\text{,}\)

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

Basis step: \(P(0)\) is true, because both sides of the equation equal 0 when \(n = 0.\)

Inductive step: Assuming an inductive hypothesis that \(P(k)\) is true, that is

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

for some nonnegative integer \(k\text{.}\) Adding \(k+1\) to both sides of the equation implies that

\begin{align*} 1 + 2 + 3 + \cdots + k +(k+1) \amp = \frac{k(k+1)}{2} +(k+1) & \\ \amp = \frac{(k+1)(k+2)}{2} & \text{(by simple algebra)} \end{align*}

which proves \(P(k+1).\)

Conclusion: So it follows by induction that \(P(n)\) is true for all nonnegative \(n\text{.}\) \(\blacksquare\)

It probably bothers you that induction led to a proof of this summation formula but did not provide an intuitive way to understand it nor did it explain where the formula came from in the first place. This is both a weakness and a strength. It is a weakness when a proof does not provide insight. But it is a strength that a proof can provide a reader with a reliable guarantee of correctness without requiring insight.

Subsection 14.1.3 Strong Induction

A useful variant of induction is called strong induction. Strong induction and ordinary induction are used for exactly the same thing: proving that a predicate is true for all nonnegative integers. Strong induction is useful when a simple proof that the predicate holds for \(n+1\) does not follow just from the fact that it holds at \(n\text{,}\) but from the fact that it holds for other values\(\leq n\text{.}\)

Definition 14.1.6. Principle of Strong Induction.

Let \(P\) be a predicate on nonnegative integers. If

\(P(0)\) is true, and
for all \(n \in \N, P(0), P(1), \dots, P(n)\) together imply \(P(n+1)\text{,}\)

then \(P(M)\) is true for all \(m \in \N\text{.}\)

The only change from the ordinary induction principle is that strong induction allows you make more assumptions in the inductive step of your proof! In an ordinary induction argument, you assume that \(P(n)\) is true and try to prove that \(P(n+1)\) is also true. In a strong induction argument, you may assume that \(P(0), P(1), \dots,\) and \(P(n)\) are all true when you go to prove \(P(n+1)\text{.}\) So you can assume a stronger set of hypotheses which can make your job easier.

Formulated as a formal argument as in Chapter 5, strong induction is

Theorem 14.1.7. Strong Induction Rule.

\begin{align*} & P(0)\\ & \forall n,(P(0) \land P(1) \land \dots P(n))\Rightarrow p(n+1)\\ \hline \\ \therefore & \forall m \in \N, P(m) \end{align*}

Stated more succinctly, the rule is

\begin{align*} & P(0)\\ & \left[ \forall k \leq n \in \N,P(k) \right] \Rightarrow p(n+1)\\ \hline \\ \therefore & \forall m \in \N, P(m) \end{align*}

The template for strong induction proofs is identical to the template given in Subsection 14.1.2 for ordinary induction except for two things:

you should state that your proof is by strong induction, and
you can assume that \(P(0),P(1),\dots,\) and \(P(n)\) are all true instead of only \(P(n)\) during the inductive step.

Example 14.1.8. Product of Primes.

Theorem 14.1.9.

Every integer greater than 1 is a product of primes.

We will prove Theorem 14.1.9 by strong induction, letting \(P(n)\) be the statement: \(\forall n > 1 \in \N, n\) is a product of primes.

Basis step: \(P(2)\) is true because 2 is prime, so it is a length one product of primes by convention.

Inductive step: Suppose that \(k\geq 2\) and that every number from 2 to \(k\) is a product of primes. We must show that \(P(k+1)\) holds, namely, that \(k +1\) is also a product of primes. We argue by cases:

If \(k+1\) itself is prime, it is a length one product of primes by convention, and so \(P(k+1)\) holds in this case.
Otherwise, \(k+1\) is not prime, which by definition means \(k+1 = i\cdot j\) for some integers \(i, j\) between 2 and \(k\text{.}\) Now by the strong induction hypothesis, we know that both \(i\) and \(j\) are products of primes. By multiplying these products, it follows immediately that \(i\cdot j = k+1 \) is also a product of primes. Therefore, \(P(K+1)\) holds in this case as well.

Conclusion:So \(P(k+1)\) holds in any case, which completes the proof by strong induction that \(P(n)\) holds for all \(n \geq2\text{.}\) \(\blacksquare\)

Prev Top Next