Skip to main content

Chapter 4 Induction and Recursion

Induction is a technique that may be used to prove that a given statement is true for every positive integer.

Example 4.1.

We begin with two statements that we might try to prove are true for every positive integer. Are both of these statements true for every positive integer?

  1. My car will start on the \(n^{th}\) day after yesterday.

  2. The sum of the first \(n\) positive integers is \(n(n+1)/2\text{.}\)

Suppose I wish to prove that the second statement above is true for every positive integer. Let's check the first few. If \(n=1\) then this says \(1 = \frac{1(1+1)}{2}\) which is true. If \(n=2\) then this says that \(1 + 2 = \frac{2(2+1)}{2}\) which is true. If \(n=3\) then this says that \(1 + 2 + 3 = \frac{3(3+1)}{2}\) which is true. Now, even if we proved this was true for the first \(1,000,000\) positive integers, we would not know if it was true for \(n=1,000,001\text{.}\) How do we prove that it is true for all positive integers? Let's proceed by contradiction and suppose that it is not true for every positive integer. Since it is not true for every positive integer, then there must be a first positive integer \(m\) for which it is not true. Since it is true for \(1\text{,}\) there is a positive integer \(n\) such that \(m=n+1\text{.}\) Since \(n \lt m\text{,}\) it is true for \(n\text{,}\) that is,

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

Adding \(n+1\) to both sides we have

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

Using common denominators to combine the terms on the right yields

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

Simplifying the right hand side leaves us with

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

We assumed that \(n+1\) was the first positive integer for which the statement was false, yet we have just shown that it is true for \(n+1\text{.}\) We have a contradiction. This means that our assumption that it was not true for all positive integers is false and we may conclude that the statement is true for all positive integers.

Problem 4.2.

Show that each statement is true.

  1. The sum of the squares of the first \(2\) positive integers is \(\frac{2(2+1)(2(2)+1)}{6}\text{.}\)

  2. The sum of the squares of the first \(3\) positive integers is \(\frac{3(3+1)(2(3)+1)}{6}\text{.}\)

  3. The sum of the squares of the first \(n\) positive integers is \(\frac{n(n+1)(2n+1)}{6}\) for all \(n \geq 2\text{.}\)

Problem 4.3.

Show that each statement is true.

  1. The sum of the first \(2\) cubes is \(\frac{2^2 (2+1)^2}{4}\text{.}\)

  2. The sum of the first \(3\) cubes is \(\frac{3^2 (3+1)^2}{4}\text{.}\)

  3. The sum of the first \(n\) cubes is \(\frac{n^2 (n+1)^2}{4}\) for all \(n \geq 2\text{.}\)

Problem 4.4.

A set of numbers is bounded if there are two numbers \(m\) and \(M\) so that for each number \(x\) in the set, \(m \leq x \leq M\text{.}\)

  1. Show that a set with one element is bounded.

  2. Show that a set with two elements is bounded.

  3. Show that a set with three elements is bounded.

  4. Show that for each positive integer \(n\text{,}\) a set with \(n\) elements is bounded.

Problem 4.5.

Show that a postage of 12, 13, 14 or 15 cents may be formed using only 4-cent and 5-cent stamps. Then show that every amount of postage of 12 cents or more can be formed using just 4-cent and 5-cent stamps.

Problem 4.6.

Show that the sum of the first \(n\) odd positive integers is \(n^2\text{.}\)

Problem 4.7.

Assume Theorem 3.7 (The Multiplication Principle for Counting) is true and prove that Theorem 3.8 (The Generalized Multiplication Principle for Counting) is true for every positive integer \(n\text{.}\)

Problem 4.8.

