Skip to main content

Section Project: More Induction

In this chapter we developed and used a method for proving that a given statement is true for all positive integers. This technique is called strong induction. Many books treat two techniques of induction, induction and strong induction, separately. For both induction and strong induction, you first show that the statement is true for \(n=1\text{.}\) With induction, you assume only that the statement is true for \(n\) in order to prove that it is true for \(n+1\text{.}\) With strong induction, you assume that the statement is true for every number from \(1\) to \(n\) and use this to prove that it is true for \(n+1\text{.}\) Since both are valid methods, we should state and prove theorems justifying both. In this section we will state an axiom on which these theorems depend, provide guidance on how you might prove them, state the theorems for you to prove, and then provide additional problems using these theorems.

Problem 4.22.

Prove the following two theorems and note where you use the Well Ordering Axiom. The proofs amount to simply repeating again the argument you have used in each of the previous problems that you have done. If you prove this theorem, you will never need to repeat that argument again. You will just quote one of these two theorems!

The previous principle is called “strong induction” in order to contrast it with the next principle which is called “induction”. You might prove Theorem 4.24 directly or you might use Theorem 4.23 to prove Theorem 4.24.

In each of the induction problems you worked in the main section, you assumed the statement was true for integers \(1, 2, 3, \dots, n\) and showed that it must then be true for \(n+1\text{.}\) If you review your arguments, you will see that, for most of them, you only used the fact that the statement was true for \(n\) in order to prove that it was true for \(n+1\text{.}\) In those cases, you could have used either induction or strong induction. The exceptions were Problems 4.5 and Problem 4.16 where your argument most likely used strong induction even though you can work both using induction. You might also note that there is nothing special about starting with \(n=1\) and for many of the problems, we started with a value for \(n\) greater than 1. For each positive integer \(b\) we could prove a variant of Theorem 4.23 ending with

  1. \(S(b)\) is true and

  2. \(S(k+1)\) is true whenever \(S(m)\) is true for \(b \leq m \leq k\text{,}\)

then \(S(n)\) is true for all positive integers \(n\geq b\text{.}\) }

Similarly Theorem 4.24 could be modified to start with \(b\text{.}\)

Enough theory, let's do some problems. To solve the next problem, we need a recursive definition for factorial.

Definition 4.25.

If \(n\) is a non-negative integer then n factorial is denoted by \(n!\) and defined by

\begin{equation*} n! = \begin{cases} 1 \amp \text{if} \;\;\;\; n=0 \;\; \text{or} \;\; n=1 \\ (n+1)! = (n+1)\cdot n! \amp \mbox{if} \;\;\;\; n > 1 \end{cases} \end{equation*}
Problem 4.26.

Prove that if \(n \ge 5\text{,}\) then \(n!\) is a multiple of \(5\text{.}\)

Problem 4.27.

Define a function \(g\) recursively by

  1. \(g(1) = 2\) and

  2. \(g(k+1) = 4g(k) - 5\text{.}\)

Compute \(g(7)\text{.}\) Prove that \(g(n) > 2^n\) for all \(n \ge 4\text{.}\)

Recursively defined functions can grow surprisingly fast. As a result, one must be cautious about asking a computer to do recursions since both time and memory are limited. When we were students, if you divided by zero or asked a computer to compute a number that was too large for its memory, it exploded, immediately killing the student. That is why everyone over the age of 30 is smart. \(;>\)

Problem 4.28.

Define a sequence of functions \(A_1, A_2, A_3,\dots\) as follows:

  1. Let \(A_1(n) = 2n\) for all \(n\text{.}\)

  2. For \(k=1,2,3,\dots\) let

    1. \(A_{k+1}(0) = 1\) and

    2. \(A_{k+1}(m+1) = A_k(A_{k+1}(m))\text{.}\)

  3. Use induction to show that \(A_2(n) = 2^n\) for all \(n\text{.}\)

  4. Use induction to show that \(A_n(1) = 2\) for all \(n\text{.}\)

  5. Write down \(A_3(5)\text{.}\)

  6. Describe \(A_3(n)\text{.}\)

  7. The number \(A_4(4)\) is so large that I will give an “A” in the course to anyone who can bring me a printout of its value (in normal decimal notation) by the end of the term.

Problem 4.29.

In one of our recent wars, an army captain received orders to deploy his soldiers over a designated enemy area and to instruct them to shoot any resident who came into view.

Now the captain talked with other captains and heard that among the new recruits there were soldiers who for some strange reason didn't buy into this mission. They were even known, in the heat of battle, to shoot their own captains and go AWOL. This worried him, so he devised the following plan.

He would deploy his soldiers, as ordered, but instruct them to situate themselves so that each one was nearest to exactly one other soldier. Each soldier was ordered to watch that nearest soldier to him, and report any suspicious behavior to the captain.

Assuming the number of soldiers was odd, prove that there was at least one soldier who wasn't being watched.