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 ﬁrst 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 ﬁrst

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

.