Monday, August 8, 2016

Precalculus, Chapter 9, 9.4, Section 9.4, Problem 15

You need to use mathematical induction to prove the formula for every positive integer n, hence, you need to perform the two steps of the method, such that:
Step 1: Basis: Show that the statement P(n) hold for n = 1, such that:
1 = 2^1 - 1=> 1 = 1
Step 2: Inductive step: Show that if P(k) holds, then also P(k + 1) holds:
P(k): 1 + 2 + 2^2 + .. + 2^(k-1) = 2^k - 1 holds
P(k+1): 1 + 2 + 2^2 + .. + 2^(k-1) + 2^k = 2^(k+1) - 1
You need to use induction hypothesis that P(k) holds, hence, you need to re-write the left side, such that:
2^k - 1 + 2^k = 2^(k+1) - 1
Reduce like terms, such that:
2^k + 2^k = 2^(k+1)
2*2^k = 2^(k+1)
Use the rule of exponents:
2^(k+1) = 2^(k+1)
Notice that P(k+1) holds.
Hence, since both the basis and the inductive step have been verified, by mathematical induction, the statement P(n): 1 + 2 + 2^2 + .. + 2^(n-1) = 2^n - 1 holds for all positive integers n.

No comments:

Post a Comment

Why is the fact that the Americans are helping the Russians important?

In the late author Tom Clancy’s first novel, The Hunt for Red October, the assistance rendered to the Russians by the United States is impor...