5
$\begingroup$

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.

  • 0
    @draks: I found a solution for the related recursion; perhaps someone can generalize it to this one?2012-07-16

1 Answers 1

7

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

enter image description here

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

Your sequence is in Sloane but it doesn't say much of interest; if you have anything to say, you should add it to Sloane.

  • 0
    That seems like a little pasted what i need to do. I know i should be doing guess and check to solve it.2012-07-16