Recurrence relationship

Question

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

Answer 1

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

Answer 2

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.