Page 337 - Discrete Mathematics and Its Applications

316 5 / Induction and Recursion

EXAMPLE 1 Show that if n is a positive integer, then

n(n + 1)
1 + 2 + ··· + n = .
2

Solution: Let P (n) be the proposition that the sum of the first n positive integers, 1 + 2 + ··· n =
n(n+1)
2 ,is n(n + 1)/2. We must do two things to prove that P (n) is true for n = 1, 2, 3,....
Namely,wemustshowthatP(1)istrueandthattheconditionalstatementP(k)impliesP(k + 1)
is true for k = 1, 2, 3,....
1(1 + 1)
BASIS STEP: P(1) is true, because 1 = . (The left-hand side of this equation is 1
2
because 1 is the sum of the first positive integer. The right-hand side is found by substituting 1
for n in n(n + 1)/2.)
INDUCTIVE STEP: For the inductive hypothesis we assume that P(k) holds for an arbitrary
positive integer k. That is, we assume that
If you are rusty
simplifying algebraic
expressions, this is the k(k + 1)
1 + 2 + ··· + k = .
time to do some 2
reviewing!
Under this assumption, it must be shown that P(k + 1) is true, namely, that

(k + 1)[(k + 1) + 1] (k + 1)(k + 2)
1 + 2 + ··· + k + (k + 1) = =
2 2

is also true. When we add k + 1 to both sides of the equation in P(k), we obtain

IH k(k + 1)
1 + 2 + ··· + k + (k + 1) = + (k + 1)
2
k(k + 1) + 2(k + 1)
=
2
(k + 1)(k + 2)
= .
2
This last equation shows that P(k + 1) is true under the assumption that P(k) is true. This
completes the inductive step.
We have completed the basis step and the inductive step, so by mathematical induction we
know that P (n) is true for all positive integers n. That is, we have proven that 1 + 2 + ··· + n =
n(n + 1)/2 for all positive integers n. ▲

As we noted, mathematical induction is not a tool for finding theorems about all positive
integers. Rather, it is a proof method for proving such results once they are conjectured. In
Example 2, using mathematical induction to prove a summation formula, we will both formulate
and then prove a conjecture.

EXAMPLE 2 Conjecture a formula for the sum of the first n positive odd integers. Then prove your conjecture
using mathematical induction.

Solution: The sums of the first n positive odd integers for n = 1, 2, 3, 4, 5 are

1 = 1, 1 + 3 = 4, 1 + 3 + 5 = 9,
1 + 3 + 5 + 7 = 16, 1 + 3 + 5 + 7 + 9 = 25.