3
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
3
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.