Recurrence relationship How do you solve the following recurrence relationship?
$$x_{n} = \frac{x_{n-1}}{1 + x_{n-1}}$$
where
$$ x(0) = 1 $$
I know the answer is 
$$ x_n = \frac{1}{n+1}$$
I solved it by induction. But I don't like it that much since I always feel like I'm cheating when I solve by induction. I assume I already know the answer.
Is there a better way?
thanks
 A: Using the hints in the comments, we let $y_n = 1/x_n$ so that $y_0 = 1/1 = 1$ and:
$$
\frac{1}{y_n}
= \frac{\frac{1}{y_{n-1}}}{1 + \frac{1}{y_{n-1}}}
= \frac{1}{y_{n-1} + 1}
$$
But by taking reciprocals of both sides, we obtain an easily solved linear recurrence relation:
\begin{align*}
y_n
&= y_{n-1} + 1 \\
&= (y_{n-2} + 1) + 1 = y_{n-2} + 2 \\
&= (y_{n-3} + 1) + 2 = y_{n-3} + 3 \\
&= \cdots \\
&= y_0 + n = 1 + n &\text{using implicit induction} 
\end{align*}
Hence, we conclude that $x_n = \frac{1}{1 + n}$.
A: This is a Ricatti recurrence, of the form:
$\begin{align}
x_{n + 1} = \frac{a x_n + b}{c x_n + d}
\end{align}$
with $c \ne 0$ and $a d - b c \ne 0$.
It is one of the few nonlinear recurrences with exact solution. I know of three techniques.
First one is due to Brand "A Sequence Defined by a Difference Equation", AMM 62(7), pp. 489-492 (1955). Substituting $y_n = c x_n + d$ gives an equation of the form:
$\begin{align}
y_{n + 1} = \alpha + \frac{\beta}{y_n}
\end{align}$
with $y_n = \frac{w_{n + 1}}{w_n}$ you get the second order recurence:
$\begin{align}
w_{n + 2} - \alpha w_{n + 1} + \beta w_n = 0
\end{align}$
Solving this one (can fix $w_0, w_1$ arbitrarily so to get the given $x_0$), and substituting back gives the solution.
Another technique is due to Mitchell, "An Analytic Riccati Solution for Two-Target Discrete-Time Control", Journal of Economic Dynamics and Control 24(4), pp 615-622 (2000), Define the auxiliary sequence:
$\begin{align}
y_n = \frac{1}{1 + \eta x_n}
\end{align}$
Write the recurrence in terms of $y_n$ to get:
$\begin{align}
    y_{n + 1}
      = \frac{(d \eta - c) y_n + c}
      {(b \eta^2 - (a - d) \eta - c) y_n + a \eta + c}
\end{align}$
Select $\eta$ so this is a linear recurrence of first order, i.e., $b \eta^2 - (a - d) \eta - c = 0$ Both zeros will do.
Third idea is to note that the function giving $x_{n + 1}$ is a Möbius transform, and those form a group. In particular, if:
$\begin{align}
\mathbf{A} = \pmatrix{a & b \\ c & d}
\end{align}$
the composition of the transforms described by $\mathbf{A}$ and $\mathbf{B}$ is described by $\mathbf{A} \cdot \mathbf{B}$. I.e., you have that $x_n$ is applying $\mathbf{A}^n$ to $x_0$. Diagonalize $\mathbf{A}$ and the power is trivial to compute.
