Transform a recurrence with fraction into a linear recurrence

Question

How can you transform this recursive formluar into a linear recurrence (in order to get a closed formular and calculate a (closed) function)?

$t(n) = 2 * \frac{(t(n-1))^3}{(t(n-2))^2}$

and $t(0) = t(1) = 2$

I would know how to countine if I had a linear recursive formular, but unfortunately the fraction makes things quite a bit tricky.

Answer 1

Hint: Use logarithms to transform the relation into an additive one.

Indeed, let $u(n)=\log t(n)$. Then $$ u(n)= \log 2 + 3 u(n-1) - 2 u(n-2), \qquad u(0)=u(1)= \log 2 $$ This is a linear recurrence that can be solved using standard techniques.

Answer 2

Alternative hint:  let $\,a_n=t_n / t_{n-1}\,$, then the recurrence can be written as:

$$a_n = 2 \cdot a_{n-1}^2 = 2 \cdot 2^2 \cdot a_{n-2}^{4}=2 \cdot 2^2 \cdot 2^4 \cdot a_{n-3}^{8} = \cdots = 2^{2^{n-1}-1} \cdot a_1^{2^{n-1}}$$

Then $t_n = a_n \cdot a_{n-1} \cdot \,\cdots\, \cdot a_1 \cdot t_0\,$.

Answer 3

The key idea is that all the numbers are integer powers of two. So let $t(n)=2^{a(n)}$ and rewrite the recurrence for $t(n)$ as a linear recurrence for $a(n)$.