Binary sequence from Fibonacci recurrence
A Fibonacci word is a specific sequence of binary digits (or symbols from any two-letter alphabet). The Fibonacci word is formed by repeated concatenation in the same way that the Fibonacci numbers are formed by repeated addition.
It is a paradigmatic example of a Sturmian word and specifically, a morphic word.
The name "Fibonacci word" has also been used to refer to the members of a formal language "L" consisting of strings of zeros and ones with no two repeated ones. Any prefix of the specific Fibonacci word belongs to "L", but so do many other strings. "L" has a Fibonacci number of members of each possible length.
Definition.
Let formula_1 be "0" and formula_2 be "01". Now formula_3 (the concatenation of the previous sequence and the one before that).
The infinite Fibonacci word is the limit formula_4, that is, the (unique) infinite sequence that contains each formula_5, for finite formula_6, as a prefix.
Enumerating items from the above definition produces:
 formula_1    0
 formula_2    01
 formula_9    010
 formula_10    01001
 formula_11    01001010
 formula_12    0100101001001
The first few elements of the infinite Fibonacci word are:
0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, ... (sequence in the OEIS)
Closed-form expression for individual digits.
The "n"th digit of the word is formula_13 where formula_14 is the golden ratio and formula_15 is the floor function (sequence in the OEIS). As a consequence, the infinite Fibonacci word can be characterized by a cutting sequence of a line of slope formula_16 or formula_17. See the figure above.
Substitution rules.
Another way of going from "S""n" to "S""n"&amp;hairsp;+1 is to replace each symbol 0 in "S""n" with the pair of consecutive symbols 0, 1 in "S""n"&amp;hairsp;+1, and to replace each symbol 1 in "S""n" with the single symbol 0 in "S""n"&amp;hairsp;+1.
Alternatively, one can imagine directly generating the entire infinite Fibonacci word by the following process: start with a cursor pointing to the single digit 0. Then, at each step, if the cursor is pointing to a 0, append 1, 0 to the end of the word, and if the cursor is pointing to a 1, append 0 to the end of the word. In either case, complete the step by moving the cursor one position to the right.
A similar infinite word, sometimes called the rabbit sequence, is generated by a similar infinite process with a different replacement rule: whenever the cursor is pointing to a 0, append 1, and whenever the cursor is pointing to a 1, append 0, 1. The resulting sequence begins
0, 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, ...
However this sequence differs from the Fibonacci word only trivially, by swapping 0s for 1s and shifting the positions by one.
A closed form expression for the so-called rabbit sequence:
The "n"th digit of the word is formula_18
Discussion.
The word is related to the famous sequence of the same name (the Fibonacci sequence) in the sense that addition of integers in the inductive definition is replaced with string concatenation. This causes the length of "S""n" to be "F""n"&amp;hairsp;+2, the ("n"&amp;hairsp;+2)nd Fibonacci number. Also the number of 1s in "S""n" is "F""n" and the number of 0s in "S""n" is "F""n"&amp;hairsp;+1.
Applications.
Fibonacci based constructions are currently used to model physical systems with aperiodic order such as quasicrystals, and in this context the Fibonacci word is also called the Fibonacci quasicrystal. Crystal growth techniques have been used to grow Fibonacci layered crystals and study their light scattering properties.
Notes.
 ;templatestyles src="Reflist/styles.css" / ;