Recursion - Data Structures and Problem Solving Using Java - page 295

background: proofs by
mathematical induction

7.2

In this section we discuss proof by mathematical induction . (Throughout this
chapter we omit the word mathematical when describing this technique.)
Induction is commonly used to establish theorems that hold for positive inte-
gers. We start by proving a simple theorem, Theorem 7.1. This particular the-
orem can be easily established by using other methods, but often a proof by
induction is the simplest mechanism.

Induction is an
important proof
technique used to
establish theorems
that hold for posi-
tive integers.

For any integer N 1 ≥ , the sum of the first N integers, given by

, equals

Theorem 7.1

12 …

N

∑

i = ++ + N NN 1 ( + ) ⁄ 2 .

i = 1

Obviously, the theorem is true for N = 1 because both the left-hand and right-
hand sides evaluate to 1. Further checking shows that it is true for 2 10.

However, the fact that the theorem holds for all N that are easy to check by hand
does not imply that it holds for all N . Consider, for instance, numbers of the form
. The first five numbers (corresponding to are 3, 5, 17, 257,
and 65,537. These numbers are all prime. Indeed, at one time mathematicians
conjectured that all numbers of this form are prime. That is not the case. We can
easily check by computer that

≤ N ≤

2 2 k + 1 0 ≤≤ k 4)

˙

2 2 5 + 1 = 641 × 6,700,417 . In fact, no other

prime of the form 2 2 k + 1 is known.

A proof by induction is carried out in two steps. First, as we have just
done, we show that the theorem is true for the smallest cases. We then show
that if the theorem is true for the first few cases, it can be extended to include
the next case. For instance, we show that a theorem that is true for all
must be true for . Once we have shown how to extend
the range of true cases, we have shown that it is true for all cases. The reason
is that we can extend the range of true cases indefinitely. We use this tech-
nique to prove Theorem 7.1.

A proof by induc-
tion shows that the
theorem is true for
some simple cases
and then shows
how to extend the
range of true cases
indefinitely.

1 Nk ≤≤ 1 Nk 1 ≤≤ +

Clearly, the theorem is true for N = 1 . Suppose that the theorem is true for all

Proof of
Theorem 7.1

1 Nk ≤≤ . Then

.

∑

k + 1

∑

k

(7.1) i = ( k + 1 ) + i

i = 1 i = 1

(continued on next page)