Page 332 - Discrete Mathematics and Its Applications

CH A P TER

5 Induction and Recursion

5.1 Mathematical any mathematical statements assert that a property is true for all positive integers.
n
3
Induction MExamples of such statements are that for every positive integer n: n!≤ n , n − n is
n
divisible by 3; a set with n elements has 2 subsets; and the sum of the first n positive integers
5.2 Strong
is n(n + 1)/2. A major goal of this chapter, and the book, is to give the student a thorough
Induction and
understanding of mathematical induction, which is used to prove results of this kind.
Well-Ordering
Proofs using mathematical induction have two parts. First, they show that the statement
5.3 Recursive holds for the positive integer 1. Second, they show that if the statement holds for a positive
Definitions and integer then it must also hold for the next larger integer. Mathematical induction is based on the
Structural rule of inference that tells us that if P(1) and ∀k(P (k) → P(k + 1)) are true for the domain of
Induction positive integers, then ∀nP (n) is true. Mathematical induction can be used to prove a tremendous
variety of results. Understanding how to read and construct proofs by mathematical induction
5.4 Recursive
is a key goal of learning discrete mathematics.
Algorithms
In Chapter 2 we explicitly defined sets and functions. That is, we described sets by listing
5.5 Program their elements or by giving some property that characterizes these elements. We gave formulae
Correctness for the values of functions. There is another important way to define such objects, based on
mathematical induction. To define functions, some initial terms are specified, and a rule is
given for finding subsequent values from values already known. (We briefly touched on this
sort of definition in Chapter 2 when we showed how sequences can be defined using recurrence
relations.) Sets can be defined by listing some of their elements and giving rules for constructing
elements from those already known to be in the set. Such definitions, called recursive definitions,
are used throughout discrete mathematics and computer science. Once we have defined a set
recursively, we can use a proof method called structural induction to prove results about this set.
When a procedure is specified for solving a problem, this procedure must always solve
the problem correctly. Just testing to see that the correct result is obtained for a set of input
values does not show that the procedure always works correctly. The correctness of a procedure
can be guaranteed only by proving that it always yields the correct result. The final section of
this chapter contains an introduction to the techniques of program verification. This is a formal
technique to verify that procedures are correct. Program verification serves as the basis for
attempts under way to prove in a mechanical fashion that programs are correct.

5.1 Mathematical Induction

Introduction

Suppose that we have an infinite ladder, as shown in Figure 1, and we want to know whether
we can reach every step on this ladder. We know two things:

1. We can reach the first rung of the ladder.
2. If we can reach a particular rung of the ladder, then we can reach the next rung.

Can we conclude that we can reach every rung? By (1), we know that we can reach the first
rung of the ladder. Moreover, because we can reach the first rung, by (2), we can also reach the
second rung; it is the next rung after the first rung. Applying (2) again, because we can reach
the second rung, we can also reach the third rung. Continuing in this way, we can show that we

311