# Linear Recursive Sequence

We derive a general technique for solving full rank linear recursive sequences. Formally, a k^{th} linear recursive sequence is defined as

- 13 August, 2012 -
- Article, Math Problems -
- Tags : algebra, analysis, titu
- 0 Comments

In vector form, we can use the notation

In this sense, is just the initial condition vector

Where as can be expressed as

If you’ve studied linear algebra before, you may recognize this immediately as . Let’s find what the transform is.

similarly

So the problem is reduced down to one of finding . Supposing that we have a full set of eigenvalues, then the characteristic polynomial

Setting , the distinct roots satifying the equation are the eigenvalues of . Since has a full rank of eigenvectors, it must be the case that is diagonalizable, that is . Therefore

suggests that is also a linear combination of . That is,

The coefficients can be found via the initial value problem

Therefore .