# Solving Recurrence $T_n = T_{n-1}*T_{n-2} + T_{n-3}$

I have a series of numbers called the Foo numbers, where $F_0 = 1, F_1=1, F_2 = 1$ then the general equation looks like the following: $$F_n = F_{n-1}(F_{n-2}) + F_{n-3}$$

So far I have got the equation to look like this: $$T_n = T_{n-1}*T_{n-2} + T_{n-3}$$

I just don't know how to solve the recurrence. I tried unfolding but I don't know if i got the right answer: $$T_n = T_{n-i}*T_{n-(i+1)} + T_{n-(i+2)}$$

Please help, I need to describe the algorithm which I have done but the analysing of the running time is frustrating me.

-
Most non-linear recurrences do not have closed-form solutions. Perhaps just an estimate of the size will do? – GEdgar Jul 16 '12 at 17:46
– draks ... Jul 16 '12 at 17:46
@draks Similar, but not quite. – Pedro Tamaroff Jul 16 '12 at 17:48
@draks: I found a solution for the related recursion; perhaps someone can generalize it to this one? – mjqxxxx Jul 16 '12 at 22:27

Numerical data looks very good for $$F_n \approx e^{\alpha \tau^n}$$ where $\tau = (1+\sqrt{5})/2 \approx 1.618$ and $\alpha \approx 0.175$. Notice that this makes sense: When $n$ is large, the $F_{n-1} F_{n-2}$ term is much larger than $F_{n-3}$, so $$\log F_n \approx \log F_{n-1} + \log F_{n-2}.$$ Recursions of the form $a_n = a_{n-1} + a_{n-2}$ always have closed forms $\alpha \tau^n + \beta \tau^{-n}$.
Here's a plot of $\log \log F_n$ against $n$, note that it looks very linear. A best fit line (deleting the first five values to clean up end effects) gives that the slope of this line is $0.481267$; the value of $\log \tau$ is $0.481212$.