Rational difference equation

A rational difference equation is a nonlinear difference equation of the form

$x_{n+1}={\frac {\alpha +\sum _{i=0}^{k}\beta _{i}x_{n-i}}{A+\sum _{i=0}^{k}B_{i}x_{n-i}}}~,$

where the initial conditions $x_{0},x_{-1},\dots ,x_{-k}$ are such that the denominator never vanishes for any n.

First-order rational difference equation

A first-order rational difference equation is a nonlinear difference equation of the form

$w_{t+1}={\frac {aw_{t}+b}{cw_{t}+d}}.$ 2

When $a,b,c,d$ and the initial condition $w_{0}$ are real numbers, this difference equation is called a Riccati difference equation.

Such an equation can be solved by writing $w_{t}$ as a nonlinear transformation of another variable $x_{t}$ which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in $x_{t}$.

Equations of this form arise from the infinite resistor ladder problem.

Solving a first-order equation

First approach

WLoG, the determinant-like quantity $ad-bc\neq 0$, and this can be easily seen by noting that, with a division on both the numerator and denominator in Equation (2), you can always set $c=1$, in which case, if $ad-bc=0$, then the numerator and denominator will cancel away, leaving no difference equation left, being instead so completely reduced as to become exactly the constant $a$. Thus, one approach to developing the transformed variable $x_{t}$, is to write

$y_{t+1}=\alpha -{\frac {\beta }{y_{t}}}$

where $\alpha =(a+d)/c$ and $\beta =(ad-bc)/c^{2}$ and where $w_{t}=y_{t}-d/c$.

Further writing $y_{t}=x_{t+1}/x_{t}$ can be shown to yield

$x_{t+2}-\alpha x_{t+1}+\beta x_{t}=0.$

Second approach

The above approach is already of general applicability. This following approach gives a first-order difference equation for $x_{t}$ instead of a second-order one. Let $r^{2}=(d-a)^{2}+4bc$. For the case in which $r^{2}\geqslant 0$, every term will be real-valued and this method may be convenient to use. Otherwise, the method still works, but complex numbers will appear, and it might be more convenient to attempt a trigonometric ansatz instead. Substituting $x_{t}=1/(\eta +w_{t})$, which implies $w_{t}=(1-\eta x_{t})/x_{t}$, into Equation (2), we find that it is always possible to make $x_{t}$ evolve according to the simple inhomogeneous first-order linear difference equation

$x_{t+1}=\left({\frac {d-\eta c}{\eta c+a}}\right)\!x_{t}+{\frac {c}{\eta c+a}}.$

by choosing $\eta$ such that $c\eta ^{2}-(d-a)\eta -b=0$, and it is clear that this can always be done in either of the two choices $\eta _{\pm }={\frac {d-a\pm r}{2c}}$, even when $r\in \mathbb {C}$

Third approach

The equation

$w_{t+1}={\frac {aw_{t}+b}{cw_{t}+d}}$

can also be solved by treating it as a special case of the more general matrix equation

$X_{t+1}=-(E+BX_{t})(C+AX_{t})^{-1},$

where all of A, B, C, E, and X are n × n matrices (in this case n = 1); the solution of this is

$X_{t}=N_{t}D_{t}^{-1}$

where

${\begin{pmatrix}N_{t}\\D_{t}\end{pmatrix}}={\begin{pmatrix}-B&-E\\A&C\end{pmatrix}}^{t}{\begin{pmatrix}X_{0}\\I\end{pmatrix}}.$

Application

It was shown in that a dynamic matrix Riccati equation of the form

$H_{t-1}=K+A'H_{t}A-A'H_{t}C(C'H_{t}C)^{-1}C'H_{t}A,$

which can arise in some discrete-time optimal control problems, can be solved using the second approach above if the matrix C has only one more row than column.

Further reading

• Simons, Stuart, "A non-linear difference equation," Mathematical Gazette 93, November 2009, 500–504.