Section 2.2 Induction
115
The following summation formula is the most important one because it occurs so often in the analysis of algorithms. If you don’t remember anything else,
you should remember this formula for the sum of the first n positive integers.
Not all proofs by induction involve formulas with sums. Other algebraic identities about the positive integers, as well as nonalgebraic assertions like the number of offspring in generation n of the Smith family, can be proved by induction.
PrACTiCe 7 Prove that for any positive integer n,
1 + 2 + 3 + c + n =
n(n+1)
2
■
ReMinDeR
To prove
P(k) S P(k + 1), you have
to discover the P(k) case
within the P(k + 1) case.
which is true. We take P(k)
1 + 2 + 2
2
+ c + 2
k
= 2
k+1
− 1
as the inductive hypothesis and try to establish P(k + 1):
1 + 2 + 2
2
+ c + 2
k+1 0 2
k+1+1
− 1
Rewriting the sum on the left side of P(k + 1) reveals how the inductive assumption can be used:
1 + 2 + 2
2
+ c + 2
k+1
= 1 + 2 + 2
2
+ c + 2
k
+ 2
k+1
= 2
k+1
− 1 + 2
k+1
     (from the inductive hypothesis P(k))
= 2(2
k+1
) − 1        (adding like terms)
= 2
k+1+1
− 1
Therefore,
1 + 2 + 2
2
+ c + 2
k+1
= 2
k+1+1
− 1
which verifies P(k + 1) and completes the proof.
eXAMPLe 16
Prove that for any positive integer n, 2
n
> n.
P(1) is the assertion 2
1
> 1, which is surely true. Now we assume P(k), 2
k
> k,
and try to conclude P(k + 1), 2
k+1
> k + 1. Now, where is P(k) hidden in here?
Aha—we can write the left side of P(k + 1), 2
k+1
, as 2k # 2, and there’s the left side
of P(k). Using the inductive hypothesis 2
k
> k and multiplying both sides of this
inequality by 2, we get 2
k # 2 > k # 2. We complete the argument
2
k+1
= 2
k # 2 > k # 2 = k + k ≥ k + 1 (because k ≥ 1)
or
2
k+1
> k + 1