# The theory behind linear recurrence relations solving (or - why does it work?)

tl;dr - a recommendation for a good book that explains the theory behind the auxiliary polynomial/companion matrix methods to solve linear recurrence relations with constant coefficients?

I've bumped into a linear recursive relation problem and it reminded me the auxiliary polynomial technique from basic combinatorics class.
In retrospective, I understand it has to do with Jordan normal forms and Jordan chains. I also checked Wikipedia and found the linear algebra methods, I can see how they are equivalent and why does it work when all the eigenvalues are distinct (and the companion matrix is diagonalizable. Alternatively, the linear system matrix for any initial values is invertible as a Van der Monde matrix). I'm a bit rusty on Jordan normal forms though, so a little help will be great. I tried a few books, mostly those that are referenced from Wikipedia, but they seem to miss this point.
Any reference suggestion will much be appreciated, thanks.

• what is your linear algebra background? Have you learned about modules and spaces? It's a bit hard to motivate these tools without. – Don Thousand Mar 20 at 19:16
• Start with a linear recurrence with constant coefficients. Re-write it using the operator $S a_n=a_{n+1}$. Then replace each occurrence of $S^{k}a_n$ by a new sequence $x_n^{k}$ and add new equations $x_{n}^{k+1}=S y_{n}^{k}$. The system then has the form $X_n=AX_{n-1}$, where $X_n$ is a vector with components $x_n^k$ and $A$ is a matrix with constant coefficients. The solution of this system is $X_n=A^nX_0$. Then it is clear why the Jordan decomposition is related. If $A=P^{-1}JP$, then $A^n=P^{-1}J^nP$. – user647486 Mar 20 at 19:45
• I don't recall a book for recurrence equations that I am sure has this content, but if you lack them you can use as replacement books in Ordinary Differential Equations. They will likely have it for linear differential equations. You just need to replace derivative of $y$ by $\Delta y_n=y_{n+1}-y_n$ or $y_{n+1}$ by $Sy_n$. – user647486 Mar 20 at 19:51
• @DonThousand I have basic knowledge in modules, mostly from a basic course in rings and fields. I'll at least give it a shot. Thanks. – galra Mar 20 at 19:57
• @user647486 I see how it is related to the Jordan forms this way, but since it has been some time since I last dealt with it, I'm missing the step between this and how the decomposition should look (except that each eigenvalue will have a single block), and from that the Jordan chains. I'll check for ODE books. Thanks. – galra Mar 20 at 19:57