Rational difference equation

A rational difference equation is a nonlinear difference equation of the form^[1][2][3][4]

${\displaystyle 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 ${\displaystyle 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

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

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

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

Equations of this form arise from the infinite resistor ladder problem.^[5][6]

Solving a first-order equation

First approach

One approach^[7] to developing the transformed variable ${\displaystyle x_{t}}$ , when ${\displaystyle ad-bc\neq 0}$ , is to write

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

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

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

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

Second approach

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

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

Third approach

The equation

${\displaystyle 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

${\displaystyle 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^[9]

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

where

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

Application

It was shown in ^[10] that a dynamic matrix Riccati equation of the form

${\displaystyle 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.

References

1. Skellam, J.G. (1951). “Random dispersal in theoretical populations”, Biometrika 38 196−–218, eqns (41,42)
2. Camouzis, Elias; Ladas, G. (November 16, 2007). Dynamics of Third-Order Rational Difference Equations with Open Problems and Conjectures. CRC Press. ISBN 9781584887669 – via Google Books.
3. Kulenovic, Mustafa R. S.; Ladas, G. (July 30, 2001). Dynamics of Second Order Rational Difference Equations: With Open Problems and Conjectures. CRC Press. ISBN 9781420035384 – via Google Books.
4. Newth, Gerald, "World order from chaotic beginnings", Mathematical Gazette 88, March 2004, 39-45 gives a trigonometric approach.
5. "Equivalent resistance in ladder circuit". Stack Exchange. Retrieved 21 February 2022.
6. "Thinking Recursively: How to Crack the Infinite Resistor Ladder Puzzle!". Youtube. Retrieved 21 February 2022.
7. Brand, Louis, "A sequence defined by a difference equation," American Mathematical Monthly 62, September 1955, 489–492. online
8. Mitchell, Douglas W., "An analytic Riccati solution for two-target discrete-time control," Journal of Economic Dynamics and Control 24, 2000, 615–622.
9. Martin, C. F., and Ammar, G., "The geometry of the matrix Riccati equation and associated eigenvalue method," in Bittani, Laub, and Willems (eds.), The Riccati Equation, Springer-Verlag, 1991.
10. Balvers, Ronald J., and Mitchell, Douglas W., "Reducing the dimensionality of linear quadratic control problems," Journal of Economic Dynamics and Control 31, 2007, 141–159.

Further reading

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