Induction: 1+2+2^2+2^3+ +2^n-1=2^n-1

[Daaniyaal]

1. Homework Statement [/b]
Use mathematical induction to prove the following statements are true for all integers n≥1
1+2+2^2+2^3+...+2^n-1=2^n-1



Attempt at a solution:


For n=1

1+2^(1-1)=2^1-1
1=1
∴ it is true.


Let Sn=Sk
If it is true for k, it must also be true for k+1

1+2+2^2+2^3+...+2^k+2^k+1-1=(2^k+1)-1

This is the part I have a slight confusion at, I keep getting something left over and the sides don't equal each other :(

 

[Ray Vickson]

1. Homework Statement [/b]
Use mathematical induction to prove the following statements are true for all integers n≥1
1+2+2^2+2^3+...+2^n-1=2^n-1



Attempt at a solution:


For n=1

1+2^(1-1)=2^1-1
1=1
∴ it is true.


Let Sn=Sk
If it is true for k, it must also be true for k+1

1+2+2^2+2^3+...+2^k+2^k+1-1=(2^k+1)-1

This is the part I have a slight confusion at, I keep getting something left over and the sides don't equal each other :(

Use brackets: you have written
1+2+2^2+2^3+...+2^n-1=2^n-1 , which is plainly impossible, because it would require that we have 1+2+2^2+2^3+... = 0 (in order to have 2^n-1=2^n-1 on both sides). If you mean 2^(n-1), then that is what you need to say.

RGV

 

[HallsofIvy]

You want to prove that if, for some k, $2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}= 2^k-1$ then $2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}+ 2^k= 2^{k+1}-1$.
(What you wrote, 1+ 2^1+ ...+ 2^n-1= 2^n-1 is, as Ray Vickson said, clearly impossible because you have "2^n- 1" on both sides but with additional positive terms on the left. Of course, you meant 2^(n-1) on the left and (2^n)- 1 on the right. Those are very different and you can't ask people to guess what you mean.)

To go from k to k+1, obviously you are adding $2^k$ to the sum on the left so do it on the right:
$$2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}+ 2^k= (2^k- 1)+ 2^k$$

What do you get when you combine those two "$2^k$" terms on the right?

 

[Daaniyaal]

I figured it out, thanks!