Solving system of coupled recurrence relations

Question

Say you are given a system of $k$ coupled recurrence relations, subject to some initial conditions, that you want to solve. For example, \begin{align} A_1(n)&= c_{11}A_1(n-1)+c_{12}A_2(n-1)+\cdots c_{1k}A_k(n-1)\\ A_2(n)&= c_{21}A_1(n-1)+c_{22}A_2(n-1)+\cdots c_{2k}A_k(n-1)\\ &\vdots \\ A_k(n)&=c_{k1}A_1(n-1)+c_{k2}A_2(n-1)+\cdots c_{kk}A_k(n-1) \end{align} How would one go about solving this? I tried finding some kind of method of solving these, but almost all of the ones I have seen were for $k=2$ and use some sort of algebraic manipulation and substitution. In this case that would not be feasible. Is there some way to solve these equations, maybe in a similar way that coupled ODEs are solved?

Answer 1

In matrix notation,

$$A_n=CA_{n-1},$$ and by induction,

$$A_n=C^nA_0.$$

This is indeed an exponential solution, as in the case of differential equations.

Now if $C$ is diagonizable, i.e. $$C=P\Lambda P^{-1},$$ we have $$C^n=P\Lambda^{n}P^{-1}$$ which shows that the solution is a linear combination of vectors weighted by exponential factors $\lambda^n$.