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