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.
Using generating functions to find a formula for the Tower of Hanoi numbers
4
$\begingroup$
combinatorics
generating-functions
-
0It looks like wolfram's result has the right initial conditions and your result does not... – 2011-03-04
1 Answers
6
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$.
-
0Thanks Fabian, I should have been more careful with my indexing. – 2011-03-04