2
$\begingroup$

I have been trying to solve the following recurrence:

$$T(n)=T(n-1)*T(n-2)$$ The initial conditions are $n \ge 2$ and $T(0) = 2$ and $T(1) = 4$.

I started by taking the $\log_{2}$ of both sides to get

$$\log(T(n)) = \log(T(n-1)) + \log(T(n-2))$$

which looks an awful lot like a Fibonacci recurrence.

So if I set $S(k) = \log(T(n))$, then I have a recurrence of the form $$S(k) = S(k-1) + S(k-2)$$ with $S(0) = 1$ and $S(1) = 2$.

I can solve this easily using a characteristic polynomial and get

$$S(k) = A*(0.5*(1+\sqrt{5}))^k + B*(0.5*(1-\sqrt{5}))^k$$ where $A$ and $B$ are constants. To get $A$ and $B$ I use the initial conditions for $S$, namely $S(0) = 1$ and $S(1) = 2$.

The problematic part is that I think to get $T(n)$ I just simply raise $2$ to the power of the entire bunch above to get

$$T(n) = 2^{n*A*0.5*(1+\sqrt{5})+n*B*0.5(1-\sqrt{5})}$$.

However, when I plug in some values for n to check I get some different integer values from the original recurrence.

Is my reasoning flawed somewhere in the process or am I just making an algebraic mistake somewhere?

Thanks!

$\endgroup$
  • 2
    $\begingroup$ Please use MathJax for typesetting equations. $\endgroup$ – Yuval Filmus Jan 24 '16 at 14:55
4
$\begingroup$

Your reasoning is perfect. To wit, here is what you get if you don't make any mistakes in your algebra. As you mention, $S(n)$ satisfies the Fibonacci recurrence, and furthermore $S(1) = 2 = F_3$, $S(0) = 1 = F_2$. We conclude that $S(n) = F_{n+2}$. Therefore $T(n) = 2^{F_{n+2}}$. The first few values are $$ 2, 4, 8, 32, 256, \ldots $$ To get a closed formula, note that $$ F_n = \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n. $$ Therefore $$ \begin{align*} S(n) &= \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^{n+2} - \frac{1}{\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^{n+2} \\ &= \frac{3+\sqrt{5}}{2\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n - \frac{3-\sqrt{5}}{2\sqrt{5}} \left(\frac{1-\sqrt{5}}{2}\right)^n \\ &= \frac{5+3\sqrt{5}}{10} \left(\frac{1+\sqrt{5}}{2}\right)^n + \frac{5-3\sqrt{5}}{10} \left(\frac{1-\sqrt{5}}{2}\right)^n, \end{align*} $$ using the fact that $(1\pm\sqrt{5})/2$ are roots of $x^2=x+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.