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.