Induction and Recursion

Induction

The following fundamental fact about the set of integers $\{ 0, 1, 2, \dots \}$ is useful for proofs. It leads to the idea of proof by induction.

Theorem 3.1 (The Well-Ordering Property) Every nonempty set of nonnegative integers has a least element.

Many theorems are that a statement $P(n)$ is true for all positive integers $n$ (here, $P(n)$ is a predicate or propositional function). Mathematical induction is a technique for proving theorems of this kind. In other words, mathematical induction is used to prove propositions of the form $\forall n\, P(n)$ , where the universe of discourse is the set $\{ 0, 1 , 2, \dots \}$ of non-negative integers, or sometimes the set $\{ 1, 2, \dots \}$ .

A proof by mathematical induction that $P(n)$ is true for every positive integer $n$ consists of two steps:

Basis step The proposition $P(0)$ (or sometimes $P(1)$ ) is shown to be true.

Inductive step The implication

is shown to be true for every non-negative integer $n$ .

Here $P(n)$ is called the inductive hypothesis. When we complete both steps of a proof by mathematical induction, we have proved that $P(n)$ is true for all positive integers $n$ ; that is, we have shown that $\forall n\, P(n)$ is true.

Expressed as a rule of inference, this proof technique can be stated as

The first step in the proof is to show that $P(0)$ is true. This amounts to showing that the particular statement $P(n)$ obtained when $n$ is replaced by $0$ is true.

The next step is to show that $P(n) \rightarrow P(n + 1)$ is true for every positive integer $n$ . This can be done by assuming that $P(n)$ is true and showing that under this hypothesis $P(n + 1 )$ must also be true.

The final step of the proof is to invoke the “principle of mathematical induction” which implies the theorem $\forall n, P(n)$ is true.

Thus, by the principle of mathematical induction,

$P(n)$ is true for every integer $n\geq m$ .

Although we are taking $m=0$ in this discussion it is sometimes convenient to start with $m=1$ , or $m=2$ , etc.

In a proof by mathematical induction it is not assumed that $P(n)$ is true for all positive integers! It is only shown that if $P(n)$ is true, then $P(n + 1)$ is also true, that is, $P(n) \rightarrow P(n+1)$ . Thus, a proof by mathematical induction is not a circular argument.

When we use mathematical induction to prove a theorem, we first show that $P(0)$ is true. Then we know that $P(1)$ is true, since $P(0)$ implies $P(1)$ . Further, we know that $P(2)$ is true, since $P(1)$ implies $P(2)$ . Continuing along these lines, we see that $P(k)$ is true, for any positive integer $k$ .

A way to illustrate the principle of mathematical induction is to consider an infinite row of dominoes, labelled $1, 2, 3, \ldots, n$ , where each domino is standing up. Let $P(n)$ be the proposition that domino $n$ is knocked over. If $P(1)$ is true (meaning: the first domino is knocked over), and if $P(n) \rightarrow P(n + 1 )$ is true (meaning: if the $th$ domino is knocked over then it also knocks over the $(n + 1 )$ -th domino), then all the dominoes are knocked over.

The validity of mathematical induction as a proof technique comes from the well-ordering property of the natural numbers.

Suppose we know that $P( 0 )$ is true and that the proposition $P(n) \rightarrow P(n + 1 )$ is true for all positive integers $n.$ To show that $P(n)$ must be true for all positive integers, assume that there is at least one positive integer for which $P(n)$ is false.

• Then the set $S$ of non-negative integers for which $P(n)$ is false is nonempty.
• Thus, by the well-ordering property, $S$ has a least element, which will be denoted by $k$ . We know that $k$ cannot be 0 since $P(0)$ is true.
• Since $k$ is positive and greater than 1, $k - 1$ is a positive integer.
• Furthermore, since $k - 1$ is less than $k$ , it is not in $S$ , so $P(k - 1)$ must be true.
• Since the implication P$(k - 1) \rightarrow P(k)$ is also true, it must be the case that $P(k)$ is true. This contradicts the choice of $k$ .
• Hence, $P(n)$ must be true for every positive integer $n$ .

We will use a variety of examples to illustrate how theorems are proved using mathematical induction. (Many theorems proved in this section via mathematical induction can be proved using different methods. However, it is worthwhile to try to prove a theorem in more than one way, since one method of attack may succeed whereas another approach may not.)

