How to solve $f(n) = f(n-1) + f(n-1) f(n-2)$?

Question

Consider the following recurrence:

$$f(0) = f(1) = 2$$ $$f(n) = f(n-1) + f(n-1) f(n-2)$$

It is clear the function grows very quickly but how can it be solved exactly? If this is difficult, I would be happy with an asymptotic or $\Theta()$ answer.

Answer 1

The $f(n-1)$ term is fairly insignificant compared to the $f(n-1)f(n-2)$ term. That is, consider the following:

$$g(n)=g(n-1)g(n-2)$$

Letting $g=2^h$ we get

$$h(n)=h(n-1)+h(n-2)$$

and hence $h(n)=F_{n+1}$, where $F_n$ is the nth Fibonacci number. Hence we get the asymptotic:

$$f(n)\simeq2^{F_{n+1}}\simeq2^{\phi^{n+1}/\sqrt5}$$

where $\phi$ is the golden ratio.

We can more accurately see how the provided sequences compares to something like $2^{\phi^{n+C}}$ by extracting $C$ from

$$C=\lim_{n\to\infty}\log_\phi(\log_2(f(n)))-n$$

This converges very quickly to $C\simeq-0.9705900452306$.

$$f(n)\simeq2^{\phi^{n-0.9705900452306}}$$

Try it online!

The values quickly grow too large for floats. It may be better take a look at the logarithm of the terms:

\begin{align}\log_2(f(n))&=\log_2(f(n-1))+\log_2(f(n-2)+1)\\&=\log_2(f(n-1))+\log_2(f(n-2))+\log_2\left(1+\frac1{f(n-2)}\right)\\&\simeq\log_2(f(n-1))+\log_2(f(n-2))+\frac1{\ln(2)f(n-2)}\end{align}

Try it online!