Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am trying to solve this rational recursive relation:


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.

share|improve this question
When $E$ is a constant you are iterating a linear fractional transformation, or Mobius transformation (en.wikipedia.org/wiki/M%C3%B6bius_transformation), and this is easy to do in closed form by finding the eigenvalues and eigenvectors of an associated matrix. When $E$ is not a constant you are instead more or less composing a family of a priori unrelated matrices and I don't think you should expect anything reasonable unless you know more about $E[n]$ (for example if it were periodic you would still be fine). –  Qiaochu Yuan Feb 20 '12 at 20:56
I don't really know what kind of a "solution" you're even looking for. With some ingenuity you could probably write down some monstrous expression involving all of the $E[n]$s, but what good would it do you? What do you actually want to know? –  Qiaochu Yuan Feb 20 '12 at 20:59
@QiaochuYuan In the simplest form of my problem, I am given $D$ and a constraint on $\sum_{k=1}^nE[k]$ and am trying to minimize $T[n]$. Looks like this might be very hard to do. –  M.B.M. Feb 20 '12 at 21:12
Is $n$ fixed? You might try seeing what happens in the special case that $E[k]$ has small period (since you can reduce to the case of iterating a single linear fractional transformation). –  Qiaochu Yuan Feb 20 '12 at 21:19
$n$ is fixed. $E[k]$ might be periodic in the physical interpretation of the problem, so I'll try that. What do you mean by "iterating a linear fractional transformation," how does one reduce the periodic case to it, and what is the associated matrix? I am not that familiar with group theory (I think the wikipedia article you cited uses the results from it) but I am reasonably good at linear algebra. –  M.B.M. Feb 20 '12 at 21:33

2 Answers 2

up vote 1 down vote accepted

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

share|improve this answer

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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.