Page 333 - Discrete Mathematics and Its Applications

312 5 / Induction and Recursion

. .
. . . .
We can reach step k + 1 if
we can reach step k

Step k + 1
Step k

Step 4
Step 3
We can reach
step 1
Step 2
Step 1

FIGURE 1 Climbing an Infinite Ladder.

can reach the fourth rung, the fifth rung, and so on. For example, after 100 uses of (2), we know
that we can reach the 101st rung. But can we conclude that we are able to reach every rung
of this infinite ladder? The answer is yes, something we can verify using an important proof
technique called mathematical induction. That is, we can show that P (n) is true for every
positive integer n, where P (n) is the statement that we can reach the nth rung of the ladder.
Mathematical induction is an extremely important proof technique that can be used to prove
assertions of this type. As we will see in this section and in subsequent sections of this chapter
and later chapters, mathematical induction is used extensively to prove results about a large
variety of discrete objects. For example, it is used to prove results about the complexity of
algorithms, the correctness of certain types of computer programs, theorems about graphs and
trees, as well as a wide range of identities and inequalities.
In this section, we will describe how mathematical induction can be used and why it is a
valid proof technique. It is extremely important to note that mathematical induction can be used
only to prove results obtained in some other way. It is not a tool for discovering formulae or
theorems.

Mathematical Induction

In general, mathematical induction ∗ can be used to prove statements that assert that P(n) is
true for all positive integers n, where P(n) is a propositional function. A proof by mathematical

∗ Unfortunately, using the terminology “mathematical induction” clashes with the terminology used to describe different types
of reasoning. In logic, deductive reasoning uses rules of inference to draw conclusions from premises, whereas inductive
reasoning makes conclusions only supported, but not ensured, by evidence. Mathematical proofs, including arguments that
use mathematical induction, are deductive, not inductive.