| I'm not a math expert, but I like trying to follow these proofs as a puzzle. Here's my handwavy, intuitive take: 1) Setup a matrix to advance fibonacci numbers Define a matrix A so that A times (Fib1, Fib2) = (Fib2, Fib3) That is, A "advances" the Fibonacci relationship when you put two numbers in (Fib1, Fib2 and Fib3 are also multiplied by the appropriate power of 10 to make them at the right decimal place). You can see this when we multiply it out: A * (Fib1, Fib2) = (Fib2, Fib1 + Fib2) = (Fib2, Fib3) Since Fib1 + Fib2 = Fib3 [again, at the right power of 10; writing all the 10^(i+1) bookkeeping obscures the reasoning IMO). 2) Define the sequence we want We really want the sequence Fib1 + Fib2 + Fib3, where each Fib number is advanced the appropriate number of decimals above. We can do (.01, .001) [starting with the first numbers 1 and 1 in the right spots: .01 and .001, with .0002 coming next). This means we take (.01, .001) and use itself (multiply by identity matrix I), then take (.01, .001) and advance it once (multiply by A), then take (.01, .001) and advance it 2 steps (multiply by A^2) and so on: Initial * Identity + Initial * A + Initial * A^2 + ... (I + A + A^2) * Initial = (Fib1 + Fib2 + Fib3 + ..., Fib2 + Fib3 + Fib4...) We only want the first element of this result: the sequence starting at Fib1. 3) Rewrite the sequence I + A + A^2 looks like a geometric series which (handwavy) has the same properties as regular series: 1 + r + r^2 ... = (1-r)^-1 so the series can be rewritten as (I - A)^-1 If we do the appropriate calculations, we get I - A = (1 0, 0 1) - (0 1, .01 .1) = (1 -1, -.01, .9) which we can invert to get 1/(.9 - .99) * (.9 1,.01 1) = 1/(89/100) * (.9 1,.01 1) = 1/89 * (90 100, 1 100) This last matrix is the SUM of doing all the operations: I + A + A^2 + A^3, etc. We seed it with the first two fibonacci numbers, in the positions we want: (.01, .001) and off it goes! 1/89 * (90 100, 1 100) * (.01, .001) = (1/89, 11/89) We only want the the first element (1/89) which is the sequence starting Fib1 + Fib2 + Fib3... Phew. There's probably some typos in there, but that's how I intuitively understood their argument. It helped to actually work through the matrix math to see what was happening. |