Page 338 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 317

From these values it is reasonable to conjecture that the sum of the first n positive odd integers
2
2
is n , that is, 1 + 3 + 5 + ··· + (2n − 1) = n . We need a method to prove that this conjecture
is correct, if in fact it is.
2
Let P (n) denote the proposition that the sum of the first n odd positive integers is n . Our
conjecture is that P (n) is true for all positive integers. To use mathematical induction to prove
this conjecture, we must first complete the basis step; that is, we must show that P(1) is true.
Then we must carry out the inductive step; that is, we must show that P(k + 1) is true when
P(k) is assumed to be true. We now attempt to complete these two steps.
2
BASIS STEP: P(1) states that the sum of the first one odd positive integer is 1 . This is true
because the sum of the first odd positive integer is 1. The basis step is complete.
INDUCTIVE STEP: To complete the inductive step we must show that the proposition
P(k) → P(k + 1) is true for every positive integer k. To do this, we first assume the inductive
hypothesis. The inductive hypothesis is the statement that P(k) is true for an arbitrary positive
integer k, that is,
2
1 + 3 + 5 + ··· + (2k − 1) = k .
(Note that the kth odd positive integer is (2k − 1), because this integer is obtained by adding 2 a
total of k − 1 times to 1.) To show that ∀k(P (k) → P(k + 1)) is true, we must show that if P(k)
is true (the inductive hypothesis), then P(k + 1) is true. Note that P(k + 1) is the statement that

2
1 + 3 + 5 + ··· + (2k − 1) + (2k + 1) = (k + 1) .
So, assuming that P(k) is true, it follows that

1 + 3 + 5 + ··· + (2k − 1) + (2k + 1) =[1 + 3 + ··· + (2k − 1)]+ (2k + 1)
IH 2
= k + (2k + 1)
2
= k + 2k + 1
2
= (k + 1) .
This shows that P(k + 1) follows from P(k). Note that we used the inductive hypothesis P(k)
2
in the second equality to replace the sum of the first k odd positive integers by k .
We have now completed both the basis step and the inductive step. That is, we have shown
thatP(1)istrueandtheconditionalstatementP(k) → P(k + 1)istrueforallpositiveintegersk.
Consequently, by the principle of mathematical induction we can conclude that P (n) is true for
2
all positive integers n. That is, we know that 1 + 3 + 5 + ··· + (2n − 1) = n for all positive
integers n. ▲

Often, we will need to show that P (n) is true for n = b, b + 1, b + 2,..., where b is an
integer other than 1.We can use mathematical induction to accomplish this, as long as we change
the basis step by replacing P(1) with P(b). In other words, to use mathematical induction to
show that P(n) is true for n = b, b + 1,b + 2,..., where b is an integer other than 1, we show
that P(b) is true in the basis step. In the inductive step, we show that the conditional statement
P(k) → P(k + 1) is true for k = b, b + 1,b + 2,.... Note that b can be negative, zero, or
positive. Following the domino analogy we used earlier, imagine that we begin by knocking
down the bth domino (the basis step), and as each domino falls, it knocks down the next domino
(the inductive step). We leave it to the reader to show that this form of induction is valid (see
Exercise 83).
We illustrate this notion in Example 3, which states that a summation formula is valid for
all nonnegative integers. In this example, we need to prove that P(n) is true for n = 0, 1, 2,....
So, the basis step in Example 3 shows that P(0) is true.