Like many people, when I first discovered the Fibonacci sequence, I was immediately enamored. It has some wonderful properties, some of which I will discuss below. But first, we need to beware of the large amount of Golden Garbage and Fibonacci Flim-Flam that pervades the internet.
A few years back, I ran across this excellent article by Donald Simanek where he meticulously takes apart many of the more popular myths associated with the Fibonacci numbers and the Golden Ratio. If you have not read it, go read it now! The link is
here. I highly recommend it! More recently, Keith Devlin made a video where he stomped out much of the pseudoscientific nonsense going around about the Golden Ratio. I have embedded the video below as it is well worth the watch.
Debunking 10 Golden Ratio Myths from
Keith Devlin on
Vimeo.
What really irritates me the most about all this--as well as Simanek and Devlin--is that the Golden Ratio really is a special number with some wonderful and beautiful properties. The nonsense is completely unnecessary. Anyway, now that we've visited the debunking, let's talk about some Fibonacci and Golden Ratio facts that I really like.
Some interesting facts about Fibonacci-like sequences
As Dr. Devlin pointed out in his video, it has been known for a long time that the ratio of consecutive Fibonacci numbers is the golden ratio Φ. There are many ways to show this. Here's one that I came up.
Let γ
n = F
n/F
n-1 be some ratio of consecutive Fibonacci numbers. Then γ
n+1 = F
n+1/F
n = (F
n+F
n-1)/F
n = 1+F
n-1/F
n = 1+1/γ
n. We can verify that γ
2 = F
2/F
1 = 1/1 and γ
3 = F
3/F
2 = 2/1 = 2 = 1+1/1 = 1+1/γ
2. Now assume as an inductive hypothesis that γ
n can be represented by the continued fraction
1+1/(
1+...+1/(
1+
1/
1) with n red
1's. Then γ
n+1 = 1+1/γ
n =
1+1/(
1+1/(
1+...+1/(
1+
1/
1)) which is the continued fraction with n+1 red
1's. Hence as n --> ∞, γ
n --> 1+1/(1+1/(1+1/(1+...) = Φ. This identity can be verified since Φ is the positive root of the quadratic equation x=1+1/x. (The negative root of this quadratic, sometimes referred to as its algebraic conjugate is Ψ = -1/Φ. More on Ψ later).
 |
| Φ as a continued fraction |
As an interesting side note, the fact that Φ can be represented by the infinite continued fraction of all 1's, is why it is considered to be the "most irrational number." So is Φ the most irrational number? (In my best Keith Devlin voice) That's
TRUE!
 |
| Leonardo of Pisa originally described the Fibonacci sequence |
Several years back, I was playing around with Fibonacci-like sequences--sequences with the same recursion relation as the Fibonacci sequence, but with a different starting point. I began to wonder how many of the Fibonacci-like sequences also had the property that the ratio of consecutive elements tended towards Φ. If one were to allow non-integer seeds, then it is apparent that if γ
1 = Φ, then γ
n = Φ for all n, and likewise for γ
1 = Ψ. This is true since both Φ and Ψ are roots to the quadratic x=1+1/x. But which other sequences go to Φ and which to Ψ? Does it go to whichever limit is closer to γ
1? Do most go Φ but those close enough to Ψ go to Ψ? Or is it something different? At the time, I conjectured that with the exception of the two above where γ
n doesn't vary with n, all Fibonacci-like sequences tended towards Φ. Unfortunately, I did not have the mathematical tools back then to prove it. I was determined to figure it out on my own though (what's the point of doing a puzzle if you just look up the answer without solving it yourself?).
Recently I was reminded of my old puzzle and finally worked out a proof. I'll just give you the gist of it without going into the details. Basically, I worked out a formula for the difference between γ
n and Φ (provided that γ
1 > 0). Then using some known inequalities involving the Fibonacci numbers, I was able to show that for any given ε > 0, there is an N s.t. for all n > N, |γ
n-Φ| < ε. Thus for any γ
1 > 0, the sequence of ratios tends towards Φ. Suppose now that γ
1 < -1. Then γ
2 = 1+1/γ
1 > 0 and the sequence tends towards Φ. And if γ
1 > -½, then γ
2 < -1 and the sequence tends towards Φ. If we continue in this vein, we find that if γ
1 < -1/F
2n or > -1/F
2n-1 for some n, then the sequence tends towards Φ. In other words, the set of initial ratios that spawn a sequence that tends towards Φ is
R\{Ψ}.
This is pretty amazing. It means that no matter how close to Ψ the ratio γ
1 is (just as long as it's not equal), there is some finite n for which γ
n is even closer to Φ. This naturally led me to wonder why and keep playing around. I guess there are many ways to explain this, but here's the one I came up with. Let's consider the Fibonacci sequence in reverse. We are used to thinking about the Fibonacci sequence as beginning with 1, 1 and moving forward following the recursion relation F
n+1 = F
n-1 + F
n. However, there is no reason why we can't follow the sequence backwards using the equivalent relation F
n-1 = F
n+1 - F
n. If we do this we get that F
0 = 0, F
-1 = 1, F
-2 = -1, F
-3 = 2, F
-4 = -3, ... , F
-n = (-1)
n+1F
n. Now consider what happens to F
n+1/F
n as n --> -∞. This is equivalent to looking at the limit as n --> ∞ of F
(-n)+1/F
-n = F
-(n-1)/F
-n = -(F
n-1/F
n) = -1/Φ = Ψ. Furthermore, using essentially the same proof as above, we can show that with the exception of the two sequences whose ratio doesn't vary, this happens for every Fibonacci-like sequence. So of course they all tend towards Φ no matter how close to Ψ we begin; looking at it this way, arbitrarily close to Ψ is where they all ultimately "originate." This at once made the original conjecture seem a little less amazing, while simultaneously being much more astounding (I can't think of a better way of explaining my emotions). When I realized this result, I pictured in my mind a graph of all the sequences as something akin to the magnetic field lines of a bar magnet with Φ and Ψ as the fixed poles. Quite lovely!
I showed my work to a Number Theorist here at the Math Department where I go, and after a few days he came back to me with three alternative ways to prove this. I will show you my favorite below which involves a linear equation. It is known that for Fibonacci-like sequences, the n
th term can be expressed as
Fn =
aΦ
n +
bΨ
n where
a and
b are constants defined by the starting points of the Fibonacci-like sequence. For example, for the actual Fibonacci sequence
a = 1/√5 and
b = -1/√5 , for the Lucas sequence (which begins with 1, 3)
a =
b = 1 , for the Φ sequence
b = 0, and
a = 0 for the Ψ sequence. Consider, for
a,
b ≠ 0, what happens to
Fn+1/
Fn as n --> ∞. Note that |Ψ| < 0 and so the second term disappears in the limit while the
a's in the numerator and denominator cancel leaving the limit as Φ. Now consider, for
a,
b ≠ 0, what happens as n --> -∞. We have
Fn =
a/Φ
n+
b/Ψ
n, so the opposite happens and we're left with a limit of Ψ.
Beautiful!
Musings on a variation of 2048
In case you've been living under a rock and haven't heard of the game 2048,
go check it out now. (
WARNING: Game is highly addictive!) It's a fun little game. The basic idea is that you move tiles around on a 4X4 board. The starting position consists of two tiles randomly placed on the board, valued either 2 or 4 (randomly chosen). On each move you move all tiles on the board either left, right, up or down provided they have room to move. If two tiles of the same value are pushed together, they merge into a single tile with double the value of the original tiles. On each move a single tile, either a 2 or 4, is randomly placed on an open space. The game end when you run out of room to play. You WIN if you create the 2048 tile, although you may continue to play to see how high you can go.
 |
| Binary Exponential |
One of the attributes of the game is that it's fairly easy at first. In fact, it's fairly easy for a while. You think that you're doing so well then, seemingly suddenly, the world caves in on you. This is due to the exponential nature of the game. Each level is "as big" as all the levels before it. For example, in order to make the 512 tile, you must first make two 256 tiles. In other words, once you reach the 256 tile, to get to the next level, you have to do everything that you've already done over again to make a second 256 tile, but with less room to work with (since you didn't have that first 256 tile taking up space the first time around). Of course it's actually a little messier than that. On the first go there were 14 empty spots to work with; It is quite unusual to clear the board that efficiently when creating the higher valued tiles. Naturally, many of the tiles cluttering the playing board at this time can be used to make the 256 tile, so it's not quite as dire as that. Bear in mind that at each level, the maximum number of free spaces is reduced by one. So (for simplicity, let's ignore the fact that the game sometimes gives 4's and pretend that it always deals a 2) to make the 2048 tile, you must first make two 1024 tiles. But to make that second 1024 tile, you must first make two 512 tiles. But to make the second 512 tile, you must first make two 256 tiles, etc. Therefore, while constructing the 2048 tile, you
must pass through a position where the playing board only has 16 - 11 = 5 free spaces to work with (because 2048 = 2
11). There is no escaping this since making duplicate tiles in parallel rather than in series leaves you with
less free spaces to work with. And
getting the 4096 tile is even harder yet. Knowing what I know about the exponential nature of the game and how long it took me to get good enough to finally make that tile, I'm not too optimistic about being able to make the 8192 tile. Although if I stop and carefully plan out each move rather than use the heuristic algorithm that has been this successful so far, who knows? What I do know is that 2048 has been a real time hoover and I sure hope I'm getting over it soon.
The game's popularity has spawned several variants. There is
the pi variant. If you, like me, enjoy British sci-fi, then
the Doctor Who variant is for you. The last two aren't "true" variants as the only difference is what's on the tiles; the next two are quite clever. If you're in the mood for a good laugh, I recommend
the Numberwang! variant. (Note: If you are unfamiliar with the show
That Mitchell and Webb Look, then watch the video below or else that variant won't make any sense.)
My favorite though, has to be
the Fibonacci variant (
via). The one thing that I don't like about that particular version of the variant is that it stops play after achieving the 2584 tile. Perhaps one of the other versions available are more like
the app I have on my Android and let you keep playing (although that one might stop after the 6765 tile--not that I could do much better--although I have made the 4181 tile a handful of times). Anyhow, allow me to rewind a bit and relate a story.
I first became aware of 2048 when I saw
this xkcd cartoon which I didn't understand at the time (late to the game, as usual). I soon became hooked and when I saw that the
Garden State Mathematics Conference was looking for speakers, I thought that perhaps all this play wasn't a complete waste of time after all. I prepared an outline and abstract for the talk and submitted it and was approved. Then, a couple of days before my talk, I discovered the Fibonacci variant. That changed everything. How could I not make half my talk about that? So I did.
There are some key differences between the games. For one, instead of merging like numbers to get double, you merge consecutive Fibonacci numbers to get the next Fibonacci number. Except for 1, like tiles don't mesh, but each tile does have two different values that it can merge with. One needs to be a little more careful here. For example, if you're trying to merge a 13 with a 21 to get 34, you could accidentally bump into an 8 and get stuck with a pair of 21's. But don't fret it; not all is lost. If you make another 13 then hit the two 21's in sequence, you'll make a 55. Another thing to be note is that making the F
18 tile takes about the same amount of room as making the 2
11 tile does in regular 2048. (
see figures below)
 |
| Set-up for the win in 2048 |
 |
| Similar situation for 2584 |
As you can see, in the Fibonacci variant, each F
n is not adjacent to the F
n-1 and F
n+1 tiles but rather to the F
n-2 and F
n+2 tiles. Also, Unlike regular 2048, for each level you don't need to repeat everything you've done, but merely to the level below. Hence the game's increase in difficulty is not as fast as the binary exponential growth of regular 2048. However, it is exponential. Can you guess what the base is? (
hint: Φ)
I should note here that since I figured all this out the day before my presentation, I made a mistake. I incorrectly reasoned that since the ratio of the number of levels needed to reach each level was n(n-1)/n, that the game's difficulty would approach 2
n in the limit. This didn't quite sit right with me and when I realized that that last level is the "biggest" of the levels, I recalculated to get the result below. I will be giving the same talk again in a week or two and the mistake has been corrected.
There are many to show that it approaches Φ in the limit including continued fractions (which I did). There is also a simpler way to look at it. Since the game gives you nothing but 1's (F
1 = F
2 = 1, unlike in regular 2048 where 2
1 = 2 ≠ 2
2 = 4), every tile is built up from 1 tiles in the quantity of the face value of the tile in question. In other words, each level's "size" is equal to its value. So the increase in the difficulty of achieving each level relative to the previous level is just the ratio of consecutive Fibonacci numbers, which we've already shown is Φ. There you have it: the difficulty of each level of the Fibonacci variant of 2048 basically increases exponentially in Φ.
WONDERFUL!
