![Fibonacci word cutting sequence](https://upload.wikimedia.org/wikipedia/commons/2/2d/Fibonacci_word_cutting_sequence.png)
A Fibonacci word is a specific sequence of
binary
Binary may refer to:
Science and technology Mathematics
* Binary number, a representation of numbers using only two digits (0 and 1)
* Binary function, a function that takes two arguments
* Binary operation, a mathematical operation that t ...
digits (or symbols from any two-letter
alphabet
An alphabet is a standardized set of basic written graphemes (called letters) that represent the phonemes of certain spoken languages. Not all writing systems represent language in this way; in a syllabary, each character represents a syll ...
). The Fibonacci word is formed by repeated
concatenation
In formal language, formal language theory and computer programming, string concatenation is the operation of joining character string (computer science), character strings wikt:end-to-end, end-to-end. For example, the concatenation of "sno ...
in the same way that the
Fibonacci number
In mathematics, the Fibonacci numbers, commonly denoted , form a sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start the sequence from ...
s are formed by repeated addition.
It is a paradigmatic example of a
Sturmian word and specifically, a
morphic word
In mathematics and computer science, a morphic word or substitutive word is an infinite sequence of symbols which is constructed from a particular class of endomorphism of a free monoid.
Every automatic sequence is morphic.
Definition
Let ''f'' ...
.
The name "Fibonacci word" has also been used to refer to the members of a
formal language
In logic, mathematics, computer science, and linguistics, a formal language consists of words whose letters are taken from an alphabet and are well-formed according to a specific set of rules.
The alphabet of a formal language consists of symb ...
''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
, that is, the (unique) 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, ...
Closed-form expression for individual digits
The n
th digit of the word is
where
is the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
and
is the
floor function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
. As a consequence, the infinite Fibonacci word can be characterized by a cutting sequence of a line of slope
or
. See the figure above.
Substitution rules
Another way of going from ''S''
''n'' to ''S''
''n'' + 1 is to replace each symbol 0 in ''S''
''n'' with the pair of consecutive symbols 0, 1 in ''S''
''n'' + 1, and to replace each symbol 1 in ''S''
''n'' with the single symbol 0 in ''S''
''n'' + 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
where
is the
golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
and
is the
floor function
In mathematics and computer science, the floor function is the function that takes as input a real number , and gives as output the greatest integer less than or equal to , denoted or . Similarly, the ceiling function maps to the least int ...
.
Discussion
The word is related to the famous sequence of the same name (the
Fibonacci sequence
In mathematics, the Fibonacci numbers, commonly denoted , form a integer sequence, sequence, the Fibonacci sequence, in which each number is the sum of the two preceding ones. The sequence commonly starts from 0 and 1, although some authors start ...
) in the sense that addition of integers in the
inductive definition
In mathematics and computer science, a recursive definition, or inductive definition, is used to define the elements in a set in terms of other elements in the set ( Aczel 1977:740ff). Some examples of recursively-definable objects include fact ...
is replaced with string concatenation. This causes the length of ''S''
''n'' to be ''F''
''n'' + 2, the (''n'' + 2)th Fibonacci number. Also the number of 1s in ''S''
''n'' is ''F''
''n'' and the number of 0s in ''S''
''n'' is ''F''
''n'' + 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
A palindrome is a word, number, phrase, or other sequence of symbols that reads the same backwards as forwards, such as the words ''madam'' or ''racecar'', the date and time ''11/11/11 11:11,'' and the sentence: "A man, a plan, a canal – Panam ...
. Example: 01
= 0101001010 is a palindrome. The
palindromic density
A palindrome is a word, palindromic number, number, phrase, or other sequence of symbols that reads the same backwards as forwards, such as the words ''madam'' or ''racecar'', the date and time ''11/11/11 11:11,'' and the sentence: "A man, a pla ...
of the infinite Fibonacci word is thus 1/φ, where φ is the
Golden ratio
In mathematics, two quantities are in the golden ratio if their ratio is the same as the ratio of their sum to the larger of the two quantities. Expressed algebraically, for quantities a and b with a > b > 0,
where the Greek letter phi ( ...
: this is the largest possible value for aperiodic words.
* In the infinite Fibonacci word, the ratio (number of letters)/(number of zeroes) is φ, as is the ratio of zeroes to ones.
* The infinite Fibonacci word is a
balanced sequence
In computer science, the complexity function of a ''word'' or '' string'' (a finite or infinite sequence of symbols from some alphabet) is the function that counts the number of distinct ''factors'' (substrings of consecutive symbols) of that strin ...
: Take two
factors
Factor, a Latin word meaning "who/which acts", may refer to:
Commerce
* Factor (agent), a person who acts for, notably a mercantile and colonial agent
* Factor (Scotland), a person or firm managing a Scottish estate
* Factors of production, suc ...
of the same length anywhere in the Fibonacci word. The difference between their
Hamming weight
The Hamming weight of a string is the number of symbols that are different from the zero-symbol of the alphabet used. It is thus equivalent to the Hamming distance from the all-zero string of the same length. For the most typical case, a string o ...
s (the number of occurrences of "1") 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 (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.
* 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
Critical or Critically may refer to:
*Critical, or critical but stable, medical states
**Critical, or intensive care medicine
*Critical juncture, a discontinuous change studied in the social sciences.
*Critical Software, a company specializing in ...
for the infinite Fibonacci word is
. It is the smallest index (or critical exponent) among all Sturmian words.
* The infinite Fibonacci word is often cited as the
worst case
In computer science, best, worst, and average cases of a given algorithm express what the resource usage is ''at least'', ''at most'' and ''on average'', respectively. Usually the resource being considered is running time, i.e. time complexity, b ...
for algorithms detecting repetitions in a string.
* The infinite Fibonacci word is a
morphic word
In mathematics and computer science, a morphic word or substitutive word is an infinite sequence of symbols which is constructed from a particular class of endomorphism of a free monoid.
Every automatic sequence is morphic.
Definition
Let ''f'' ...
, generated in * by the endomorphism 0 → 01, 1 → 0.
* The th element of a Fibonacci word,
, is 1 if the
Zeckendorf representation (the sum of a specific set of Fibonacci numbers) of includes a 1, and 0 if it does not include a 1.
* The digits of the Fibonacci word may be obtained by taking the sequence of
fibbinary number
In mathematics, the fibbinary numbers are the numbers whose binary representation does not contain two consecutive ones. That is, they are sums of distinct and non-consecutive powers of two.
Relation to binary and Fibonacci numbers
The fibbinary ...
s modulo 2.
Applications
Fibonacci based constructions are currently used to model physical systems with aperiodic order such as
quasicrystal
A quasiperiodic crystal, or quasicrystal, is a structure that is ordered but not periodic. A quasicrystalline pattern can continuously fill all available space, but it lacks translational symmetry. While crystals, according to the classical cr ...
s, 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.
See also
*
Mathematics and art
Mathematics and art are related in a variety of ways. Mathematics has itself been described as an art motivated by beauty. Mathematics can be discerned in arts such as music, dance, painting, architecture, sculpture, and textiles. This artic ...
*
Tribonacci word
In mathematics, the Rauzy fractal is a fractal set associated with the Tribonacci substitution
: s(1)=12,\ s(2)=13,\ s(3)=1 \,.
It was studied in 1981 by Gérard Rauzy, with the idea of generalizing the dynamic properties of the Fibonacci mor ...
Notes
References
*.
*.
*.
*.
*.
*.
*. Reprint of the 2002 hardback.
*.
*.
*.
External links
A detailed and accessible description, on Ron Knott's site*
*
{{DEFAULTSORT:Fibonacci Word
Binary sequences
Fibonacci numbers