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: If we recursively apply the recursive relation we get
$$x_{n+1} = \frac{1}{2-x_n} = \frac{2-x_{n-2}}{3-2x_{n-2}} = \frac{3-2x_{n-3}}{4-3x_{n-3}}$$
and in general
$$x_{n+1} = \frac{k-(k-1)x_{n-k}}{k+1-kx_{n-k}}$$
Setting $k=n-1$ we get
$$x_{n+1} = \frac{n-1-(n-2)\frac{1}{2}}{n-(n-1)\frac{1}{2}} = \frac{n}{n+1}$$
I haven't checked the second one but I believe the same method should produce the result.
A: This can be proven easily with induction. 
Without induction, for (1), define 
$$y_n := \frac{1}{1-x_n}\Rightarrow x_n = \frac{y_n-1}{y_n}$$
so $y_1=2$ and :
$$ \frac{y_{n+1}-1}{y_{n+1}}=\frac{y_n}{y_n+1}\Rightarrow y_{n+1}=y_n+1$$
From here it's clear that 
$$y_n=y_{n-1}+1=y_{n-2}+2=\ldots=y_1+n-1=n+1$$ 
and thus 
$$x_n=\frac{n+1-1}{n+1}=\frac{n}{n+1}$$
For (2) a similar idea works by defining 
$$y_n := \frac{3(x_n-1)}{x_n-2}$$
and observing that $y_n$ is a geometric progression.
A: 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.
