Page 350 - Discrete Mathematics and Its Applications

5.1 Mathematical Induction 329

Template for Proofs by Mathematical Induction

1. Express the statement that is to be proved in the form “for all n ≥ b, P (n)”forafixed
integer b.
2. Write out the words “Basis Step.” Then show that P(b) is true, taking care that the correct
value of b is used. This completes the first part of the proof.
3. Write out the words “Inductive Step.”
4. State, and clearly identify, the inductive hypothesis, in the form “assume that P(k) is true
for an arbitrary fixed integer k ≥ b.”
5. State what needs to be proved under the assumption that the inductive hypothesis is true.
That is, write out what P(k + 1) says.
6. Prove the statement P(k + 1) making use the assumption P(k). Be sure that your proof
is valid for all integers k with k ≥ b, taking care that the proof works for small values
of k, including k = b.
7. Clearly identify the conclusion of the inductive step, such as by saying “this completes
the inductive step.”
8. After completing the basis step and the inductive step, state the conclusion, namely that
by mathematical induction, P (n) is true for all integers n with n ≥ b.

It is worthwhile to revisit each of the mathematical induction proofs in Examples 1–14 to see
how these steps are completed. It will be helpful to follow these guidelines in the solutions of the
exercises that ask for proofs by mathematical induction. The guidelines that we presented can
be adapted for each of the variants of mathematical induction that we introduce in the exercises
and later in this chapter.

Exercises

1. There are infinitely many stations on a train route. Sup- f) Explain why these steps show that this formula is true
pose that the train stops at the first station and suppose whenever n is a positive integer.
that if the train stops at a station, then it stops at the next 4. Let P(n) be the statement that 1 + 2 + ··· + n =
3
3
3
station. Show that the train stops at all stations. (n(n + 1)/2) for the positive integer n.
2
a) What is the statement P(1)?
2. Suppose that you know that a golfer plays the first hole of
a golf course with an infinite number of holes and that if b) Show that P(1) is true, completing the basis step of
this golfer plays one hole, then the golfer goes on to play the proof.
the next hole. Prove that this golfer plays every hole on c) What is the inductive hypothesis?
the course.
d) What do you need to prove in the inductive step?
Use mathematical induction in Exercises 3–17 to prove sum-
mation formulae. Be sure to identify where you use the in- e) Complete the inductive step, identifying where you
ductive hypothesis. use the inductive hypothesis.
2 2 2 f) Explain why these steps show that this formula is true
3. Let P(n) be the statement that 1 + 2 + ··· + n =
whenever n is a positive integer.
n(n + 1)(2n + 1)/6 for the positive integer n.
2
2
2
2
a) What is the statement P(1)? 5. Prove that 1 + 3 + 5 + ··· + (2n + 1) = (n + 1)
(2n + 1)(2n + 3)/3 whenever n is a nonnegative integer.
b) Show that P(1) is true, completing the basis step of
6. Prove that 1 · 1!+ 2 · 2! + ··· + n · n!= (n + 1)!− 1
the proof.
whenever n is a positive integer.
c) What is the inductive hypothesis?
n
2
7. Prove that 3 + 3 · 5 + 3 · 5 +···+ 3 · 5 =3(5 n+1 − 1)/4
d) What do you need to prove in the inductive step? whenever n is a nonnegative integer.
n
2
e) Complete the inductive step, identifying where you 8. Prove that 2 − 2 · 7 + 2 · 7 − ··· + 2(−7) = (1 −
use the inductive hypothesis. (−7) n+1 )/4 whenever n is a nonnegative integer.