Help on a rational recursive relation: $T[n+1]=\frac{E[n+1](D+T[n])}{E[n+1]+D+T[n]}$

Question

I am trying to solve this rational recursive relation:

$$T[n+1]=\frac{E[n+1](D+T[n])}{E[n+1]+D+T[n]}$$

where $T[1]=\frac{E[1]*D}{E[1]+D}$ for constant $D>0$ and $E[n]>0$.

When $E[n]$ is replaced by a constant $E$ (independent of $n$), Wolfram Mathematica's RSolve (after FullSimplify) yields the following:

$$T[n]=\frac{2E}{1+\sqrt{1+4E/D}-\frac{2\sqrt{1+4E/D}\left(D+2E-\sqrt{D(D+2E)}\right)^n}{\left(D+2E-\sqrt{D(D+2E)}\right)^n- \left(D+2E+\sqrt{D(D+2E)}\right)^n}}$$

I assume that for constant $E$ Mathematica used methods for solving rational difference equations (but I really have no knowledge of the inner workings of that software package). It's not helpful when function $E[n+1]$ is inserted in lieu of constant $E$.

To extend the result above to function $E[n]$ I've tried writing out the first few iterations of it (using RecurrenceTable function in Mathematica with and without Simplify and FullSimplify), however, no pattern emerged to me (though, perhaps the community can see something -- I can try to post it to the question if that would be helpful). I am not very familiar with recurrence relations beyond some basic facts s.t. the Master Theorem. Is this thing even soluble? I would be very happy with a solution involving sums and products of $E[n]$. Any help would be very much appreciated.

This arose out of my question on the stats forum regarding Bayesian inference using noisy observations of a Brownian motion process.

Answer 1

Mitchell "An Analytic Riccati Solution for Two-Target Discrete-Time Control", Journal of Economic Dynamics and Control 24(4), 615-622 (2000) uses an interesting trick to solve the Ricatti recurrence: $$ w_{n + 1} = \frac{a w_n + b}{b w_n + d} $$ Use the replacement $x_n = 1 / (1 + \eta w_n)$, select $\eta$ such that the result is a first order, linear recurrence in $x_n$. If $a$, $b$, $c$, and $d$ are functions of $n$, so will be $\eta$, and the resulting recurrence is linear, first order and thus has a explicit solution even if the coefficients aren't constant. But unless you are as lucky as textbook writers are with all the problems that come their way, the result will be a much worse mess than just iterating the recurrence.

Answer 2

Let $f(z) = \frac{az + b}{cz + d}$ be a fractional linear transformation. ($a, b, c, d$ can be taken to be complex numbers if you want but what I'm about to say works over any field.) The problem of studying a sequence $z_n$ of numbers satisfying $$z_{n+1} = f(z_n)$$

reduces to the problem of iterating $f$. Perhaps surprisingly, this can be done using matrix multiplication.

Lemma: Let $f(z) = \frac{az + b}{cz + d}, g(z) = \frac{pz + q}{rz + s}$ be two fractional linear transformations. Then $(fg)(z) = \frac{tz + u}{vz + w}$ where $$\left[ \begin{array}{cc} t & u \\\ v & w \end{array} \right] = \left[ \begin{array}{cc} a & b \\\ c & d \end{array} \right] \left[ \begin{array}{cc} p & q \\\ r & s \end{array} \right].$$

An alternate group-theoretic statement is that the invertible transformations of the form $\frac{az + b}{cz + d}$ form a group, the projective general linear group $\text{PGL}_2(F)$, and there is a natural surjective homomorphism from the general linear group $\text{GL}_2(F)$ of invertible $2 \times 2$ matrices to this group. The way I stated it above doesn't require the assumption of invertibility, but if the associated matrix is not invertible then the transformation is a constant and the lemma isn't interesting anyway.

The lemma can be proven by direct computation, but a more conceptual explanation is given by a study of how $\text{GL}_2(F)$ acts on lines through the origin in $F^2$; see this blog post.

In this way the problem of iterating a fractional linear transformation reduces to the problem of taking powers of a $2 \times 2$ matrix, and to do this it suffices to find its Jordan normal form. If the associated matrix is diagonalizable then we just have to take powers of the eigenvalues and using that idea you can derive the Mathematica formula in the case where $E$ is a constant.

In the case where $E$ is periodic with small period $j$, just restrict your attention to what happens when you run the iteration $j$ times. This will be described by some specific fractional linear transformation which you can iterate by the above method until you get close to $n$.