Results 1 to 6 of 6

Math Help - Is this wrong?

  1. #1
    Member
    Joined
    May 2009
    Posts
    107

    Is this wrong?

    <br />
T(n) = T(n-1) + c + T(n - 1) = 2T(n - 1) + C = 2(2(T(n - 2) + c) + c)<br />


    It's the towers of hanoi algorithm in case that helps.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,553
    Thanks
    542
    Hello, alyosha2!

    T(n) \:= \:T(n-1) + c + T(n - 1) \;=\; 2T(n - 1) + c \;=\; 2\bigg[2(T(n - 2) + c\bigg] + c

    It's the "Towers of Hanoi" algorithm in case that helps.
    Not sure what the question is . . .

    Consider the first few values of the sequence.
    . . n = number of disks, T(n) = number of moves.

    . . \begin{array}{|c|c|}<br />
n & T(n) \\ \hline<br />
1 & 1 \\<br />
2 & 3 \\<br />
3 & 7 \\<br />
4 & 15 \\<br />
5 & 31 \\<br />
\vdots & \vdots \end{array}


    The recursive form is: . T(n) \;=\;2\!\cdot\!T(n-1) + 1

    . . The closed form is: . T(n) \;=\;2^n - 1

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    May 2009
    Posts
    107
    Quote Originally Posted by Soroban View Post
    Hello, alyosha2!

    Not sure what the question is . . .

    Consider the first few values of the sequence.
    . . n = number of disks, T(n) = number of moves.

    . . \begin{array}{|c|c|} n & T(n) \\ \hline
    1 & 1 \\
    2 & 3 \\
    3 & 7 \\
    4 & 15 \\
    5 & 31 \\
    \vdots & \vdots \end{array}" alt="
    n & T(n) \\ \hline
    1 & 1 \\
    2 & 3 \\
    3 & 7 \\
    4 & 15 \\
    5 & 31 \\
    \vdots & \vdots \end{array}" />


    The recursive form is: . T(n) \;=\;2\!\cdot\!T(n-1) + 1

    . . The closed form is: . T(n) \;=\;2^n - 1
    I was meaning more about the parentheses. Shouldn't it be

     <br />
2(2T(n-2) + c) + c<br />

    in the third part?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by alyosha2 View Post
    I was meaning more about the parentheses. Shouldn't it be

     <br />
2(2T(n-2) + c) + c<br />

    in the third part?
    That is what you get by applying the itteration once more yes (note it simplifies down to:

    T_n=4T_{n-1}+3c

    CB
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    May 2009
    Posts
    107
    Quote Originally Posted by CaptainBlack View Post
    That is what you get by applying the itteration once more yes (note it simplifies down to:

    T_n=4T_{n-1}+3c

    CB
    so in the original post it is wrong then (it's from a text book and i couldn't make sense of it)

    i have a follow up question about the next part, should i post that in a new thread?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by alyosha2 View Post
    so in the original post it is wrong then (it's from a text book and i couldn't make sense of it)

    i have a follow up question about the next part, should i post that in a new thread?
    Yes the original is wrong.

    If the follow up is more or less directly related to or depends on this, post it here. If it stands up on its own, post it in a new thread. You will get a reply faster that way.

    CB
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] am I wrong here or is my textbook wrong??
    Posted in the Algebra Forum
    Replies: 5
    Last Post: September 25th 2011, 05:13 PM
  2. IVP, what am I doing wrong?
    Posted in the Differential Equations Forum
    Replies: 4
    Last Post: February 9th 2010, 11:17 PM
  3. Replies: 6
    Last Post: August 12th 2009, 02:15 AM
  4. Why am I wrong?!
    Posted in the Calculus Forum
    Replies: 1
    Last Post: April 18th 2009, 07:34 PM
  5. Wrong answer key or wrong me ?
    Posted in the Algebra Forum
    Replies: 2
    Last Post: July 2nd 2008, 04:42 AM

Search Tags


/mathhelpforum @mathhelpforum