Find a closed form solution for the recurrence relation $a_n = a_{n-1} a_{n-2}$

Question

How do I find a closed form solution to

$$a_n = a_{n-1} a_{n-2}$$

Wolframalpha gives: $$a_n = e^{c_1 F_n + c_2 L_n} \text{ where $c_1$ and $c_2$ are arbitrary parameters}$$ $F_n$ are the Fibonnaci numbers and $L_n$ are the Lucas numbers.

I don't think generating functions are gonna get me anywhere right?

I also know for my given sequence that $a_0$ = 1, $a_1$ = 2. and that $a_n = 2^{F_n}$. Of course I could prove this by Induction, but I'd rather discover how to derive the general formula rather than just prove it's valid for my specific case.

Answer 1

Define the recurrence sequence $(a_{n})_{n\geqslant 1}$ as $a_{0}:=\alpha$ and $a_{1}:=\beta$ with $\alpha,\beta$ known constant and $a_{n}:=a_{n -1}a_{n -2}$. We can linearize this recurrence using the logarithm application $$a_{n}=a_{n-1}a_{n-2},$$ $$\underbrace{\log a_{n}}_{=x_{n}}=\log(a_{n-1}a_{n-2})=\underbrace{\log(a_{n-1})}_{=x_{n-1}}+\underbrace{\log(a_{n-2})}_{=x_{n-2}}$$ So, the original recurrence sequence is equivalent to the linear recurrence sequence $x_{n}=x_{n-1}+x_{n-2}$ through of the mapping $n\mapsto \log(n)$, adjusting the respective initial conditions and henceforth continue with the general method to solve linear recurrences and finally backward substitution.

Answer 2

Okay so suppose $a_0$ and $a_1$ are given. Then $a_2 = a_0 a_1$, $a_3 = a_0 a_1^2$, $a_4 = a_0^2 a_1^3$, $a_5 = a_0^3 a_1^5$, $a_6 = a_0^5 a_1^8$

So it seems like \begin{align}a_n = \begin{cases}{a_0^{F_{n-1}} a_1^{F_{n}}, \; \; n \geq 1 \\ a_0, \;\;\;\;\;\;\;\;\;\;n=1}\end{cases}\end{align}

This you could prove via Induction. Alternatively,

One can rewrite both $a_0$ and $a_1$ in terms of $e$ to get something similar to what wolframalpha gives. I'm assuming the relationship between Fibonacci numbers and Lucas numbers ties up the loose ends.

Defining $c_n = \log a_n$ as suggested by @AlexanderXander changes the recurrence to $c_n = c_{n-1} + c_{n-2}$ which has a closed for solution (Because it's the Fibonacci sequence upto initial conditions). Substituting For $a_n$ gives the desired result.