Fibonacci word
Encyclopedia
Binary numeral system
The binary numeral system, or base-2 number system, represents numeric values using two symbols, 0 and 1. More specifically, the usual base-2 system is a positional notation with a radix of 2...
digits (or symbols from any two-letter alphabet
Alphabet
An alphabet is a standard set of letters—basic written symbols or graphemes—each of which represents a phoneme in a spoken language, either as it exists now or as it was in the past. There are other systems, such as logographies, in which each character represents a word, morpheme, or semantic...
). The Fibonacci word is formed by repeated concatenation
Concatenation
In computer programming, string concatenation is the operation of joining two character strings end-to-end. For example, the strings "snow" and "ball" may be concatenated to give "snowball"...
in the same way that the Fibonacci number
Fibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
s are formed by repeated addition.
It is a paradigmatic example of a Sturmian word
Sturmian word
In mathematics, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite word.- Definition :A word is a infinite sequence of symbols drawn from a finite alphabet. Call any finite contiguous subsequence of a word a factor...
.
The name “Fibonacci word” has also been used to refer to the members of a formal language
Formal language
A formal language is a set of words—that is, finite strings of letters, symbols, or tokens that are defined in the language. The set from which these letters are taken is the alphabet over which the language is defined. A formal language is often defined by means of a formal grammar...
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
be "0" and 
be "01". Now 
(the concatenation of the previous sequence and the one before that).The infinite Fibonacci word is the limit
.The Fibonacci words
We have:
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, ...
Closed-form expression for individual digits
The nth digit of the word is
where 
is the golden ratioGolden ratio
In mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...
and
is the floor functionFloor function
In mathematics and computer science, the floor and ceiling functions map a real number to the largest previous or the smallest following integer, respectively...
.
Substitution rules
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
- 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 0's for 1's and shifting the positions by one.
Discussion
The word is related to the famous sequence of the same name (the Fibonacci sequenceFibonacci number
In mathematics, the Fibonacci numbers are the numbers in the following integer sequence:0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\; ....
) 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 (n + 2)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 palindromePalindromeA palindrome is a word, phrase, number, or other sequence of units that can be read the same way in either direction, with general allowances for adjustments to punctuation and word dividers....
. Example: 01
= 0101001010 is a palindrome. - In the infinite Fibonacci word, the ratio (number of letters)/(number of zeroes) is
, the golden ratioGolden ratioIn mathematics and the arts, two quantities are in the golden ratio if the ratio of the sum of the quantities to the larger quantity is equal to the ratio of the larger quantity to the smaller one. The golden ratio is an irrational mathematical constant, approximately 1.61803398874989...
, as is the ratio of zeroes to ones. - The infinite Fibonacci word is "balanced": Take two factorsSubstringA subsequence, substring, prefix or suffix of a string is a subset of the symbols in a string, where the order of the elements is preserved...
of the same length anywhere in the Fibonacci word. The difference between the number of "0" in any of them and the number of "0" in the other one never exceeds 1. - The subwords 11 and 000 never occur.
- The complexity functionComplexity functionIn computer science, the complexity function of a string, a finite or infinite sequence u of letters from some alphabet, is the function of a positive integer n that counts the number of different substrings of n consecutive elements from the string u.A Sturmian word is one of minimal...
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 wordSturmian wordIn mathematics, a Sturmian word, named after Jacques Charles François Sturm, is a certain kind of infinite word.- Definition :A word is a infinite sequence of symbols drawn from a finite alphabet. Call any finite contiguous subsequence of a word a factor...
, with slope
. The infinite Fibonacci word is the standard word generated by the directive sequence (1,1,1,....). - 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. - As a consequence, the infinite Fibonacci word can be characterized by a cutting sequence of a line of slope
or 
. See figure above. - The number 0.010010100..., whose decimals are built with the digits of the infinite Fibonacci word, is transcendentalTranscendental numberIn mathematics, a transcendental number is a number that is not algebraic—that is, it is not a root of a non-constant polynomial equation with rational coefficients. The most prominent examples of transcendental numbers are π and e...
. - The letters "1" can be found at the positions given by the successive values of the Upper Wythoff sequence (OEIS A001950):
- The letters "0" can be found at the positions given by the successive values of the Lower Wythoff sequence (OEIS A000201):
- The infinite Fibonacci word can contain repetitions of 3 successive identical subwords, but never 4. The infinite Fibonacci word contains at most
repetitions. It is the smallest index (or critical exponent) among all Sturmian words. - The infinite Fibonacci word is often cited as the worst caseWorst CaseWorst Case is the 3rd book in the Michael Bennett series from James Patterson and Michael Ledwidge.-Plot summary:NYPD Detective Mike Bennett and his new partner FBI Special Agent Emily Parker are on the trail of Francis Mooney, a Manhattan trusts and estates lawyer with terminal lung cancer...
for algorithms detecting repetitions in a string.
Applications
Modern Crystal growth techniques have been used by Merlin et al., and Dharma-wardana et al., to grow one-dimensional Fibonacci crystals, and study their light scattering properties.External links
- A detailed and accessible description, on Ron Knott's site
- Repetitions in the infinite Fibonacci word, by Mignosi and Pirillo
- Sequence The Fibonacci word in the On-Line Encyclopedia of Integer SequencesOn-Line Encyclopedia of Integer SequencesThe On-Line Encyclopedia of Integer Sequences , also cited simply as Sloane's, is an online database of integer sequences, created and maintained by N. J. A. Sloane, a researcher at AT&T Labs...
- The Rabbit sequence on Mathworld