# Is this wrong?

• Aug 3rd 2009, 06:20 AM
alyosha2
Is this wrong?
$
T(n) = T(n-1) + c + T(n - 1) = 2T(n - 1) + C = 2(2(T(n - 2) + c) + c)
$

It's the towers of hanoi algorithm in case that helps.
• Aug 3rd 2009, 07:02 AM
Soroban
Hello, alyosha2!

Quote:

$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|}
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$

• Aug 4th 2009, 04:21 AM
alyosha2
Quote:

Originally Posted by Soroban
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

$
2(2T(n-2) + c) + c
$

in the third part?
• Aug 4th 2009, 04:49 AM
CaptainBlack
Quote:

Originally Posted by alyosha2
I was meaning more about the parentheses. Shouldn't it be

$
2(2T(n-2) + c) + c
$

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
• Aug 4th 2009, 04:58 AM
alyosha2
Quote:

Originally Posted by CaptainBlack
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?
• Aug 4th 2009, 05:47 AM
CaptainBlack
Quote:

Originally Posted by alyosha2
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