Solve recurrence relation

Question

Solve the following recurrence. First transform it to a simpler recurrence and then solve the new recurrence using generating functions or a characteristic polynomial: $f_n = f_{n−1} · f_{n−2}$ for $n \ge 2, f_0 = 2, f_1 = 4$.

Answer 1

Hint: Define $g_n = \log_2 f_n$.

---

Adding details: The substitution above gives the linear homogeneous recurrence relation $$g_0 = 1,\; g_1 = 2,\; n \ge 1 \implies g_n = g_{n-1}+g_{n-2}$$

This should remind you of the Fibonacci recurrence. As you have noted, the characteristic equation and roots are: $$\lambda^2-\lambda-1 = 0, \quad \lambda_{1,2} = \frac{1\pm \sqrt5}2,$$ so the solution must be of form $g_n = c_1 \lambda_1^n+c_2\lambda_2^n$. Using the initial conditions, we need $$g_0 = 1 = c_1+c_2, \; g_1 =2 = \frac12 (1+\sqrt5 ) c_1+\frac12 (1-\sqrt5) c_2$$

Solving that gives you for the coefficients $$c_{1,2} = \frac{5\pm3\sqrt5}{10}$$ So we have in general $$g_n = \frac{\left(5-3 \sqrt{5}\right) \left(1-\sqrt{5}\right)^n+\left(5+3 \sqrt{5}\right) \left(1+\sqrt{5}\right)^n}{5\cdot 2^{n+1}}$$

and $f_n = 2^{g_n}$.