114
Proofs, Induction, and Number Theory
The key to an inductive proof is to find a way to relate what we want to show—
P(k + 1), equation (3)—to what we have assumed—P(k), equation (2). The left
side of P(k + 1) can be rewritten to show the next-to-last term:
1 + 3 + 5 + c + (2k − 1) + 32(k + 1) − 1 4
This expression contains the left side of equation (2) as a subexpression. Because
we have assumed P(k) to be true, we can substitute the right side of equation (2)
for this subexpression. Thus,
1 + 3 + 5 + c + 32(k + 1) − 1 4
= 1 + 3 + 5 + c + (2k − 1) + 32(k + 1) − 14
= k
2
+ 32(k + 1) − 1 4
= k
2
+ 32k + 2 − 1 4
= k
2
+ 2k + 1
= (k + 1)
2
Therefore,
1 + 3 + 5 + c + 32(k + 1) − 1 4 = (k + 1)
2
which verifies P(k + 1) and proves that equation (1) is true for any positive
integer n.
Table 2.3 summarizes the three steps necessary for a proof using the first
principle of induction.
Any “summation” induction problem works exactly the same way. Write the summation including the next-to-last term, and you will find the left side of the P(k) equation
and can use the inductive hypothesis. After that, it’s just a question of algebra.
ExamplE 15
Prove that
1 + 2 + 2
2
+ c + 2
n
= 2
n+1
− 1
for any n ≥ 1.
Again, induction is appropriate. P(1) is the equation
1 + 2 = 2
1+1
− 1
or
3 = 2
2
− 1
TablE 2.3
To prove by First principle of Induction
Step 1
Prove base case.
Step 2
Assume P(k).
Step 3
Prove P(k + 1).