Find general term of recursive sequences $ x_{n+1}=\frac{1}{2-x_n}, x_1=1/2,$ Please help to solve:


*

*$ x_{n+1}=\frac{1}{2-x_n}, x_1=1/2,$ 

*$x_{n+1}= \frac{2}{3-x_n}, x_1=1/2$
I know answers, but can't figure out the solution.
The first one is obvious if you calculate first 3-5 terms by hand. But how can I get the result not by guessing, but mathematically?
Answers are:


*

*$x_n = \frac{n}{n+1}$

*$x_n = \frac{3\cdot2^{n-1}-2}{3\cdot2^{n-1}-1}$

A recurrence of the form:
$\begin{equation*}
  w_{n + 1}
    = \dfrac{a w_n + b}{c w_n + d}
\end{equation*}$
with $a d \ne b c$ and $c \ne 0$ is called a Ricatti recurrence. One way to solve them is to recognize the right hand side is a Möbius transform, and those can be composed like matrix products:
$\begin{align*}
  A(z)
    &= \frac{a_{1 1} z + a_{1 2}}{a_{2 1} z + a_{2 2}} \\
  B(z)
    &= \frac{b_{1 1} z + b_{1 2}}{b_{2 1} z + b_{2 2}} \\
  C(z)
    &= A(B(z)) \\
    &= \frac{c_{1 1} z + c_{1 2}}{c_{2 1} z + c_{2 2}}
\end{align*}$
where the matrix of coefficients in $C$ is $B \cdot A$. Thus the solution (as a matrix) is given by $w_n = A^n(w_0)$.
Another way is due to Mitchell. Define a new variable $x_n = (1 + \eta w_n)^{-1}$, write the recurrence in terms of $x_n$:
$\begin{equation*}
x_{n + 1}
      = \dfrac{(d \eta - c) x_n + c}
             {(b \eta^2 - (a - d) \eta - c) x_n + a \eta + c}
\end{equation*}$
Selecting $\eta$ such that $b \eta^2 - (a - d) \eta - c = 0$ (both roots work fine) reduces the recurrence to linear of the first order.
