1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

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

  1. Oct 1, 2009 #1
    Towers of hanoi induction-- slight bit i don't understand

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


    2. Relevant equations



    3. 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 :(
     
  2. jcsd
  3. Oct 1, 2009 #2
    Re: Towers of hanoi induction-- slight bit i don't understand


    I believe that the induction hypothesis should be (2^n) - 1, it should be clear after fixing that up
     
  4. Oct 1, 2009 #3
    Re: Towers of hanoi induction-- slight bit i don't understand

    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?
     
  5. Oct 1, 2009 #4
    Re: Towers of hanoi induction-- slight bit i don't understand

    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
     
  6. Oct 1, 2009 #5
    Re: Towers of hanoi induction-- slight bit i don't understand

    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?
     
  7. Oct 1, 2009 #6
    Re: Towers of hanoi induction-- slight bit i don't understand

    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
     
  8. Oct 2, 2009 #7

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

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

    |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.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Towers of hanoi induction- slight bit i don't understand
Loading...