Section 5.1 Mathematical Induction 115
CHAPTER 5
Induction and Recursion
SECTION 5.1 Mathematical Induction
Important note about notation for proofs by mathematical induction: In performing the inductive
step, it really does not matter what letter we use. We see in the text the proof of P (k) → P (k + 1); but it
would be just as valid to prove P (n) → P (n + 1), since the k in the first case and the n in the second case
are just dummy variables. We will use both notations in this Guide; in particular, we will use k for the first
few exercises but often use n afterwards.
2. We can prove this by mathematical induction. Let P (n) be the statement that the golfer plays hole n. We
want to prove that P (n) is true for all positive integers n. For the basis step, we are told that P (1) is true.
For the inductive step, we are told that P (k) implies P (k + 1) for each k ≥ 1. Therefore by the principle of
mathematical induction, P (n) is true for all positive integers n.
4. a) Plugging in n = 1 we have that P (1) is the statement 1
3
= [1 · (1 + 1)/2]
2
.
b) Both sides of P (1) shown in part (a) equal 1.
c) The inductive hypothesis is the statement that
1
3
+ 2
3
+ ··· + k
3
=
!
k(k + 1)
2
"
2
.
d) For the inductive step, we want to show for each k ≥ 1 that P (k) implies P (k + 1). In other words, we
want to show that assuming the inductive hypothesis (see part (c)) we can prove
[1
3
+ 2
3
+ ··· + k
3
] + (k + 1)
3
=
!
(k + 1)(k + 2)
2
"
2
.
e) Replacing the quantity in brackets on the left-hand side of part (d) by what it equals by virtue of the
inductive hypothesis, we have
!
k(k + 1)
2
"
2
+ (k + 1)
3
= (k + 1)
2
!
k
2
4
+ k + 1
"
= (k + 1)
2
!
k
2
+ 4k + 4
4
"
=
!
(k + 1)(k + 2)
2
"
2
,
as desired.
f) We have completed both the basis step and the inductive step, so by the principle of mathematical induction,
the statement is true for every positive integer n.
6. The basis step is clear, since 1 · 1! = 2! − 1. Assuming the inductive hypothesis, we then have
1 · 1! + 2 · 2! + ··· + k · k! + (k + 1) · (k + 1)! = (k + 1)! − 1 + (k + 1) · (k + 1)!
= (k + 1)!(1 + k + 1) − 1 = (k + 2)! − 1 ,
as desired.
8. The proposition to be proved is P (n):
2 − 2 · 7 + 2 · 7
2
− ··· + 2 · (−7)
n
=
1 − (−7)
n+1
4
.
