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

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