Mathematical induction is often used to verify summation formulae.

Solution.

Let $P(n)$ denote the proposition that the sum of the first $n$ odd positive integers is $n^2$ .

Basis step: $P(0)$ is the claim that the sum of the first zero odd positive integers is $0^2 = 0$ . This is true.

Some students may be more comfortable starting with $n=1$ in this case. $P(1)$ states that the sum of the first odd positive integer is $1^2$ . This is true since the sum of the first odd positive integer is $1$ .

Inductive step: Show that $P(n)\rightarrow P(n+1)$ is true $\forall n\in\Z^{+}$ . Suppose that $P(n)$ is true for a positive integer $n$ ; that is

(Note that the $n^{th}$ odd positive integer is $(2n-1)$ , since this integer is obtained by adding $2$ a total number of $n-1$ times to $1$ ). We must show that $P(n+1)$ is true, assuming that $P(n)$ is true. Note that $P(n+1)$ is the statement that

So, assuming that $P(n)$ is true, it follows that $1+3+5+\dots+(2n-1)+(2n+1)$ */}

This shows that $P(n+1)$ follows from $P(n)$ . Note that we used the inductive hypothesis $P(n)$ in the second equality to replace the sum of the first $n$ odd positive integers by $n^2$ . Since $P(1)$ is true and the implication $P(n)\rightarrow P(n+1)$ is true $\forall n\in\Z^{+}$ , the principle of mathematical induction shows that $P(n)$ is true for all positive integers $n$ .

for all nonnegative integers $n$ .

The next example uses the principle of mathematical induction to prove an inequality.

for all positive integers $n$ .

[Hint: $x^{n+1} - 1 = (x-1)x^n + (x^{n} - 1 )$ .]

Sometimes we need to show that $P(n)$ is true for $n = k, k + 1, k + 2, \ldots$ , where $k$ is an integer other than 0 or 1. We can use mathematical induction to accomplish this as long as we change the basis step.

The second principle of mathematical induction

There is another form of mathematical induction that is often useful in proofs. With this form we use the same basis step as before, but we use a different inductive step. We assume that $P(k)$ is true for all values $k = 1,\ldots, n$ and show that $P(n + 1 )$ must also be true based on this assumption. This is called the second principle of mathematical induction. We summarize the two steps used to show that $P(n)$ is true for all positive integers $n:$

Basis step: The proposition $P(1)$ is shown to be true.

Inductive step: It is shown that

is true for every positive integer $n$ .

The two forms of mathematical induction are equivalent; that is, each can be shown to be a valid proof technique assuming the other. We leave it as an exercise for the student to show this.

Solution.

Let $P(n)$ denote the proposition that $n$ can be written as a product of primes.

Basis step: $P(2)$ is true since it can be written as the product of one prime, itself.

Inductive step: Assume that $P(k)$ is true for all positive integers $k$ with $k\leq n$ . To complete the inductive step it must be shown that $P(n+1)$ is true under this assumption. There are two cases to consider, namely, when $n+1$ is prime and when $n+1$ is composite. If $n+1$ is prime then we can immediately see that $P(n+1)$ is true. Otherwise $n+1$ is composite and thus can be written as a product of two positive integers $a$ and $b$ with $2\leq a\leq b<n+1$ . By the induction hypothesis, both $a$ and $b$ can be written as the product of primes. Thus, if $n+1$ is composite, then it can be written as the product of primes, namely, those primes in the factorizations of $a$ and $b$ .

Loop invariant theorem

Consider a segment of computer program of the form

The condition $G$ is called the guard and $B$ is called the body. An iteration of the loop is one execution of $B$ . The loop terminates when the guard condition becomes false.

A statement $S$ is a loop invariant if, whenever $S$ is true before an iteration, $S$ remains true after the iteration.

Input: $m, n \in \mathbb{P}$

1. Set $q = 0$ and $r = n$

2. While ($r \ge m$ ) do

   • $q = q + 1$
   • $r = r - m$

Let $S$ be the statement $n = mq + r$ . Then $S$ is true at the beginning of the loop and $S$ stays true through the body of the loop.

