5 ms·

This started out taking baby steps, then took a huge leap in complexity right here: Since the Fibonacci numbers are defined by a linear recurrence, we can expr

This started out taking baby steps, then took a huge leap in complexity right here: Since the Fibonacci numbers are defined by a linear recurrence, we can express the recurrence as a matrix, and it’s easy to verify that... It's been way too long since my math minor for me to understand that.

robinhouston 15y ago
Sorry. I think it’s only the jargon that’s confusing you. As long as you can remember (or look up) the definition of matrix multiplication, then it genuinely is easy to verify. [ fib(n-1) fib(n) ] x [0 1] [ fib(n) fib(n+1) ] [1 1] = [ fib(n) fib(n-1)+fib(n) ] [ fib(n+1) fib(n)+fib(n+1) ] = [ fib(n) fib(n+1) ] [ fib(n+1) fib(n+2) ]