Resolución de repetición $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

Question

Tengo una serie de números de llamada a los Foo números, donde $F_0 = 1, F_1=1, F_2 = 1 $ entonces la ecuación general se parece a la siguiente: $$ F_n = F_{n-1}(F_{n-2}) + F_{n-3} $$

Hasta ahora tengo la ecuación para este aspecto: $$T_n = T_{n-1}*T_{n-2} + T_{n-3}$$

Sólo que no sé cómo resolver la recurrencia. Traté de despliegue, pero no sé si tengo la respuesta correcta: $$ T_n = T_{n-i}*T_{n-(i+1)} + T_{n-(i+2)} $$

Por favor ayuda, necesito a describir el algoritmo que he hecho, pero el análisis del tiempo de ejecución es frustrante para mí.

Answer 1

Los datos numéricos se ve muy bien para $$F_n \approx e^{\alpha \tau^n}$$ donde$\tau = (1+\sqrt{5})/2 \approx 1.618$$\alpha \approx 0.175$. Aviso que esto tiene sentido: Al $n$ es grande, el $F_{n-1} F_{n-2}$ plazo es mucho más grande de lo $F_{n-3}$, por lo que $$\log F_n \approx \log F_{n-1} + \log F_{n-2}.$$ Recursiones de la forma $a_n = a_{n-1} + a_{n-2}$ siempre tienen formas cerradas $\alpha \tau^n + \beta \tau^{-n}$.

Aquí está una parcela de $\log \log F_n$ contra $n$, ten en cuenta de que es muy lineal. Un mejor ajuste de la línea (la eliminación de los primeros cinco valores para limpiar los efectos finales) que da la pendiente de esta línea es $0.481267$; el valor de $\log \tau$$0.481212$.

Su secuencia es en Sloane , pero no dice mucho de intereses; si tiene algo que decir, debe agregarlo a Sloane.