Quadratic Recurrence : $f(n) = f(n-1) + f(n-2) + f(n-1) f(n-2)$ Solution? How?

Question

I have encountered this question in a coding competition and want the formula for $f(n)$. Is there any way to do this?

Answer 1

Supposing the first two terms are $0$ and $1$ (or $1$ and $1$) this would be OEIS entry A063896:

$f(n) = 2^{F(n)} - 1$ where $F(n)$ is the $n$th Fibonacci Number.

To prove that this relation continues to hold, you may wish to try mathematical induction.

Answer 2

We have from @Daniel's comment,

$$\ln (1+f(n))=\ln((1+f(n-1))(1+f(n-2))$$

$$\ln (1+f(n))=\ln (1+f(n-1))+\ln (1+f(n-2))$$

Let $A(n)=\ln (1+f(n))$ then we have,

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

This has characteristic equation,

$$r^2-r-1=0$$

Whose solution is the golden ratio $\phi$ and $1-\phi$.

Hence,

$$A(n)=c_1(\phi)^n+c_2(1-\phi)^n$$

$$1+f(n)=\exp (c_1(\phi)^n+c_2(1-\phi)^n)$$

$$f(n)=\exp (c_1(\phi)^n+c_2(1-\phi)^n)-1$$