If you are anything like me, and I hope for your sake that you aren’t, then you will often ask yourselves questions such as:
Late at night, when they’re peckish, do Vampires ever bite themselves?
Was Hitler’s moustache homage to Charlie Chaplin?
Can I find an exact formula for the Fibonacci sequence?
I can only answer one question. Which one?
Yup, it’s the last one.
In Yoak: Miles, Kilometers and Fibonacci Numbers Jeff showed a lot of fun stuff about the Fibonacci sequence and how it relates to the golden ratio. He didn’t explain how this comes about.
The Golden Ratio, phi (I’ll use g), was beloved by classical architects and is still loved today. It was thought to be the most aesthetically pleasing ratio. It was the ratio used for the Parthenon.
It has a simple definition, if you have a rectangle with proportions 1:g then you can remove a square from one end and the leftover is a rectangle with the same proportions.
From that you can work out that g2 = g + 1 and g = 1 + 1/g. There is a revealing symmetry in that last equation which is better shown by g – 1/g = 1, if you switch the sign and invert g then you get another solution.
Anyway:
g = (sqrt(5) + 1)/2 ~= 1.618
1/g= (sqrt(5) – 1)/2 ~= 0.618
The Fibonacci sequence goes 1, 1, 2, 3, 5, 8, 13, 21, 34 …
The Fibonacci rule is Fn+2 = Fn+1 + Fn
There are lots of sequences that fit this rule. Any particular sequence is fixed by specifying two elements, for example the actual Fibonacci sequence starts 1, 1. Another sequence that fits the rule is 1, 3, 4, 7, 11, 18, 29 …
We note that if xn+2 = xn+1 + xn then the sequence 1, x, x2, x3, x4 … satisfies the Fibonacci rule.
We can solve for x. Dividing by xn and rearranging gives x2 – x – 1 = 0.
This gives two solutions for x:
g = (1+sqrt(5))/2
(-1/g) = (1-g) = (1-sqrt(5))/2
Both of these solutions for x generate sequences that satisfy the Fibonacci rule.
1, g, g2, g3 …
1, (1-g), (1-g)2, (1-g)3 …
But we can go further. Put Xn = Agn + B(1-g)n then Xn satisfies the Fibonacci rule.
A + B, Ag + B(1-g), Ag2 + B(1-g)2, Ag3 + B(1-g)3 …
A particular sequence that satisfies the Fibonacci rule is fixed by just two entries. I claim that we can always find values for A and B that will create any sequence which satisfies the Fibonacci rule.
We have two simultaneous equations with two unknowns, A and B. This always gives a unique solution (it matters that (1, g) and (1, 1-g) are linearly independent vectors). For example lets calculate A and B for the actual Fibonacci sequence. F1 =1 and F2 = 1. Using the Fibonacci rule backwards gives F0 = 0.
So F0 = A + B = 0 F1 = Ag + B(1-g) = 1
Working this through
B = -A
Ag – A(1-g) = 1
A(2g -1) = 1
A(2(sqrt(5) + 1)/2 -1) = 1
A = 1/sqrt(5)
Which solves to give A = 1/sqrt(5), B = -1/sqrt(5)
So we have : Fn = (gn – (1-g)n) /sqrt(5)
Now there is something very bizarre going on here. We know that the Fibonacci sequence is a sequence of integers. We have found that it has an exact formula but the formula involves lots of irrational numbers, raising them to powers, adding and dividing them. Somehow this process always ends up with an integer. Knowing that we will always get an integer we can short-circuit the calculation.
Note that 1/ sqrt(5) is about 0.447, (1-g)/ sqrt(5) is about -0.276 and that (1-g)n/ sqrt(5) always has a magnitude of less than a half. Knowing that we will always get an integer we can just ignore this term and round to the nearest integer.
Fn = round(gn /sqrt(5)) for n >= 0
It is also true that
F-n = (-1)n+1round(gn /sqrt(5)) for n >= 0
To see this remember that 1-g = -1/g so Fn = (gn – (-1/g)n) /sqrt(5). For negative n it is the first term that is smaller than a half and can be ignored. I’ll let you work out the rest.
In fact extending the Fibonacci sequence backwards gives … -3, 2, -1, 1, 0, 1, 1, 2, 3 …
What is most wonderful about this is that the ratio between successive members of the Fibonacci sequence is about g. It becomes very close very quickly. Also wonderful is that this technique extends to other sequences which are defined by similar rules. In general you can find an exact formula, involving taking powers of irrational numbers, which will always give you the integer you were looking for.
I find that quite amazing!
It shows that you cannot take one part of mathematics in isolation, if you want to understand integers you have to understand irrational numbers, and for many sequences complex numbers. It’s all interconnected, you can’t pick and choose. Even the simplest parts of mathematics are tied up in the most complex!
All good fun though!
Martin Gardner died this week.
The Math Factor in iTunes
RSS feed
Comments RSS
mathbun.com