Theorem 3.2 (Loop invariant theorem) Let $S$ be an invariant of the loop “while $G$ do $B$ “. Suppose $S$ is true on the first entry into the loop. Then $S$ stays true at every iteration of the loop, and if the loop terminates then $S$ is true after the last iteration.

Recursive definitions

Sometimes it is difficult to define an object explicitly. However, it may be easy to define this object in terms of itself. This process is called recursion_.

We can use recursion to define sequences, functions, and sets. In previous discussions, we specified the terms of a sequence using an explicit formula.

To define a function with the set of nonnegative integers as its domain,

1. Specify the value of the function at zero (and possibly 1, 2, … ).

2. Give a rule for finding its value at an integer from its values at smaller integers.

Such a definition is called a recursive or iterative or inductive definition.

Find $f (1), f (2), f (3)$ , and $f (4)$ .

In some recursive definitions of functions, the values of the function at the first $k$ positive integers are specified, and a rule is given for the determining the value of the function at larger integers from its values at some or all of the preceding $k$ integers.

for $n=2,3,4,\ldots$ . What are the Fibonacci numbers $f_{2}, f_{3}, f_{4}, f_{5}, f_{6}$ ?

Recurrence relations

Consider the following type of counting problem:

In the previous section we discussed how sequences can be defined recursively. Recursive definitions can be used to solve counting problems. When they are, the rule for finding terms from those that precede them is called a recurrence relation.

Definition 3.1 A recurrence relation for the sequence $\{a_{n}\}$ is a formula that expresses $a_{n}$ in terms of one or more of the previous terms of the sequence, namely, $a_{0}, a_{1}, \ldots, a_{n-1}$ , for all integers $n$ with $n \geq n_{0}$ where $n_{0}$ is a nonnegative integer.

A sequence is called a solution of a recurrence relation if its terms satisfy the recurrence relation.

The initial conditions for a sequence specify the terms that precede the first term where the recurrence relation takes effect.

The recurrence relation and initial conditions uniquely determine a sequence. This is the case since a recurrence relation, together with initial conditions, provide a recursive definition of the sequence. Any term of the sequence can be found from the initial conditions using the recurrence relation a sufficient number of times. However, there are better ways for computing the terms of certain classes of sequences defined by recurrence relations and initial conditions.

We can use recurrence relations to model a wide variety of problems, such as finding compound interest, counting rabbits an island, determining the number of moves in the tower of Hanoi puzzle, and counting bit strings with certain properties.

The next example shows how the population of rabbits on an island can be modelled using a recurrence relation.

The next example involves a famous puzzle.

Initially these discs are placed on the first peg in order of size, with the largest on the bottom. The rules of the puzzle allow discs to be moved one at a time from one peg to another as long as a disc is never placed on top of a smaller disc.

The goal of the puzzle is to have all the discs on the second peg in order of size, with the largest on the bottom.

Let $H_{n}$ denote the number of moves needed to solve the Towers of Hanoi problem with $n$ discs. Set up a recurrence relation for the sequence $\{H_{n}\}$ .

Non-consecutive $0$ ‘s

The next example shows how a recurrence relation can be used to model the number of codewords that are allowable using certain validity checks.

Let $a_{n}$ be the number of valid $n$ -digit codewords. Find a recurrence relation for $a_{n}$ .

Solving recurrence relations

A wide variety of recurrence relations occur in models. Some of these recurrence relations can be solved using iteration or some other ad hoc technique. However, one important class of recurrence relations can be explicitly solved in a systematic way. These are recurrence relations that express the terms of a sequence as linear combinations of previous terms.

Definition 3.2 A linear homogeneous recurrence relation of degree $k$ with constant coefficients is a recurrence relation of the form

where $c_{1}, c_{2}, \ldots, c_{k}$ are real numbers, and $c_{k}\not = 0.$

The recurrence relation in the definition is linear since the right-hand side is a sum of constant multiples of the previous terms of the sequence. The recurrence relation is homogeneous since no terms occur that are not multiples of the $a_{j}$ ‘s. The coefficients of the terms of the sequence are all constants, rather than functions that depend on $n$ . The degree is $k$ because $a_{n}$ is expressed in terms of the previous $k$ terms of the sequence.

