Subject: problem of induction
Name: Zamira
Who are you: Student (All)

hi, i'm studying induction but i don't get how to proof that 1+2+2^2+2^3+...+2^(n-1) = (2^n) - 1.

if you could help i really would appreciate it.

zamira

Hi Zamira,

I want to state the problem more precisely.

Prove that 1+2+2²+2³+...+2^n-1 = 2ⁿ - 1 for n = 1, 2, 3, ...

There are two steps in a proof by induction, first you need to show that the result is true for the smallest value on n, in this case n = 1.

When n = 1 the left side has only one term, 2^n-1 = 2^1-1 = 2⁰ = 1. The right side is 2ⁿ - 1= 2¹ - 1 = 1. Thus the statement is true for n = 1.

The second step is the inductive step. You need to show that if the statement is true for any particular value of n it is also true for the next value of n. If you can do this then, since it is true for n = 1 it will also be true for the next value of n, n = 2. Then, since it is true for n = 2 it will also be true for n = 3, and so on. To show the inductive step I am going to assume that the statement is true for the particular value of n, n = k. Here is my proof.

Suppose that the statement is true for n = k, that is

1+2+2²+2³+...+2^k-1 = 2^k - 1           equation 1

I need to prove that the statement is true for n = k + 1, that is I need to prove that

1+2+2²+2³+...+2^(k+1)-1 = 2^k+1 - 1                equation 2

The left side of equation 2 is

1+2+2²+2³+...+2^(k+1)-1 = 1+2+2²+2³+...+2^k 

The next to the last term in this sum is 2^k-1 and hence I can write the left side of equation 2 as

1+2+2²+2³+...+2^k-1 + 2^k

But I know that 1+2+2²+2³+...+2^k-1 = 2^k - 1 (this is equation 1) so the left side of equation 2 is is

1+2+2²+2³+...+2^k-1 + 2^k = 2^k - 1 + 2^k = 2(2^k) - 1 = 2^k+1- 1

Hence we have shown that the left side and right side of equation 2 are equal.

This completes the inductive step and hence, by induction, I have proved that

1+2+2²+2³+...+2^n-1 = 2ⁿ - 1 for n = 1, 2, 3, ...

Penny