Solving the recursion $T(n) = T(n-1)\cdot T(n-2)$

Question

Given $T(1) = a$ and $T(2) = b$, solve for $T(n)= T(n-1)\cdot T(n-2)$

[For the sake of clarity,that is $T(n-1)$ multiplied by $T(n-2)$ ]

It was asked in one of the entrance tests for a PHD program. I have seen some websites in which they state this type of problem to be Non-Linear Recurrence,but they do not state how to solve such problem.

Answer 1

You can show that $T(n)=a^{F_{n-2}}b^{F_{n-1}}$ by induction where $F_n$ is the $n$th Fibonacci number defined by $F_{-1}=1,F_0=0,F_{n+1}=F_{n}+F_{n-1}\ (n\ge 0)$. The Fibonacci numbers have a closed-form solution.

Answer 2

Here is how you advance. Take the logarithm to both sides of the equation as

$$ \ln( T( n) ) = \ln(T(n-1))+\ln( T(n-2) ),$$

then let $Y(n) = \ln(T(n))$ which transforms the recurrence to

$$ Y(n) = Y(n-1)+Y(n-2) $$

which is a recurrence relation with constant coefficients.