• Support PF! Buy your school textbooks, materials and every day products Here!

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

  • Thread starter Daaniyaal
  • Start date
  • #1
64
0
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 :(
 

Answers and Replies

  • #2
Ray Vickson
Science Advisor
Homework Helper
Dearly Missed
10,706
1,728
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
 
  • #3
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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?
 
Last edited by a moderator:
  • #4
64
0
I figured it out, thanks!
 

Related Threads on Induction: 1+2+2^2+2^3+ +2^n-1=2^n-1

  • Last Post
Replies
7
Views
1K
Replies
15
Views
76K
Replies
12
Views
2K
  • Last Post
Replies
5
Views
3K
  • Last Post
Replies
9
Views
3K
  • Last Post
Replies
14
Views
16K
Replies
8
Views
9K
Replies
6
Views
5K
Replies
5
Views
920
Top