# Matrix Methods for Difference Problems

• MHB
• topsquark

#### topsquark

Gold Member
MHB
I'm looking at ways of solving 2nd order difference equations with non-constant coefficients. I am working on a method to use transformations (ie rewriting the equation in new variables) to change the form of the equation. Such as $$\displaystyle a_{n + 2} + f(n) a_{n +1} + g(n) a_n = 0$$ to something like $$\displaystyle u_{n + 2} + h(n) u_n = k(n)$$ I don't know if this is even possible but I thought I'd give it a try. Anyway, I'm starting with some simple examples and I'm already running into theoretical troubles. Say we have the system:
$$\displaystyle a_{n + 1} = n^2 b_n$$ and $$\displaystyle b_{n + 1} = a_n$$.

I would like to write something like
$$\displaystyle \left ( \begin{matrix} a_{n + 1} \\ b_{n + 1} \end{matrix} \right ) = \left ( \begin{matrix} 0 & n^2 \\ 1 & 0 \end{matrix} \right ) \left ( \begin{matrix} a_n \\ b_n \end{matrix} \right )$$

I can "solve" this using the usual Linear Algebra methods (diagonalize the matrix, solve the problem in the eigenvector basis, then transform back to the original variables) but the problem is that there is a new connection... I can always make $$\displaystyle a_{n + 1}$$ from $$\displaystyle a_n$$ just by taking n -> n +1 and that seems to ruin the method. Is there any matrix method I can use to work with this?

In case anyone cares: the solution to $$\displaystyle a_{n + 2} - 3n a_n = 0$$ is
$$\displaystyle a_n = - (-1)^{n(n + 1)/2} (-3)^{n/2} (n - 2)! \left ( A + B \sum_{k = 1}^{n - 1} (-1)^k \right )$$

(I'm trying to find a good function to simplify that $$\displaystyle (-1)^{n(n + 1)/2}$$. Any suggestions?)

I've been having fun stretching my new skills in Difference Calculus. I already know I've only scratched the surface but I found a set of talks on the internet yesterday on Galois theory of Difference Equations. I only know a teensy touch of Galois theory so I didn't really look at it.

-Dan

Last edited by a moderator:
In theory if you write your system as $$\mathbf{a}_{n+1} = A(n)\mathbf{a}_n$$ then the solution is simply $$\mathbf{a}_n = \left(\prod_{k=0}^{n-1} A(n-1-k)\right)\mathbf{a}_0.$$ (The meaning of this is that $A_0$ is rightmost factor and $A_{n-1}$ is the leftmost.)

However, trying to compute the product by diagonalizing the factors may not work: the eigenvectors of $A(k)$, and thus the change of variable necessary to diagonalize it, will in principle depend on $k$. It may not be possible to find a single change of variable which diagonalizes all of them simultaneously.

The solution of $a_{n+2} + f(n)a_n = 0$ is best found by treating even and odd terms separately. Setting $n = 2m$ gives $$a_{2(m+1)} = -f(2m)a_{2m}$$ which is a first order recurrence with solution $$a_{2m} = (-1)^m\left(\prod_{k=0}^{m-1}f(2k)\right)a_0$$ whilst $n= 2m+1$ gives $$a_{2(m+1)+1} = -f(2m+1)a_{2m+1}$$ which has solution $$a_{2m+1} = (-1)^m\left(\prod_{k=0}^{m-1} f(2k+1)\right)a_1.$$ It is best not to combine these into a single expression for $a_n$.

• topsquark
Very interesting. As it happens I'm currently taking a break from my Physics studies and am working on some Math. My most recent project is how to solve second order recursions with non-constant coefficients. I learned the basics of Difference Calculus but I haven't been able to find much of anything on the net about non-constant coefficients. I came up with a method but it's rather "inelegant" to say the least.

Do you have any suggestions for sources on this?

Thanks!
-Dan