# Solving the recurrence $T(n) = \dfrac{T(n-1) + T(n-3)} {T(n-2)}$

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.

• What are the initial values? – Yuval Filmus Nov 1 '20 at 11:22

## 1 Answer

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.