Recurrence relations over division algebras

We generalize the solution of linear recurrence relations from fields to central division algebras, adapting the standard tools of companion matrices and characteristic polynomials to the non-commutative setting. We then solve linear recurrences of order 2 over octonion division algebras.