# Thread: Is this wrong?

1. ## 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.

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

3. 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?

4. 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

5. 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?

6. 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