How to compute the nth number of a general Fibonacci sequence with matrix multiplication?

Question

If we want to compute the nth Fibonacci number we just power the matrix $M = \left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]$ $n$ times and we get $M =\left[ \begin{array}{cc} F_{n+1} & F_n \\ F_n & F_{n-1} \end{array}\right]$ But, How should be the elements arranged when I want to find the $n$th term of the fibonnaci series whose starting elements are $a$ and $b$?

Answer 1

If $a_{n} = a_{n-1} + a_{n-2}$, then $$ {\begin{bmatrix} 1 & 1 \\ 1 & 0 \\ \end{bmatrix}}^n \begin{bmatrix} a_1 \\ a_0 \\ \end{bmatrix} = \begin{bmatrix} a_{n+1} \\ a_n \end{bmatrix} $$ for any $a_0, a_1$. Any linear recurrence relation can be solved using matrix exponentiation, e.g., $a_{n}=a_{n-1}-3a_{n-3}+5a_{n-5}-7$. See this blog post: Recurrence relation and matrix exponentiation.

Answer 2

Just multiply your power matrix by the vector $[a,b]$ and you will get the $n+1$th and $n$th terms of your sequence as the resultant vector.

Answer 3

If you have a sequence, say $G_{-1} = a, G_0 = b$, and $G_{n+1} = G_{n} + G_{n-1}$, note that $$\left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]\cdot\left[\begin{array}{c} G_n \\ G_{n-1} \end{array}\right] = \left[\begin{array}{c} G_n + G_{n-1} \\ G_n \end{array}\right] = \left[\begin{array}{c} G_{n+1} \\ G_n \end{array}\right].$$

Then it isn't too hard to show that $$\left[\begin{array}{cc} 1 & 1 \\ 1 & 0 \end{array}\right]^n\cdot\left[\begin{array}{c} b \\ a \end{array}\right] = \left[\begin{array}{c} G_{n} \\ G_{n-1} \end{array}\right].$$