The problem is 1 + 2 + 2^2 + ... + 2^(n-1) = (2^n) - 1
I'm just confused on how to add the next term to both sides because the next term is 2^n so when you plug n into the other side it doesn't change. Or is that correct?
I'm just confused on how to add the next term to both sides because the next term is 2^n so when you plug n into the other side it doesn't change. Or is that correct?
-
Base step: Plug in n = 1:
1 = 2^(1) - 1 = 1, so this checks out
Then we assume that 1 + 2 + 2² + ... + 2^(n - 1) = 2^(n) - 1 is true. With this assumption, we look at the case where we replace n with n+1. Plugging this into the left side we get:
1 + 2 + 2² + ... + 2^(n - 1) + 2^((n + 1) - 1)
This is the same as:
1 + 2 + 2² + ... + 2^(n - 1) + 2^(n)
Then remember that we assumed 1 + 2 + 2² + ... + 2^(n - 1) = 2^(n) - 1 is true, so we can rewrite the above statement as:
[1 + 2 + 2² + ... + 2^(n - 1)] + 2^(n) = [2^(n) - 1)] + 2^(n)
Now we want to show that this equals 2^(n+1) - 1. So we apply some algebra:
2^(n) - 1 + 2^(n)
= 2*2^(n) - 1
= 2^(n + 1) - 1
Thus we have shown:
1 + 2 + 2² + ... + 2^(n - 1) + 2^((n + 1) - 1) = 2^(n+1) - 1
This means we have proven the case of n+1 and by mathematical induction, 1 + 2 + 2^2 + ... + 2^(n-1) = (2^n) - 1 follows.
1 = 2^(1) - 1 = 1, so this checks out
Then we assume that 1 + 2 + 2² + ... + 2^(n - 1) = 2^(n) - 1 is true. With this assumption, we look at the case where we replace n with n+1. Plugging this into the left side we get:
1 + 2 + 2² + ... + 2^(n - 1) + 2^((n + 1) - 1)
This is the same as:
1 + 2 + 2² + ... + 2^(n - 1) + 2^(n)
Then remember that we assumed 1 + 2 + 2² + ... + 2^(n - 1) = 2^(n) - 1 is true, so we can rewrite the above statement as:
[1 + 2 + 2² + ... + 2^(n - 1)] + 2^(n) = [2^(n) - 1)] + 2^(n)
Now we want to show that this equals 2^(n+1) - 1. So we apply some algebra:
2^(n) - 1 + 2^(n)
= 2*2^(n) - 1
= 2^(n + 1) - 1
Thus we have shown:
1 + 2 + 2² + ... + 2^(n - 1) + 2^((n + 1) - 1) = 2^(n+1) - 1
This means we have proven the case of n+1 and by mathematical induction, 1 + 2 + 2^2 + ... + 2^(n-1) = (2^n) - 1 follows.
-
Not as confused as I am