Towers of Hanoi

**Sampras** · June 2nd 2009, 03:36 PM

We know that the recurrence relation for the Towers of Hanoi problem is: $\begin{cases} t_0 = 0; \\ T_n = 2T_{n-1}+1, \ \ \text{for} \ n >0 \end{cases}$ . Also we know that $T_n = 2^n-1$ .

But is finding the generating function $A(x)$ significant at all? E.g. $A(x) = \sum_{n \geq 0} a_nx^n$ where the $a_n$ 's are the $n$ th terms of $T_n$ ? Here $A(x) = \frac{x}{(1-x)(1-2x)}$ .

**Plato** · June 2nd 2009, 03:49 PM

Does thjs help?

**Sampras** · June 2nd 2009, 03:54 PM

Originally Posted by Plato

Does thjs help?

Well this derives the explicit formula for $T_n$ . However, is there any special significance of using generating functions to look at the Towers of Hanoi problem?

Thread: Towers of Hanoi

LinkBack

Thread Tools

Display

Towers of Hanoi

Similar Math Help Forum Discussions

Towers of Hanoi Problem2

Towers of Hanoi Problem

hanoi towers,induction

Reve's Puzzle (Hanoi Problem with 4 towers)

Towers of Hanoi Adjacent

Search Tags