A consequence of the second principle of mathematical induction is that a sequence satisfying the recurrence relation in the definition is uniquely determined by this recurrence relation and the $k$ initial conditions

Linear homogeneous recurrence relations are studied for two reasons. First, they often occur in modelling of problems. Second, they can be systematically solved.

Solving linear homogeneous recurrence relations

The basic approach for solving linear homogeneous recurrence relations is to look for solutions of the form $a_{n} = r^{n}$ , where $r$ is a constant. Note that $a_{n} = r^{n}$ is a solution of the recurrence relation

if and only if

When both sides of this equation are divided by $r^{n-k}$ and the right-hand side is subtracted from the left, we obtain the equivalent equation

Consequently, the sequence $\{a_{n}\}$ with $a_{n} = r^{n}$ is a solution if and only if $r$ is a solution of this last equation, which is called the characteristic equation of the recurrence relation. The solutions of this equation are called the characteristic roots of the recurrence relation. As we will see, these characteristic roots can be used to give an explicit formula for all the solutions of the recurrence relation.

We now turn our attention to linear homogeneous recurrence relations of degree two. First, consider the case when there are two distinct characteristic roots.

Theorem 3.3 Let $c_{1}$ and $c_{2}$ be real numbers. Suppose that $r^{2} - c_{1}r - c_{2} = 0$ has two distinct roots $r_{1}$ and ” $r_{2}$ . Then the sequence $\{a_{n}\}$ is a solution of the recurrence relation

if and only if $a_{n} = \beta_{1} r_{1}^{n}+\beta_{2}r_{2}^{n}$ for $n = 0,1,2,\ldots$ , where $\beta_{1}$ and $\beta_{2}$ are constants.

Proof: See lecture

The actual procedure for solving the recurrence relation

with initial values $a_0$ and $a_1$ is the following (provided that the roots of the characteristic equation are distinct.):

Step 1 : Identify the characteristic polynomial $p(x)$ and find its roots $r_1$ and $r_2$

Step 2 : If $r_1\not= r_2$ then the general solution is of the form

where $\beta_1$ and $\beta_2$ are constants.

Step 3 : Determine the values of $\beta_1$ and $\beta_2$ by using the initial conditions $a_0$ and $a_1$ .

with initial values $a_0=1$ and $a_1=-1$ .

Solution

Step 1 Determine the characteristic equation by substituting $a_n=r^n$ and factoring out $r^n$ __

Take $r_1=-3$ and $r_2=1$ .

Step 2 The general solution is

Step 3 Using the initial values $a_0=1$ and $a_1=-1$ we obtain

and this gives us $\beta_1=\beta_2=\frac{1}{2}$ . Thus $a_n=\frac{1}{2}+\frac{1}{2}(-3)^n,\qquad n\geq0$ is the unique solution to the given recurrence relation.

with $a_{0} = 2$ and $a_{1} = 7$ ?

Theorem 4.2 does not apply when there is one characteristic root of multiplicity two. This case can be handled using the following theorem.

Theorem 3.4 Let $c_{1}$ and $c_{2}$ be real numbers with $c_{2}\not = 0$ . Suppose that $r^{2} - c_{1}r - c_{2} = 0$ has only one root $r_{1}$ . A sequence $\{a_{n}\}$ is a solution of the recurrence relation $a_{n} = c_{1}a_{n-1} + c_{2}a_{n-2}$ if and only if $a_{n} = \beta_{1}r_{1}^{n} + \beta_{2}nr_{1}^{n}$ , for $n = 0, 1, 2, \ldots$ , where $\beta_{1}$ and $\beta_{2}$ are constants.

The actual procedure for solving the recurrence relation

with initial values $a_0$ and $a_1$ is the following (provided that the roots of the characteristic equation are not distinct):

Step 1 : Identify the characteristic polynomial $p(x)$ and find its roots $r_1$ and $r_2$

Step 2 : If $r_1=r_2$ then the general solution is of the form

where $\beta_1$ and $\beta_2$ are constants.

Step 3 : Determine the values of $\beta_1$ and $\beta_2$ by using the initial conditions $a_0$ and $a_1$ .

with initial values $a_0=1$ and $a_1=-3$ .

with initial conditions $a_{0} = 1$ and $a_{1} = 6$ ?