3
$\begingroup$

How can I solve this? I saw Solving the recurrence $T(n)=T(n-1)*T(n-2)$ but I don't know how I can apply it to $T(n)=T(n-1)/T(n-2)$?

$\endgroup$
5
$\begingroup$

Then assume $T(0) = a, T(1)=b$ such as $a \neq 0$ and $b \neq 0$. You could write down first few terms and deduce the pattern $$T(0)= a$$ $$T(1)= b$$ $$T(2)= \frac{T(1)}{T(0)} = \frac{b}{a}$$ $$T(3)= \frac{T(2)}{T(1)} = \frac{b/a}{b} = \frac{1}{a}$$ $$T(4)= \frac{T(3)}{T(2)} = \frac{1/a}{b/a} = \frac{1}{b}$$ $$T(5)= \frac{T(4)}{T(3)} = \frac{1/b}{1/a} = \frac{a}{b}$$ $$T(6)= \frac{T(5)}{T(4)} = \frac{a/b}{1/b} = a = T(0)$$ $$T(7)= \frac{T(6)}{T(5)} = \frac{a}{a/b} = b = T(1)$$ $$...$$ Thus the values of $T(n)$ repeat with period of $6$.

$\endgroup$
2
$\begingroup$

If you are dealing with a recurrence for which you have no idea how to attempt the solution, it is always a good idea to try working out the first few terms by hand (or using software such as Excel). If you try this, the solution for this recurrence will probably be quite obvious...

$\endgroup$
  • 1
    $\begingroup$ I tried this. Took me exactly 12 seconds to set up a spreadsheet that made the solution shown by fade2black absolutely obvious. $\endgroup$ – gnasher729 Nov 4 '17 at 15:01

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.