@shafik There's a lot of nice proofs. You know the iterative algorithm:
(x, y) = (0, 1)
for i in range(n):
(x, y) = (y, x + y)
Notice that (x, y) = (y, x + y) is a linear operator acting on the state vector (x, y) to advance it by 1 step. Indeed, (y, x + y) = (0x + 1y, 1x + 1y), so the corresponding 1-step matrix F is [[0, 1], [1, 1]. The final state of (x, y) after n steps is F * F * ... * F * (x, y) which you can left-associate to F^n * (x, y). Now compute the matrix exponential F^n.
@shafik You can compute matrix exponentials efficiently by binary exponentiation (repeated squaring) in O(log n) scalar operations versus O(n) for the initial step-by-step algorithm. Binet's formula results from the diagonalization of the F matrix: the phi and -1/phi in Binet's formula are F's two eigenvalues. The matrix approach works for linear recurrences in general.
Add comment