From your Calculus I course, you know that if each of \(f\) and \(g\) is a differentiable functions, then \((fg)' = f'g + fg'\text{.}\) Use induction to show that for every positive integer \(n\text{,}\) if each of \(f_1, f_2, f_3, \dots f_n\) is a differentiable function then

\begin{equation*} \left( f_1 f_2 f_3 \cdot\cdot f_n \right)' = f_1' f_2 f_3 \cdot\cdot f_n + f_1 f_2' f_3 \cdot\cdot f_n + f_1 f_2 f_3' \cdot\cdot f_n + \dots + f_1 f_2 f_3 \cdot\cdot f_n'\text{.} \end{equation*}

Towers of Hanoi The Towers of Hanoi is a mathematical puzzle with a history worth Googling. As illustrated above, the puzzle consists of three rods with \(n\) disks of different radii which can slide onto any rod. Start with the disks stacked all on one rod, the largest on the bottom, the smallest on the top and in order of size. The object of the puzzle is to move the stack to another rod, obeying the following rules:

  1. Only one disk may be moved at a time.

  2. Each move consists of taking the upper disk from one of the rods and moving it onto another rod, on top of any other disks that may already be present on that rod.

  3. No disk may be placed on top of a smaller disk.

Problem 4.9.

Show that it is possible to solve the Tower of Hanoi puzzle with \(n\) discs in \(2^n - 1\) moves.

Problem 4.10.

Show that to solve the Tower of Hanoi puzzle on \(n\) discs, at least \(2^n-1\) moves must be made.

Problem 4.11.

Show that \(1/2 + 1/4 + 1/8 + 1/16 + .... + 1/2^n = 1 - 1/2^n\text{.}\)

Problem 4.12.

Show that \(3^0 + 3^1 + 3^2 + \dots + 3^n = (3^{n+1} - 1)/2\) is valid for all non-negative integers, \(n=0,1,2,\dots\text{.}\)

Definition 4.13.

A positive integer is a prime if it has exactly two positive factors, 1 and itself.

Problem 4.14.

You have an interview with the NSA and they ask you if \(p(n) = n^2 - n + 41\) is prime for every positive integer \(n\text{.}\) Is it?

Problem 4.15.

Show that

\begin{equation*} 1\cdot 2 + 2\cdot 3 + 3\cdot 4 + 4\cdot 5 + .... + n\cdot (n+1) = n(n+1)(n+2)/3\text{.} \end{equation*}
Problem 4.16.

Prove that every positive integer is either \(1\text{,}\) a prime, or the product of primes.

Problem 4.17.

There are many commonly used functions \(f\) with domain \(\Z\) that are not easily defined explicitly. Instead, we tell how to compute \(f\) by what we call a recursive process. To do this, we

  1. choose a positive integer \(b\) (often \(b = 1\)),

  2. give the values of \(f(1), f(2),...,f(b)\) explicitly, and

  3. tell how to compute, for any \(k > b\text{,}\) the value of \(f(k)\) using the previous values \(f(1), f(2), f(3), ..., f(k-1)\text{.}\)

Prove that steps 1-3 can be used to compute \(f(n)\) for every positive integer \(n\text{.}\)

This is exactly what happens when you ask a program to do a recursive call. An advantage of recursively defined functions is that their properties can often be verified by using induction. Your use of quotes in the program and your use of the quotes in the last sentence are incongruous, so I deleted them from the last sentence.

Problem 4.18.

Consider the following computer program:

Let i = 1 and  a = 2
While  i > 0   Do
    Print ''f(''  i '') ='' a
    i=i+1
    a=2a-1
End i While Loop

Use induction to prove that for each positive integer \(n\) the computer will eventually print \(f(n) = 2^{n-1} + 1\text{.}\)

Problem 4.19.

The Fibonacci Sequence is obtained by taking \(b=2\) and defining

  1. \(F(1) = 1, \enspace F(2) = 1\) and

  2. \(F(k) = F(k-2) + F(k-1)\) for \(k \ge 3\text{.}\)

Compute \(F(3)\) through \(F(12)\text{.}\) Use induction to prove that for all \(n \ge 1\text{,}\)

\begin{equation*} F(1) + F(2) + F(3) + ... + F(n) + 1= F(n+2) \end{equation*}
Problem 4.20.

Check that \(F(3), F(6), F(9)\) and \(F(12)\) are even. Then use induction to prove that \(F(3n)\) is even for all \(n \ge 1\text{.}\)