# Induction question

1. Sep 25, 2009

### zeion

1. The problem statement, all variables and given/known data

Show that the statement holds for all positive integers n

$$2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{n-1} = 2^n - 1$$

2. Relevant equations

3. The attempt at a solution

Assume:
$$2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{k-1} = 2^k - 1$$ is true.

Then:
$$2^{k+1}-1 = 2^k(2) - 1 = 2(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{k-1})$$

Not sure what to do next :/

Show that:
$$2^k(2) - 1 = 2(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{k-1})$$ is true

2. Sep 25, 2009

### tiny-tim

Hi zeion!

You have the right basic idea, but you're making it too complicated.

Do the obvious

just multiply both sides of the original equation by 2 (and then fiddle about with it).

3. Sep 25, 2009

### zeion

Since:
$$2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{k-1} = 2^k - 1$$

Then:
$$(2)(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{k-1}) = (2)2^k - 1 = 2^{k+1}-1$$

4. Sep 26, 2009

### tiny-tim

No, it isn't … be careful!

$$(2)(2^0 + 2^1 + 2^2 + 2^3 + ... + 2^{k-1}) = (2)(2^k - 1) = \cdots\ ?$$