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

Question

Please help to solve:

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

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:

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

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

Answer 1

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.

Answer 2

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.

Answer 3

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.