How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation?

I am trying to solve this recurrence relation for a while but not getting anywhere. Actually, the sequence is given as,


F(n) = F(n-1) + F(n-2) + F(n-1)*F(n-2)

where, F(0) and F(1) will be given. I added 1 on both sides to factorize it. I tried to solve it by taking log on both sides but unable to come to a conclusion.

P.S. I can't use simple for loop as n can go upto 10^9 so it'll result into a timeout.

It can be computed in a completely analytical way. Take:

$$
F_n = F_{n-1} + F_{n-2} + F_{n-1}F_{n-2}
$$

Adding $1$ to both sides and factorizing we obtain:

$$
F_n + 1 = (F_{n-1} +1)(F_{n-2}+1)
$$

Now let $G_n = F_n + 1$ :

$$
G_n = G_{n-1} G_{n-2}$$

Taking the logarithm in some base $b$ :

$$
\log_b{G_n} = \log_b G_{n-1} + \log_b G_{n-2}$$

Which we rewrite, letting $H_n = \log_b{G_n}$ , as:

$$
H_n = H_{n-1} + H_{n-2}
$$

This suggests an effective way to compute $F_n$ . First of all we compute $H_0 = \log_b(1 + F_0)$ and similarly $H_1$. Then we determine $H_n$ in closed form. Since $H$ is a second-order recurrence with constant coefficients, $H_n$ is in the form:

$$
H_n = A\phi^n + B\psi^n
$$

where $\phi, \psi$ are the solutions to the associated polynomial equation $h^2 = h +1$, namely $\frac{1 \pm \sqrt{5}}{2}$. Knowing $H_0$, $H_1$, we can determine $A, B$ as the solutions to the following system:

$$
\left \{
\begin{array}{r c l}
H_1 & = & A\left( \frac{1 - \sqrt{5}}{2} \right) + B\left( \frac{1 - \sqrt{5}}{2} \right) \\
H_0 & = & A + B
\end{array}
\right .
$$

Now, remembering that $H_n = \log_b{G_n}$ and $G_n = F_n + 1$, we can finally compute:

$$
F_n = b^{H_n} -1
$$

StackExchange Computer Science Q#69031, answer score: 3