# 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.

You already solved a major part of the problem. Now just take logarithm of the both sides: $$\log(F(n)+1) = \log(F(n-1)+1) + \log(F(n-2)+1)$$ Then define $G(n) = \log(F(n)+1)$. Now you have a Fibonacci-like recursive relationship: $$G(n)=G(n-1)+G(n-2)$$ You might know that Fibonacci sequence has a closed form solution in terms of inital terms as follows: $$U_n=\frac{U_1-U_0\psi}{\sqrt{5}}\times \phi^n+ \frac{U_0\phi-U_1}{\sqrt{5}}\times \psi^n$$ where $\phi=\frac{1+\sqrt{5}}{2}$ and $\psi=\frac{1-\sqrt{5}}{2}$. Now just replace $U_n$ with $G(n)$, then you have the following: $$G(n)=\frac{G(1)-G(0)\psi}{\sqrt{5}}\phi^n+ \frac{G(0)\phi-G(1)}{\sqrt{5}}\psi^n$$ Now get back to the $F(n)$ by using $F(n)=e^{G(n)}-1$ which is: $$F(n)=e^{(\frac{\log(F(1)+1)-\log(F(0)+1)\psi}{\sqrt{5}}\phi^n+ \frac{\log(F(0)+1)\phi-\log(F(1)+1)}{\sqrt{5}}\psi^n)}-1$$

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$$