Solve nonlinear Recurrence Relation

Question

I am trying to solve the following recurrence relation for general constants $c_1,c_2,c_3$:

$R(k) = c_1 + \frac{c_2}{R(k-1)}$, $R(0)=c_3$

I got a solution from Mathematica, but can't figure out how to get there.

Answer 1

Change variables to $u_k = R(k) - c_1$, you get a Ricatti recurrence:

$\begin{align*} u_{k + 1} &= \frac{c_2}{u_k + c_1} \end{align*}$

Ricatti recurrences have the form:

$\begin{align*} w_{n + 1} &= \frac{a w_n + b}{c w_n + d} \end{align*}$

where $c \ne 0$ and $a d \ne b c$.

A way to solve them is to use the substitution $x_n = 1 / (1 + \eta w_n)$, which gives after light massage:

$\begin{align*} x_{n + 1} &= \frac{(d \eta - c) x_n + c} {(b \eta^2 - (a - d) \eta - c) x_n + a \eta + c} \end{align*}$

Pick $\eta$ so this reduces to a linear recurrence, and you are set.