# 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. –  Hobbie 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

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. –  Hobbie Mar 4 '11 at 21:55
I think you also need $h_0$.
$$g(x) = \sum_{n \geq 0} h_n x^n = h_0 x_0 + \sum_{n \geq 1} (2 h_{n-1} + 1)x^n$$
If you write $\sum_{n \geq 0} 2 h_{n-1} x^n$, this is not defined because you don't know $h_{-1}$. Or is it given in the problem?
Start the sum of g from $n=1$ –  Fabian Mar 4 '11 at 10:05
@Fabian: I'm not sure I understand. I think an ordinary generating function is a formal power series starting at $0$. Can you clarify what you mean? –  Matt N. Mar 4 '11 at 10:14