Decimal expansion of 1/89 is Fibonacci sequence added together in a simple way.(geom.uiuc.edu)
geom.uiuc.edu
Decimal expansion of 1/89 is Fibonacci sequence added together in a simple way.
http://www.geom.uiuc.edu/~rminer/1over89/
6 comments
I'm embarrassed to say that I have a degree in math but don't really follow the given proof. Can anyone explain it?
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.
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.
[deleted]
What step gave you trouble? Other than the typo in the first equation (F_n should be F_(i-1)).
Also works with 1/9899 in base 100.
And in base b, it's 1/( b (b-1) -1 ).
Yes. I was too lazy to type that. :o) Anyway, it also works with polynomials (and even better there):
x / (1-x-x^2) = 0 + x + x^2 + 2 x^2 + 3 x^3 + 5 x^4 + ...
(FYI: Look up "Generating Functions" in "Concrete Math" or on the Web. A lot of operations on sequences e.g. adding them, multiplying by a scalar, convoluting them, splicing, taking every n-th element, can be done efficiently and elegantly on their generating function.)
http://en.wikipedia.org/wiki/Fibonacci_number#Power_series
x / (1-x-x^2) = 0 + x + x^2 + 2 x^2 + 3 x^3 + 5 x^4 + ...
(FYI: Look up "Generating Functions" in "Concrete Math" or on the Web. A lot of operations on sequences e.g. adding them, multiplying by a scalar, convoluting them, splicing, taking every n-th element, can be done efficiently and elegantly on their generating function.)
http://en.wikipedia.org/wiki/Fibonacci_number#Power_series
I don't understand why this is interesting. Would adding any other infinite series using that same "fashion" not result in a sum which converges to some number? why is 1/89 special? Is it that the reciprocal of the infinite decimal expansion is an int?
Basically, yes. But 1/89 is a nifty example.
It's a pity that they totally ruin their proof with an incorrect statement of the thing being proved. But start with a correct statement and it's a 5 minute job to prove this using basic arithmetic.
I'd type up the proof but typing math on the iPhone is impossible.
I'd type up the proof but typing math on the iPhone is impossible.
[deleted](1)
[deleted](1)