2
$\begingroup$

What's the (asymptotic) solution of the following recurrence? $$ T(n) = \frac{T(n-1) + T(n-3)} {T(n-2)}. $$ I tried to solve this with generating functions to find an accurate bound.

$\endgroup$
1
  • $\begingroup$ What are the initial values? $\endgroup$ – Yuval Filmus Nov 1 '20 at 11:22
2
$\begingroup$

The solution depends on the initial conditions. For example, if $T(0) = T(1) = T(2) = 2$ then $T(n) = 2$ for all $n$, but in general the recurrence converges to a pattern of length $4$. The limiting patterns are of the form $$ a, \frac{ab\pm\sqrt{(ab)^2-4(a+b)}}{2}, b, \frac{ab\mp\sqrt{(ab)^2-4(a+b)}}{2} $$ For example, if $T(0)=T(1)=T(2)=1$ then $a ≈ 3.13200592382654$ and $b ≈ 1.35282312408545$. For large $n$, the values $T(4n),T(4n+1),T(4n+2),T(4n+3)$ are close to $$ 3.13200592382654, 2.06091243965066, 1.35282312408545, 2.17613759887451. $$ (So we choose $-$ in the $\pm$.)

The above was determined empirically. It would be nice to come up with a proof.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy