Towers of hanoi induction- slight bit i don't understand

  • Thread starter pyrosilver
  • Start date
  • #1
39
0
Towers of hanoi induction-- slight bit i don't understand

Homework Statement


I am trying to prove towers of hanoi. Now I am on the induction part and there is a part I don't get. I have the whole thing, but i don't understand a couple lines.


Homework Equations





The Attempt at a Solution



WTS: f(n+1) = 2n+1 - 1
By the Induction Hypothesis, f(n) = 2n-1.

Earlier, we showed f(n) = f(n-1) + 1 + f(n-1).

By the recursive definition,
f(n+1) = f(n) + 1 + f(n).
f(n+1) = 2f(n) + 1
f(n+1) = 2(2n-1) + 1
f(n+1) = 2(2n - 2) + 1
f(n+1) = 2n+1 - 1.
QED.

Ok I get the first line...get the second line...I get that you substitute f(n) in the third line... but I have no idea what the fourth and fifth lines are about! Please help me? I need to understand this by tomorrow :(
 

Answers and Replies

  • #2
217
0


Homework Statement


I am trying to prove towers of hanoi. Now I am on the induction part and there is a part I don't get. I have the whole thing, but i don't understand a couple lines.


Homework Equations





The Attempt at a Solution



WTS: f(n+1) = 2n+1 - 1
By the Induction Hypothesis, f(n) = 2n-1.

Earlier, we showed f(n) = f(n-1) + 1 + f(n-1).

By the recursive definition,
f(n+1) = f(n) + 1 + f(n).
f(n+1) = 2f(n) + 1
f(n+1) = 2(2n-1) + 1
f(n+1) = 2(2n - 2) + 1
f(n+1) = 2n+1 - 1.
QED.

Ok I get the first line...get the second line...I get that you substitute f(n) in the third line... but I have no idea what the fourth and fifth lines are about! Please help me? I need to understand this by tomorrow :(


I believe that the induction hypothesis should be (2^n) - 1, it should be clear after fixing that up
 
  • #3
39
0


Oh okay, i missed that, thanks. I'm still confused though...so the third line would be

f(n+1) = 2(2n - 1) + 1, right? why is the next line 2(2n - 2) + 1?
 
  • #4
217
0


after 2(2^n - 1) , you should get (2^n+1 - 2) + 1 --> 2^n+1 - 1 and it is proven.

you have some more typo errors, that line should be 2(2^n - 1) + 1, since you had above that 2f(n) + 1 - which now after clearing up, is definitely 2(2^n - 1) + 1
 
  • #5
39
0


OHHH sorry that took me awhile! Thank you so much lol xD

I have another question on a diff topic? I feel really stupid for asking but I'm not sure what to do.

for proving this carefully:

|x-3| = 8

I know you have to split it into two cases, x-3> 0. x-3 < 0.

For x-3>0,
x-3 = 8
x= 11.

For x-3<0, what do I do? I know it equals -5, but i don't know how to prove it?
 
  • #6
217
0


OHHH sorry that took me awhile! Thank you so much lol xD

I have another question on a diff topic? I feel really stupid for asking but I'm not sure what to do.

for proving this carefully:

|x-3| = 8

I know you have to split it into two cases, x-3> 0. x-3 < 0.

For x-3>0,
x-3 = 8
x= 11.

For x-3<0, what do I do? I know it equals -5, but i don't know how to prove it?

Hi, the absolute function is explicitly defined, so just distinguish the cases where f(x) = x when x > 0 and -x when x < 0; when x> 3 x-3 , when x < 3 -(x-3) or 3-x
 
  • #7
HallsofIvy
Science Advisor
Homework Helper
41,847
966


|x| is equal to x if [itex]x\ge 0[/itex], -x if x< 0.

So |x-3| is equal to x-3 if [itex]x\ge 3[/itex], -(x-3)= -x+ 3 if x< 3.

If [itex]x\ge 3[/itex] then |x- 3| becomes x- 3= 8 or x= 8+ 3= 11, which is, in fact, greater than 3. If x< 3 then |x- 3|= -(x-3)= -x+ 3= 8 so -x= 8- 3= 5 and x= -5, which is, in fact, less than 3. (You should always check to see if the result is in the correct range.)

x= 11 and x= -5 satisfy this equation. If x= 11, then x- 3= 11-3= 8 so |x- 3|= 8. If x= -5, x- 3= -5- 3= -8 so |-8|= 8.
 

Related Threads on Towers of hanoi induction- slight bit i don't understand

  • Last Post
Replies
1
Views
2K
Replies
29
Views
2K
Replies
6
Views
2K
Replies
11
Views
819
Replies
8
Views
2K
Replies
7
Views
2K
Replies
14
Views
2K
Replies
2
Views
1K
Replies
6
Views
1K
Replies
1
Views
1K
Top