Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

I have the following recurrence relation:

\begin{equation} A[n]=f_A[n-1] A[n-1] + f_B[n-1]B[n-1], \\ B[n]=g_A[n-1] A[n-1] + g_B[n-1]B[n-1], \end{equation}

where $f_{A/B}$ and $g_{A/B}$ are known complex functions that vary at each step $n$. I would like to know $A[n+i]$ in terms of $A[n]$ and $B[n]$, for some positive integer $i$.

I have taken the obvious approach of putting the coefficients into a matrix $X[n]=\mathcal{M}_{n-1}X[n-1]$ where

\begin{equation} \mathcal{M}_n = \begin{pmatrix} f_A[n] & f_B[n] \\ g_A[n] & g_B[n] \\ \end{pmatrix}. \end{equation}

With my functions $f$ and $g$ (I can put them in later if it matters) the determinant of $\mathcal{M}_n$ is non-zero, so it has an inverse and should be able to be diagonalized --- the eigenvalues and eigenvectors are of course trivial to find. If $f$ and $g$ were constant, this would just be a matter of diagonalizing $\mathcal{M}$ and finding the $i$-th power. However, the basis which diagonalizes $\mathcal{M}_n$ changes depending on when $f_B$ and $g_A$ are zero. OK, so I attempt to break my problem into pieces where I can take $j$ steps in one basis before shifting to another. After I do this, however, I'm not finding it straightforward how to express my desired result $A[n+i]=\mathcal{F}(A[n]+B[n])$. Furthermore, in an effort to be as general as possible, I'm trying to consider general functions $f_{A/B}$ and $g_{A/B}$ that may be zero at known, but arbitrary steps $n$, which compounds my difficulties.

I'm a physicist and don't run into recurrence relations everyday. Also, I'm finding that my undergraduate linear algebra tools have unfortunately rusted a bit. Help?

share|improve this question
You are taking the product of a number of 2x2 matrices (applied to some vector). Without further information the result could be "just about anything", truly. –  Charles Matthews Feb 3 '13 at 21:49
@Charles Matthews: I'm not sure if I understand what you're saying. If you just carry out the substitutions for say $n+2$ you can see that $A[n+2]=(f_A[n+1]f_A[n]+f_B[n+1]g_B[n])A[n] + (f_A[n+1]f_B[n] + f_B[n+1]g_b[n])B[n]$, which is clearly showing some structure (which I'm having trouble identifying). $A[n+i]$ can't be "just about anything," but rather some function of $f$ and $g$ evaluated at all integers between $n$ and $n+i$. –  cosmoguy Feb 3 '13 at 22:10
The point is that we don't know your $f$'s and $g$'s. $X_n = P_n X_0$ where $P_n = {\cal M}_n \ldots {\cal M}_1$ could be any sequence of invertible matrices: just take ${\cal M}_n = P_n P_{n-1}^{-1}$. –  Robert Israel Feb 3 '13 at 22:48
The point is: can I get $A[n+i]$ regardless of the exact form of the sequences $f_{A/B}$ and $g_{A/B}$? This is very general, but the recurrence equations, plus 2 boundary conditions, uniquely determines the linear system. Is this a known (or achievable) result? Note that with some substitution we can get the equations into the form $A[n]=\alpha(n) A[n-1]+\beta(n) A[n-2]$ for some $\alpha$ and $\beta$. Is this linear recurrence equation able to be solved by some method I'm ignorant to? –  cosmoguy Feb 4 '13 at 0:46
One can produce any sequence whatever of (nonzero) vectors for $X[n]$, by choosing $f$ and $g$ correctly. And once $X$ becomes zero, it will remain zero thereafter. In the absence of any knowledge of $f$ and $g$, there is nothing more to be said. Perhaps if you explained what your actual problem is, someone might be able to help. I don't know why you're trying to keep $f$ and $g$ secret from us-- you must have some theory that constrains them. –  Carl Feynman Feb 4 '13 at 4:25

Your Answer


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

Browse other questions tagged or ask your own question.