# Proof by Induction

Tags:
1. Dec 4, 2014

### Math325

1. The problem statement, all variables and given/known data
1 + 2 + 2^2 + 2^3 + ...+2^(n-1) = 2^n - 1
2. Relevant equations
Sum formula?

3. The attempt at a solution

I know you are suppose to use the base case and prove its true for k +1, but I'm not sure what to do for similar bases. Can someone please solve it step by step? Thanks!

2. Dec 4, 2014

### Staff: Mentor

No, we won't "solve" it for you step by step. The Physics Forums rules expressly forbid this. Anyway, you're not "solving" this problem, you need to prove that the statement above is true for all integers n, n ≥ 1.

For an induction proof, you need to do three things.
1. Show that the statement is true for n = 1 or whatever the base case is. Do you know what statement you need to prove when n = 1?
2. Assume that the statement is true for n = k. What does this statement look like?
3. Show that the statement is true for n = k + 1. You will need to use the assumption of step 2 to do this.

3. Dec 6, 2014

### RUber

If you don't have to use induction, you can let A = the sum, and see what 2A looks like. 2A-A=A.

4. Dec 8, 2014

### HallsofIvy

Staff Emeritus
I'm not sure what you mean by "similar bases". What similar bases are you referring to?

This says that 1= 2^1- 1= 2- 1, 1+ 2= 2^2- 1= 4- 1= 3 , 1+ 2+ 4= 2^3- 1= 8- 1= 7, etc.
The "base case" is, of course, when n= 1. Is "1= 2^1- 1" true?
Now, suppose 1+ 2+ 4+ 8+ ...+ 2^(n-1)= 2^n- 1. Write 1+ 2+ 4+ 8+ ...+ 2^(n-1)+ 2^n= (1+ 2+ 4+ 8+ ...+ 2^(n-1))+ 2^n