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