Rational difference equation

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

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

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

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.^[5]^[6]

Solving a first-order equation

First approach

One approach^[7] to developing the transformed variable $x_{t}$ , when $ad-bc\neq 0$ , 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

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

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

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^[9]

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 ^[10] 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.

References

^ Skellam, J.G. (1951). “Random dispersal in theoretical populations”, Biometrika 38 196−218, eqns (41,42)
^ 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.
^ ^a ^b 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.
^ Newth, Gerald, "World order from chaotic beginnings", Mathematical Gazette 88, March 2004, 39-45 gives a trigonometric approach.
^ "Equivalent resistance in ladder circuit". Stack Exchange. Retrieved 21 February 2022.
^ "Thinking Recursively: How to Crack the Infinite Resistor Ladder Puzzle!". Youtube. Retrieved 21 February 2022.
^ Brand, Louis, "A sequence defined by a difference equation," American Mathematical Monthly 62, September 1955, 489–492. online
^ Mitchell, Douglas W., "An analytic Riccati solution for two-target discrete-time control," Journal of Economic Dynamics and Control 24, 2000, 615–622.
^ 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.
^ 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.