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

Daaniyaal · Sep 5, 2012

1. The problem statement, all variables and given/known data[/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 · Sep 5, 2012

Daaniyaal said: ↑

1. The problem statement, all variables and given/known data[/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 · Sep 6, 2012

You want to prove that if, for some k, [itex]2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}= 2^k-1[/itex] then [itex]2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}+ 2^k= 2^{k+1}-1[/itex].
(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 [itex]2^k[/itex] to the sum on the left so do it on the right:
[tex]2^0+ 2^1+ \cdot\cdot\cdot+ 2^{k-1}+ 2^k= (2^k- 1)+ 2^k[/tex]

What do you get when you combine those two "[itex]2^k[/itex]" terms on the right?

Daaniyaal · Sep 6, 2012

I figured it out, thanks!

Log in or Sign up

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

Daaniyaal

Ray Vickson

HallsofIvy

Daaniyaal

Prove 2^n > 1/2(n+1)² is true help! (Replies: 15)

Show that 2^(k-1) doesn't divide n(n-1)/2 (Replies: 11)

2(-1)^n = -2? Problem with (-1) to the power of natural numbers (Replies: 1)

Why Is the Sum of 1/2 (n+1)/2? (Replies: 1)

Any integer = a_0 * 2^n + a_1 * 2^(n – 1) + a_2 * 2^(n – 2) + + a_n (Replies: 9)