A rational difference equation is a nonlinear difference equation of the form
x n + 1 = α + ∑ i = 0 k β i x n − i A + ∑ i = 0 k B i x n − i , {\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 x 0 , x − 1 , … , x − k {\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
When a , b , c , d {\displaystyle a,b,c,d} and the initial condition w 0 {\displaystyle w_{0}} are real numbers, this difference equation is called a Riccati difference equation. Such an equation can be solved by writing w t {\displaystyle w_{t}} as a nonlinear transformation of another variable x t {\displaystyle x_{t}} which itself evolves linearly. Then standard methods can be used to solve the linear difference equation in x t {\displaystyle 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 a d − b c ≠ 0 {\displaystyle 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 {\displaystyle c=1} , in which case, if a d − b c = 0 {\displaystyle 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 {\displaystyle a} . Thus, one approach to developing the transformed variable x t {\displaystyle x_{t}} , is to write
y t + 1 = α − β y t {\displaystyle y_{t+1}=\alpha -{\frac {\beta }{y_{t}}}}
where α = ( a + d ) / c {\displaystyle \alpha =(a+d)/c} and β = ( a d − b c ) / c 2 {\displaystyle \beta =(ad-bc)/c^{2}} and where w t = y t − d / c {\displaystyle w_{t}=y_{t}-d/c} . Further writing y t = x t + 1 / x t {\displaystyle y_{t}=x_{t+1}/x_{t}} can be shown to yield
x t + 2 − α x t + 1 + β x t = 0. {\displaystyle 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 {\displaystyle x_{t}} instead of a second-order one. Let r 2 = ( d − a ) 2 + 4 b c {\displaystyle r^{2}=(d-a)^{2}+4bc} . For the case in which r 2 ⩾ 0 {\displaystyle 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 / ( η + w t ) {\displaystyle x_{t}=1/(\eta +w_{t})} , which implies w t = ( 1 − η x t ) / x t {\displaystyle w_{t}=(1-\eta x_{t})/x_{t}} , into Equation (2), we find that it is always possible to make x t {\displaystyle x_{t}} evolve according to the simple inhomogeneous first-order linear difference equation
x t + 1 = ( d − η c η c + a ) x t + c η c + a . {\displaystyle x_{t+1}=\left({\frac {d-\eta c}{\eta c+a}}\right)\!x_{t}+{\frac {c}{\eta c+a}}.}
by choosing η {\displaystyle \eta } such that c η 2 − ( d − a ) η − b = 0 {\displaystyle c\eta ^{2}-(d-a)\eta -b=0} , and it is clear that this can always be done in either of the two choices η ± = d − a ± r 2 c {\displaystyle \eta _{\pm }={\frac {d-a\pm r}{2c}}} , even when r ∈ C {\displaystyle r\in \mathbb {C} }
Third approach The equation
w t + 1 = a w t + b c w t + d {\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
X t + 1 = − ( E + B X t ) ( C + A X t ) − 1 , {\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
X t = N t D t − 1 {\displaystyle X_{t}=N_{t}D_{t}^{-1}}
where
( N t D t ) = ( − B − E A C ) t ( X 0 I ) . {\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 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 , {\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
Further reading Simons, Stuart, "A non-linear difference equation," Mathematical Gazette 93, November 2009, 500–504.