A Fibonacci word is a specific sequence of binary digits. 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 languageLconsisting 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 be "0" and be "01". Now . The infinite Fibonacci word is the limit, that is, the infinite sequence that contains each, for finite, as a prefix. Enumerating items from the above definition produces: 0 01 010 01001 01001010 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,...
Another way of going from Sn to Sn + 1 is to replace each symbol 0 in Sn with the pair of consecutive symbols 0, 1 in Sn + 1, and to replace each symbol 1 in Sn with the single symbol 0 in Sn + 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 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 nth digit of the word is where is the golden ratio and is the floor function.
Discussion
The word is related to the famous sequence of the same name in the sense that addition of integers in the inductive definition is replaced with string concatenation. This causes the length of Sn to be Fn + 2, the th Fibonacci number. Also the number of 1s in Sn is Fn and the number of 0s in Sn is Fn + 1.
Other properties
The infinite Fibonacci word is not periodic and not ultimately periodic.
The last two letters of a Fibonacci word are alternately "01" and "10".
Suppressing the last two letters of a Fibonacci word, or prefixing the complement of the last two letters, creates a palindrome. Example: 01 = 0101001010 is a palindrome. The palindromic density of the infinite Fibonacci word is thus 1/φ, where φ is the Golden ratio: this is the largest possible value for aperiodic words.
In the infinite Fibonacci word, the ratio / is φ, as is the ratio of zeroes to ones.
The infinite Fibonacci word is a balanced sequence: Take two factors of the same length anywhere in the Fibonacci word. The difference between their Hamming weights never exceeds 1.
The subwords 11 and 000 never occur.
The complexity function of the infinite Fibonacci word is n+1: it contains n+1 distinct subwords of length n. Example: There are 4 distinct subwords of length 3 : "001", "010", "100" and "101". Being also non-periodic, it is then of "minimal complexity", and hence a Sturmian word, with slope. The infinite Fibonacci word is the standard word generated by the directive sequence.
The infinite Fibonacci word is recurrent; that is, every subword occurs infinitely often.
If is a subword of the infinite Fibonacci word, then so is its reversal, denoted.
If is a subword of the infinite Fibonacci word, then the least period of is a Fibonacci number.
The concatenation of two successive Fibonacci words is "almost commutative". and differ only by their last two letters.
The number 0.010010100..., whose decimals are built with the digits of the infinite Fibonacci word, is transcendental.
The letters "1" can be found at the positions given by the successive values of the Upper Wythoff sequence :
The letters "0" can be found at the positions given by the successive values of the Lower Wythoff sequence :
The distribution of points on the unit circle, placed consecutively clockwise by the golden angle, generates a pattern of two lengths on the unit circle. Although the above generating process of the Fibonacci word does not correspond directly to the successive division of circle segments, this pattern is if the pattern starts at the point nearest to the first point in clockwise direction, whereupon 0 corresponds to the long distance and 1 to the short distance.
The infinite Fibonacci word contains repetitions of 3 successive identical subwords, but none of 4. The critical exponent for the infinite Fibonacci word is. It is the smallest index among all Sturmian words.
The infinite Fibonacci word is often cited as the worst case for algorithms detecting repetitions in a string.
The infinite Fibonacci word is a morphic word, generated in * by the endomorphism 0 → 01, 1 → 0.
The th element of a Fibonacci word,, is 1 if the Zeckendorf representation of includes a 1, and 0 if it does not include a 1.
Applications
Fibonacci based constructions are currently used to model physical systems with aperiodic order such as quasicrystals. Crystal growth techniques have been used to grow Fibonacci layered crystals and study their light scattering properties.
