The celebrated Fibonacci Sequence is defined by setting each term equal to the sum of the two previous terms, starting at \(F_0=0\) and \(F_1=1\). So it continues like this:
What’s the relation to last week‘s infinite jump sequence,
Let’s find out!
Recall from last week that we can group our sequence into blocks of \(A=(ab)\) and \(B=(abb)\), and that the pattern of “short” and “long” blocks is the same as the pattern of as and bs in the original sequence:
This means we can do this grouping again! Specifically, we can group our sequence into “blocks of blocks”, or level 2 blocks, that look like \(A_2=[(ab)(abb)]\) and \(B_2=[(ab)(abb)(abb)]\):
Furthermore, the pattern of short and long level 2 blocks is still the same as the original jump sequence! So we can keep going, grouping our sequence into level 3 blocks \(A_3=A_2 B_2\) and \(B_3=A_2 B_2 B_2\), level 4 blocks \(A_4=A_3 B_3\) and \(B_4=A_3 B_3 B_3\), and so on, thus finding longer and longer patterns that fill up our sequence. Here’s level 3:
One natural question is: what are the lengths of these blocks? Let’s make a table:
| n | An | Bn | An Length | Bn Length |
|---|---|---|---|---|
| 0 | a | b | 1 | 1 |
| 1 | ab | abb | 2 | 3 |
| 2 | ababb | ababbabb | 5 | 8 |
| 3 | ababbababbabb | ababbababbabbababbabb | 13 | 21 |
The lengths are exactly the Fibonacci numbers! (Prove this!) Furthermore, how many as and bs does each block have? Here’s another table:
| n | An | # of as | # of bs | Bn | # of as | # of bs |
|---|---|---|---|---|---|---|
| 0 | a | 1 | 0 | b | 0 | 1 |
| 1 | ab | 1 | 1 | abb | 1 | 2 |
| 2 | ababb | 2 | 3 | ababbabb | 3 | 5 |
| 3 | ababbababbabb | 5 | 8 | ababbababbabbababbabb | 8 | 13 |
Again the Fibonacci numbers! This gives us another way to compute the ratio of as to bs in the jump sequence: The ratios of bs to as in blocks An and Bn are \(F_{2n}/F_{2n-1}\) and \(F_{2n+1}/F_{2n}\) respectively, so as n gets larger these ratios should both approach last week’s answer, the golden ratio \(\phi\).
OK, so our jump sequence is very “Fibonacci”y: it has blocks of Fibonacci lengths with Fibonacci proportions of as and bs. How can it get any “Fibonacci”er than that? Here’s how: Define a different infinite string using the same definition as the Fibonacci numbers themselves: write \(W_0=0\), \(W_1=1\), and after that, each string is formed by writing the previous two next to each other: \(W_n=W_{n-1}W_{n-2}\). The Ws continue like this:
and in the limit they define some infinite string of 0s and 1s that, without a doubt, is as “Fibonacci”y as it gets. But wait; except for the first digit, this is exactly the same as our jump sequence with 0=a and 1=b!
- 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1 1 ... This truly is the Fibonacci numbers reincarnated in a binary string.
a b a b b a b a b b a b b a b a b b a b a b b a b b a b a b b a b b ...