Matrix powers and recurrence relations

Question

The nth Fibonacci number can be found by raising the matrix $\begin{pmatrix}1 & 1 \\ 1 & 0 \end{pmatrix}$ to the nth power. Are there other recurrence formulas that can be solved like this? This yields faster algorithms for computing them.

Answer 1

Yes - all constant coefficient homogeneous linear recurrence relations can be solved this way:
Let $a_n=\alpha_{1}a_{n-1}+...+\alpha_{r}a_{n-r}$ be a recurrence relation with initial conditions - given $a_0,...,a_{r-1}$. Then, observing that $$\begin{pmatrix}a_{n}\\a_{n-1}\\a_{n-2}\\\vdots\\a_{n-r+1}\end{pmatrix}=\begin{pmatrix} \alpha_1&\alpha_2&\alpha_3&... &\alpha_{r-1}&\alpha_r\\ 1&0&0&...&0&0\\ 0&1&0&...&0&0\\ \vdots& &\ddots& &&\vdots\\ 0&0&0&...&1&0 \end{pmatrix} \begin{pmatrix}a_{n-1}\\a_{n-2}\\a_{n-3}\\\vdots\\a_{n-r}\end{pmatrix}$$ Denote that matrix by $A$. Then we see that $$\begin{pmatrix}a_{n}\\a_{n-1}\\a_{n-2}\\\vdots\\a_{n-r+1}\end{pmatrix}=A^{n-r} \begin{pmatrix}a_{r-1}\\a_{r-2}\\a_{r-3}\\\vdots\\a_{0}\end{pmatrix}$$ So you need to raise $A$ to the $n$th power to find $a_n$.