Merge pull request #1455 from cp-algorithms/fibmatrix

mhayter · web-flow · commit 546ce1188d40 · 2025-04-21T23:58:03.000-04:00
Fibonacci: restore matrix power form
diff --git a/src/algebra/fibonacci-numbers.md b/src/algebra/fibonacci-numbers.md
@@ -159,7 +159,20 @@ F_{n}
 \end{pmatrix}
 $$
 
-where $F_1 = 1, F_0 = 0$.
+where $F_1 = 1, F_0 = 0$. 
+In fact, since 
+
+$$
+\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}
+= \begin{pmatrix} F_2 & F_1 \\ F_1 & F_0 \end{pmatrix}
+$$
+
+we can use the matrix directly:
+
+$$
+\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n
+= \begin{pmatrix} F_{n+1} & F_n \\ F_n & F_{n-1} \end{pmatrix}
+$$
 
 Thus, in order to find $F_n$ in $O(\log  n)$ time, we must raise the matrix to n. (See [Binary exponentiation](binary-exp.md))
 
