Recuento de los árboles de extensión en un grafo de rueda

Question

Quiero encontrar una fórmula explícita para el número de árboles que se extienden en el gráfico de la rueda. La respuesta, es

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

Mi enfoque es encontrar un conjunto de relaciones de recurrencia y luego resolverlas para encontrar la fórmula explícita. Un conjunto de relaciones de recurrencia para este problema, es

$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}$

Mirando este , puedo ver que una solución para estas relaciones de recurrencia es

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

y cuando tengo esta relación de recurrencia, puedo resolverla para obtener la fórmula indicada anteriormente. Mi problema es, resolver las 5 relaciones de recurrencia acopladas para obtener

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

He intentado aislar y sustituir simplemente las ecuaciones muchas veces, y he intentado trabajar con funciones generadoras, pero ninguna de ellas me da la respuesta.

Answer 1

En la página a la que enlazas, hay precisamente una derivación de este tipo, por eta oin shrdlu . Citando:

Sus dos últimas recurrencias dan $$(d_n−d_{n−1})−(d_{n−1}−d_{n−2})=e_{n−1}−e_{n−2}=d_{n−1}$$ y así $$0=d_n−3d_{n−1}+d_{n−2}.$$ Ahora $a_n=d_{n−1}+w_{n−1}=a_{n−1}+2d_{n−1}$ y así $$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}).$$ Así que ambos $a_n$ y $d_n$ satisfacen la recursión $0=x_n−4x_{n−1}+4x_{n−2}−x_{n−3}$ y, por tanto, también su suma $a_n+d_n=w_n$ .