<s>[INST] how to solve the following recurrence? $t(n)=[4-t(n-1)]^{-1}$ I am trying to solve the following recurrence :
$T_n=\frac{1}{4-T_{n-1}}$
I tried various methods using range transformation but still can't figure it out.
 [/INST] If it has a limit $L$,
$T_n=\frac{1}{4-T_{n-1}}
$
becomes
$L=\frac{1}{4-L}
$
or
$L^2-4L+1 = 0$
so that
$L
=\dfrac{4\pm\sqrt{16-4}}{2}
=2\pm\sqrt{3}
$.
Let
$L_1
=2+\sqrt{3}
$
and
$L_2
=2-\sqrt{3}
$.
If
$0 < T_{n-1} < 1$,
then
$\frac14 < T_n
< \frac13
$.
After this,
$\frac1{4-1/3}
< T_{n+1}
< \frac1{4-1/4}
$
or
$\frac{3}{13}
< T_{n+1}
< \frac{4}{15}
$.
If $0 < x < \frac14$,
then
$1+x
<\frac1{1-x}
< 1+2x
$,
so that,
if $0 < T_{n-1}
< 1$,
then
$T_n
=\frac{1}{4-T_{n-1}}
=\frac14\frac{1}{1-T_{n-1}/4}
\gt\frac14(1+T_{n-1}/4)
$
and
$T_n
=\frac14\frac{1}{1-T_{n-1}/4}
\lt\frac14(1+2T_{n-1}/4)
=\frac14+\frac{T_{n-1}}{8}
\lt \frac38
$.
Let
$u_n
= T_n-L_2
$.
Then
$u_n+L_2
=\dfrac1{4-(u_{n-1}+L_2)}
$
or
$\begin{array}\\
1
&=(u_n+L_2)(4-L_2-u_{n-1})\\
&=u_n(4-L_2)-L_2u_{n-1}+L_2(4-L_2)\\
&=u_n(4-L_2)-L_2u_{n-1}+1
\qquad\text{since } L_2(4-L_2) = 1\\
\text{so}\\
u_n(4-L_2)
&=L_2u_{n-1}\\
\text{or}\\
u_n
&=\frac{L_2}{4-L_2}u_{n-1}\\
&=L_2^2u_{n-1}\\
\end{array}
$
Therefore,
if
$0 < u_n < 1$,
$u_{n+k}
=L_2^{2k}u_n
$.
Since
$L_2^2
=\frac{7-4\sqrt{3}}{4}
\approx 0.07179676972449
$,
this converges
quickly.
We then have
$T_{n+k}-L_2
=L_2^{2k}(T_n-L_2)
$
or
$T_{n+k}
=L_2^{2k}(T_n-L_2)+L_2
$.
Therefore,
if $0 \le T_0 < 1$,
$T_{k}
=L_2^{2k}(T_0-L_2)+L_2
$.
In particular,
if $T_0 = 0$,
$T_{k}
=L_2-L_2^{2k+1}
$.
</s>