how to solve the following recurrence? $t(n)=[4-t(n-1)]^{-1}$

Question

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.

Answer 1

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} $.

Answer 2

We have,

$$4T_n-T_{n-1}T_n=1$$

Let $\frac{f(n-1)}{f(n)}=T_{n}$. So that $T_{n-1}=\frac{f(n-2)}{f(n-1)}$.

This gives,

$$4\frac{f(n-1)}{f(n)}-\frac{f(n-2)}{f(n)}=1$$

$$4f(n-1)-f(n-2)-f(n)=0$$

$$f(n-2)-4(n-1)+f(n)=0$$

This has characteristic equation,

$$r^2-4r+1=0$$

Whose solutions are $r=2 \pm \sqrt{3}$. Hence,

$$f(n)=c_1(2+\sqrt{3})^n+c_2(2-\sqrt{3})^n$$

$$T_{n}=\frac{c_1(2+\sqrt{3})^{n-1}+c_2(2-\sqrt{3})^{n-1}}{c_1(2+\sqrt{3})^n+c_2(2-\sqrt{3})^n}$$

The constants $c_1,c_2$ can be deduced by the initial condition.