# Hanoi towers recursive expression for EVERY algorithm

What the recursive algorithm for moving $$n$$ disks says, is:

1. If $$n > 1$$, move $$n-1$$ discs from A to B.
2. Move the $$n$$th disk from A to C.
3. If $$n > 1$$, move $$n-1$$ discs from B to C.

Let $$T_n$$ be the number of moves for moving n disks.

We have $$T_n=2T_{n-1}+1 , T_1=1$$, so $$T_n=2^n-1, n \geq 1$$

Is it correct to say that for every algorithm solving the Hanoi Towers problem, it is true that $$T_n=2T_{n-1}+c$$ So we would need to know $$c$$ (number of moves for moving the last disk from A to C) and some other $$T_i$$, in order to calculate $$T_ n$$ for every $$n$$.

• It's hard to make a statement about every algorithm for a problem: what about the algorithm that acts exactly like yours, except that if $n=69105$, it first moves a single disk back and forth seventy thousand times? Now $T_{69105}$ isn't perfectly predictable from $T_{69104}$. – Draconis Dec 5 '19 at 16:46