Let some matrix be $A$, what methods are there for attaining a recurrence relation which allows us to calculate - for example - the leading term in the matrix $A^n$ when given the leading terms of a sufficient amount of previous matrices $A^{n-1}, A^{n-2},...$
I ask this because I was studying the leading term in the matrix $A^n$ where $$A= \begin{bmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \\ 7 & 8 & 9 \\ \end{bmatrix} $$ which can be found in a ridiculous closed form (https://oeis.org/A321045), but has the following recurrence relation between the nth powers of the matrix: $$a(n+2)=15a(n+1)+18a(n)$$ for $n \ge 1$. How does one find a relation like this or equivalently find it's corresponding generating function - $\frac{3x^2+14x-1}{18x^2+15x-1}$ ?
First, find some relation between “small” powers of $A$, eg here I guess $A^3=15A^2+18A$ (For this, you can try and test or use Cayley-Hamilton). Then multiply everything by $A^{n-1}$.