# Using generating functions to find a formula for the Tower of Hanoi numbers

So the Tower of Hanoi numbers are given by the recurrence $h_n=2h_{n-1}+1$ and $h_1=1$. I let my generating function be $$g(x)=\sum h_nx^n$$ Then $$g(x)=\sum h_n x^n=\sum (2h_{n-1}+1)x^n=\sum 2h_{n-1}x^n+\sum x^n=2xg(x)+\frac{1}{1-x}.$$ Solving for $g(x)$ I find $$g(x)=\frac{1}{(1-2x)(1-x)}=\frac{2}{1-2x}-\frac{1}{1-x}=2\sum (2x)^n-\sum x^n.$$ It seems then that the coefficient $h_n$ of $x^n$ is $2^{n+1}-1$, but wolfram mathworld says it should be $h_n=2^n-1$. What did I do wrong here? Thanks.

-
What is the initial condition on the recurrence relation? –  Fabian Mar 4 '11 at 9:41
@Fabian, just added it. –  Dani Hobbes Mar 4 '11 at 9:42
It looks like wolfram's result has the right initial conditions and your result does not... –  Fabian Mar 4 '11 at 10:04

## 1 Answer

Setting $$g(x) = \sum_{n=0}^{\infty} h_{n+1} x^n,$$ we obtain using $h_n = 2 h_{n-1} +1$ and $h_1 =1$ $$g(x) = \sum_{n=0}^{\infty} h_{n+1} x^n = h_1 + \sum_{n=1}^{\infty} (2 h_{n} +1) x^n = 1 + \sum_{n=0}^{\infty} (2 h_{n+1} +1) x^{n+1} =1 +2 x g(x) + \frac{x}{1-x}.$$ Solving for $g(x)$, we obtain $$g(x) = \frac{1}{(1-x) (1-2x)} = \frac{2}{1-2x} - \frac{1}{1-x} = \sum_{n=0}^{\infty} (2^{n+1} -1) x^n$$ such that $h_n = 2^n -1$.

-
Thanks Fabian, I should have been more careful with my indexing. –  Dani Hobbes Mar 4 '11 at 21:55