Sign in to watch this lesson
Advanced - Number Theory · 4:31
Matrix Exponentiation and Fibonacci
Multiplying the pair (F_n, F_n-1) by the matrix [[1,1],[1,0]] moves it one step along the Fibonacci sequence, so the n-th power of that matrix holds F_n, and binary exponentiation computes it with about log n matrix products. We cover fast doubling, the identities the matrix explains (Cassini and gcd(F_m, F_n) = F_gcd(m,n)), and the same technique for any linear recurrence and for counting walks in a graph.
You will learn
- Write the Fibonacci step as a 2×2 matrix and explain why A^n = [[F_n+1, F_n], [F_n, F_n-1]]
- Compute F_n mod p for n up to 10^18 with binary exponentiation of matrices, starting from the identity and reducing inside the multiplication
- Use fast doubling and the identities Cassini and gcd(F_m, F_n) = F_gcd(m,n)
- Turn any order-d linear recurrence into a d×d matrix, and count walks of length k with the k-th power of an adjacency matrix