5
$\begingroup$

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$?

$\endgroup$
6
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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].$$

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.