# Counting the spanning trees in a wheel graph

I want to find an explicit formula for the number of spanning trees in the wheel graph. The answer, is

$$\tau(W_n) = \left(\frac{3+\sqrt{5}}{2}\right)^n + \left(\frac{3-\sqrt{5}}{2}\right)^n - 2$$

My approach is to find a set of recurrence relations, and then solve these to find the explicit formula. A set of recurrence relations for this problem, is

$w_n = a_n+b_{n−1}$

$a_n = d_{n−1}+w_{n−1}$

$b_n = e_n+b_{n−1}$

$d_n = d_{n−1}+e_{n−1}$

$e_n = d_n+e_{n−1} =e_{n−1}+b_{n−1}$

By looking at this, I can see that a solution for these recurrence relations is

$$w_n−4w_{n−1}+4w_{n−2}−w_{n−3}=0$$

and when I have this recurrence relation, I can solve it to obtain the formula stated above. My problem is, to solve the 5 coupled recurrence relations to obtain

$$w_n−4w_{n−1}+4w_{n−2}−w_{n−3}=0$$

I have tried to simply isolate and substitute the equations many times, and I have tried working with generating functions, but none of those give me the answer.

-
The generating function approach works. The characteristic polynomial $x^3 - 4x^2 + 4x - 1$ has root $x = 1$ by inspection. Factoring it out gives $(x - 1)(x^2 - 3x + 1)$ and the roots of the latter are precisely the two quadratic irrationals which appear in the closed formula. The rest is computation. – Qiaochu Yuan May 29 '11 at 17:39
Yes, but the part I am interested in, is finding the recurrence relation to solve, not solving it. – utdiscant May 29 '11 at 18:34
Oh, I see. Write all of the equations in a form with $x_n$ on the LHS for one of the sequences $x$ and only terms involving $x_{n-1}$ for some sequences $x$ on the RHS, then write the whole thing as a matrix equation $v_n = A v_{n-1}$ where $A$ is a $5 \times 5$ matrix and $v$ is a vector of all of the sequences. Then find the characteristic polynomial of $A$. – Qiaochu Yuan May 29 '11 at 19:30

In the page you link to, there is just such a derivation, by eta oin shrdlu. Quoting:
Your last two recursions give $$(d_n−d_{n−1})−(d_{n−1}−d_{n−2})=e_{n−1}−e_{n−2}=d_{n−1}$$ and so $$0=d_n−3d_{n−1}+d_{n−2}.$$ Now $a_n=d_{n−1}+w_{n−1}=a_{n−1}+2d_{n−1}$ and so $$0=2(d_{n−1}−3d_{n−2}+d_{n−3})=(a_n−a_{n−1})−3(a_{n−1}−a_{n−2})+(a_{n−2}−a_{n−3}).$$ So both $a_n$ and $d_n$ satisfy the recursion $0=x_n−4x_{n−1}+4x_{n−2}−x_{n−3}$, and hence so does their sum $a_n+d_n=w_n$.
@utdiscant: Your last equation implies that $d_n = b_{n-1}$. Another possible pitfall is deriving $0 = d_n - 4d_{n-1} + 4d_{n-2} - d_{n-3}$ from $0 = d_n - 3d_{n-1} + d_{n-2}$: just subtract $0 = d_{n-1} - 3d_{n-2} + d_{n-3}$. – Yuval Filmus May 29 '11 at 21:06
Thanks, that cleared some of the puzzle for me, but I can't make sense of $a_n=d_{n-1}+w_{n-1} = a_{n-1}+2d_{n-1}$. – utdiscant May 29 '11 at 21:51
@utdiscant: Did you try $w_{n-1} = a_{n-1} + b_{n-2} = a_{n-1} + d_{n-1}$? – Yuval Filmus May 29 '11 at 23:52