Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
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
    
1  
@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

1 Answer 1

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.

share|improve this answer
    
That seems like a little pasted what i need to do. I know i should be doing guess and check to solve it. –  Alex Jul 16 '12 at 18:34

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.