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
    Most non-linear recurrences do not have closed-form solutions. Perhaps just an estimate of the size will do?2012-07-16
  • 0
    possible dupe: [Solving a Nonlinear Recursion $a_{n+3} = a_{n+2}a_{n+1} - a_n$](http://math.stackexchange.com/q/170159/19341)?2012-07-16
  • 1
    @draks Similar, but not quite.2012-07-16
  • 0
    @draks: I found a solution for the related recursion; perhaps someone can generalize it to this one?2012-07-16

1 Answers 1