Rational difference equation

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

[math]\displaystyle{ x_{n+1} = \frac{\alpha+\sum_{i=0}^k \beta_ix_{n-i}}{A+\sum_{i=0}^k B_ix_{n-i}}~, }[/math]

where the initial conditions [math]\displaystyle{ x_{0}, x_{-1},\dots, x_{-k} }[/math] 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

[math]\displaystyle{ w_{t+1} = \frac{aw_t+b}{cw_t+d}. }[/math]

When [math]\displaystyle{ a,b,c,d }[/math] and the initial condition [math]\displaystyle{ w_0 }[/math] are real numbers, this difference equation is called a Riccati difference equation.

Such an equation can be solved by writing [math]\displaystyle{ w_t }[/math] as a nonlinear transformation of another variable [math]\displaystyle{ x_t }[/math] which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in [math]\displaystyle{ x_t }[/math].

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

Solving a first-order equation

First approach

One approach to developing the transformed variable [math]\displaystyle{ x_t }[/math], when [math]\displaystyle{ ad-bc \neq 0 }[/math], is to write

[math]\displaystyle{ y_{t+1}= \alpha - \frac{\beta}{y_t} }[/math]

where [math]\displaystyle{ \alpha = (a+d)/c }[/math] and [math]\displaystyle{ \beta = (ad-bc)/c^{2} }[/math] and where [math]\displaystyle{ w_t = y_t -d/c }[/math].

Further writing [math]\displaystyle{ y_t = x_{t+1}/x_t }[/math] can be shown to yield

[math]\displaystyle{ x_{t+2} - \alpha x_{t+1} + \beta x_t = 0. }[/math]

Second approach

This approach gives a first-order difference equation for [math]\displaystyle{ x_t }[/math] instead of a second-order one, for the case in which [math]\displaystyle{ (d-a)^{2}+4bc }[/math] is non-negative. Write [math]\displaystyle{ x_t = 1/(\eta + w_t) }[/math] implying [math]\displaystyle{ w_t = (1- \eta x_t)/x_t }[/math], where [math]\displaystyle{ \eta }[/math] is given by [math]\displaystyle{ \eta = (d-a+r)/2c }[/math] and where [math]\displaystyle{ r=\sqrt{(d-a)^{2}+4bc} }[/math]. Then it can be shown that [math]\displaystyle{ x_t }[/math] evolves according to

[math]\displaystyle{ x_{t+1} = \left(\frac{d-\eta c}{\eta c+a}\right)\!x_t + \frac{c}{\eta c+a}. }[/math]

Third approach

The equation

[math]\displaystyle{ w_{t+1} = \frac{aw_t+b}{cw_t+d} }[/math]

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

[math]\displaystyle{ X_{t+1} = -(E+BX_t)(C+AX_t)^{-1}, }[/math]

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

[math]\displaystyle{ X_t = N_tD_t^{-1} }[/math]

where

[math]\displaystyle{ \begin{pmatrix} N_{t} \\ D_{t}\end{pmatrix} = \begin{pmatrix} -B & -E \\ A & C \end{pmatrix}^t\begin{pmatrix} X_0\\ I \end{pmatrix}. }[/math]

Application

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

[math]\displaystyle{ H_{t-1} = K +A'H_tA - A'H_tC(C'H_tC)^{-1}C'H_tA, }[/math]

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.