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.
How to solve F(n)+1 = (F(n-1)+1)*(F(n-2)+1) this recurrence relation?
recurrence relation;mathematical programming
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$$