View source for Fibonacci word

{{Short description|Binary sequence from Fibonacci recurrence}}
[[File:Fibonacci word cutting sequence.png|thumb|upright=1.35|Characterization by a [[cutting sequence]] with a line of [[slope]] <math>1/\varphi</math> or <math>\varphi-1</math>, with <math>\varphi</math> the [[golden ratio]].]]
{{multiple image
 | direction = vertical
 | width = 220
 | image1 = Fibonacci curve F10.svg
 | caption1 = <math>S_{10}</math>
 | image2 = Fibonacci curve F17.svg
 | caption2 = <math>S_{17}</math>
 | footer = [[Fibonacci curve]]s made from the 10th and 17th Fibonacci words<!--RULES: 1 = draw forward, 0 in even position = draw forward turn left, 0 in odd position = draw forward turn right-->{{sfnp|Ramírez|Rubiano|De Castro|2014}}
}}

A '''Fibonacci word''' is a specific sequence of [[Binary numeral system|binary]] digits (or symbols from any two-letter [[Alphabet (formal languages)|alphabet]]). The Fibonacci word is formed by repeated [[concatenation]] in the same way that the [[Fibonacci number]]s 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 <math>S_0</math> be "0" and <math>S_1</math> be "01". Now <math>S_n = S_{n-1}S_{n-2}</math> (the concatenation of the previous sequence and the one before that).

The infinite Fibonacci word is the limit <math>S_{\infty}</math>, that is, the (unique) infinite sequence that contains each <math>S_n</math>, for finite <math>n</math>, as a prefix.

Enumerating items from the above definition produces:

: <math>S_0</math> &nbsp;&nbsp; 0
: <math>S_1</math> &nbsp;&nbsp; 01
: <math>S_2</math> &nbsp;&nbsp; 010
: <math>S_3</math> &nbsp;&nbsp; 01001
: <math>S_4</math> &nbsp;&nbsp; 01001010
: <math>S_5</math> &nbsp;&nbsp; 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, ... {{OEIS|A003849}}

== Closed-form expression for individual digits ==
The ''n''<sup>th</sup> digit of the word is <math>2 + \lfloor n \varphi \rfloor - \lfloor (n+1)\varphi \rfloor</math> where <math>\varphi</math> is the [[golden ratio]] and <math>\lfloor \,\ \rfloor</math> is the [[floor function]] {{OEIS|A003849}}. As a consequence, the infinite Fibonacci word can be characterized by a cutting sequence of a line of slope <math>1/\varphi</math> or <math>\varphi-1</math>. See the figure above.

== Substitution rules ==

Another way of going from ''S''<sub>''n''</sub> to ''S''<sub>''n''&hairsp;+1</sub> is to replace each symbol 0 in ''S''<sub>''n''</sub> with the pair of consecutive symbols 0,&thinsp;1 in ''S''<sub>''n''&hairsp;+1</sub>, and to replace each symbol 1 in ''S''<sub>''n''</sub> with the single symbol 0 in ''S''<sub>''n''&hairsp;+1</sub>.

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,&thinsp;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,&thinsp;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''<sup>th</sup> digit of the word is <math>\lfloor n \varphi \rfloor - \lfloor (n-1)\varphi \rfloor - 1.</math>

== Discussion ==
The word is related to the famous sequence of the same name (the [[Fibonacci number|Fibonacci sequence]]) in the sense that addition of integers in the [[inductive definition]] is replaced with string concatenation.  This causes the length of ''S''<sub>''n''</sub> to be ''F''<sub>''n''&hairsp;+2</sub>, the (''n''&hairsp;+2)nd Fibonacci number.  Also the number of 1s in ''S''<sub>''n''</sub> is ''F''<sub>''n''</sub> and the number of 0s in ''S''<sub>''n''</sub> is ''F''<sub>''n''&hairsp;+1</sub>.

== Other properties ==
* The infinite Fibonacci word is not periodic and not ultimately periodic.{{sfnp|Berstel|1986|p=13}}
* 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''S''<sub>4</sub> = 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.{{sfnp|Adamczewski|Bugeaud|2010}}
* In the infinite Fibonacci word, the ratio (number of letters)/(number of zeroes) is φ, as is the ratio of zeroes to ones.<ref>{{cite OEIS|A003849|mode=cs2}}</ref>
* The infinite Fibonacci word is a [[balanced sequence]]: Take two [[Substring|factors]] of the same length anywhere in the Fibonacci word.  The difference between their [[Hamming weight]]s (the number of occurrences of "1") never exceeds 1.{{sfnp|Lothaire|2011|p=47}}
* The subwords 11 and 000 never occur.<ref>For the subwords that do occur, see {{harvtxt|Berstel|1986}}, pp. 14 and 18 (using the letters a and b in place of the digits 0 and 1)</ref>
* The [[complexity function]] of the infinite Fibonacci word is ''n''&nbsp;+&thinsp;1: it  contains ''n''&nbsp;+&thinsp;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]],{{sfnp|de Luca|1995}} with slope <math>1/\varphi</math>.  The infinite Fibonacci word is the [[Sturmian word#Discussion|standard word]] generated by the [[Sturmian word#Discussion|directive sequence]] (1,1,1,....).
* The infinite Fibonacci word is recurrent; that is, every subword occurs infinitely often.
* If <math>u</math> is a subword of the infinite Fibonacci word, then so is its reversal, denoted <math>u^R</math>.
* If <math>u</math> is a subword of the infinite Fibonacci word, then the least period of <math>u</math> is a Fibonacci number.
* The concatenation of two successive Fibonacci words is "almost commutative". <math>S_{n+1}=S_nS_{n-1}</math> and <math>S_{n-1}S_n</math> differ only by their last two letters.
* The number 0.010010100..., whose digits are built with the digits of the infinite Fibonacci word, is [[Transcendental number|transcendental]].
* The letters "1" can be found at the positions given by the successive values of the Upper Wythoff sequence {{OEIS |A001950}}: <math>\lfloor n\varphi^2 \rfloor</math>
* The letters "0" can be found at the positions given by the successive values of the Lower Wythoff sequence {{OEIS |A000201}}: <math>\lfloor n\varphi \rfloor</math>
* The distribution of <math>n=F_k</math> points on the [[unit circle]], placed consecutively clockwise by the golden angle <math>\frac{2\pi}{\varphi^{2}}</math>, generates a pattern of two lengths <math>\frac{2\pi}{\varphi^{k-1}},\frac{2\pi}{\varphi^k}</math> 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 <math>S_{k-1}</math> 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.{{sfnp|Berstel|1986|p=13}} The  [[Critical exponent of a word|critical exponent]] for the infinite Fibonacci word is <math>2+\varphi \approx 3.618</math>.{{sfnp|Allouche|Shallit|2003|p=37}} It is the smallest index (or critical exponent) 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 {0,1}* by the endomorphism 0 → 01, 1 → 0.{{sfnp|Lothaire|2011|p=11}}
* The ''n''th element of a Fibonacci word, <math>s_n</math>, is 1 if the [[Zeckendorf's theorem|Zeckendorf representation]] (the sum of a specific set of Fibonacci numbers) of ''n'' 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]]s [[modulo operation|modulo]] 2.{{sfnp|Kimberling|2004}}

==Applications==
Fibonacci based constructions are currently used to model physical systems with aperiodic order such as [[quasicrystal]]s, and in this context the Fibonacci word is also called the '''Fibonacci quasicrystal'''.{{sfnp|Bombieri|Taylor|1986}} Crystal growth techniques have been used to grow Fibonacci layered crystals and study their light scattering properties.{{sfnp|Dharma-wardana|MacDonald|Lockwood|Baribeau|1987}}

==See also==
* [[Mathematics and art]]<!--influence; Fibonacci word in art-->
* [[Tribonacci word]]

==Notes==
{{Reflist|colwidth=30em}}

==References==
*{{citation | last1=Adamczewski | first1=Boris | last2=Bugeaud | first2=Yann | chapter=8. Transcendence and diophantine approximation | editor1-last=Berthé | editor1-first=Valérie |editor1-link = Valérie Berthé | editor2-last=Rigo | editor2-first=Michael | title=Combinatorics, automata, and number theory | location=Cambridge | publisher=[[Cambridge University Press]] | series=Encyclopedia of Mathematics and its Applications | volume=135 | page=443 | year=2010 | isbn=978-0-521-51597-9 | zbl= 1271.11073}}.
*{{citation
 | last1 = Allouche | first1 = Jean-Paul
 | last2 = Shallit | first2 = Jeffrey | author2-link = Jeffrey Shallit
 | isbn = 978-0-521-82332-6
 | publisher = [[Cambridge University Press]]
 | title = Automatic Sequences: Theory, Applications, Generalizations
 | year = 2003}}.
*{{citation
 | last = Berstel | first = Jean
 | editor1-last = Rozenberg | editor1-first = G.
 | editor2-last = Salomaa | editor2-first = A.
 | contribution = Fibonacci Words – A Survey
 | contribution-url = https://www-igm.univ-mlv.fr/~berstel/Articles/1985BookOfL.pdf
 | doi = 10.1007/978-3-642-95486-3_2
 | isbn = 9783642954863
 | pages = 13–27
 | publisher = Springer
 | title = The Book of L
 | year = 1986}}
*{{citation
 | last1 = Bombieri | first1 = E. | author1-link = Enrico Bombieri
 | last2 = Taylor | first2 = J. E. | author2-link = Jean Taylor
 | doi = 10.1051/jphyscol:1986303
 | issue = C3
 | journal = Le Journal de Physique
 | mr = 866320
 | pages = 19–28
 | title = Which distributions of matter diffract? An initial investigation
 | volume = 47
 | year = 1986| s2cid = 54194304 | url = https://hal.archives-ouvertes.fr/jpa-00225713/file/ajp-jphyscol198647C303.pdf }}.
*{{citation
 | last1 = Dharma-wardana | first1 = M. W. C.
 | last2 = MacDonald | first2 = A. H.
 | last3 = Lockwood | first3 = D. J.
 | last4 = Baribeau | first4 = J.-M.
 | last5 = Houghton | first5 = D. C.
 | journal = [[Physical Review Letters]]
 | pages = 1761–1765
 | title = Raman scattering in Fibonacci superlattices
 | volume = 58
 | year = 1987 | issue = 17
 | doi=10.1103/physrevlett.58.1761 | pmid = 10034529| bibcode = 1987PhRvL..58.1761D
 }}.
*{{citation
 | last = Kimberling | first = Clark | author-link = Clark Kimberling
 | editor-last = Howard | editor-first = Frederic T.
 | contribution = Ordering words and sets of numbers: the Fibonacci case
 | doi = 10.1007/978-0-306-48517-6_14
 | location = Dordrecht
 | mr = 2076798
 | pages = 137–144
 | publisher = Kluwer Academic Publishers
 | title = Applications of Fibonacci Numbers, Volume 9: Proceedings of The Tenth International Research Conference on Fibonacci Numbers and Their Applications
 | year = 2004| isbn = 978-90-481-6545-2 }}.
*{{citation
 | last = Lothaire | first = M. | authorlink = M. Lothaire
 | edition = 2nd
 | isbn = 0-521-59924-5
 | publisher = [[Cambridge University Press]]
 | series = Encyclopedia of Mathematics and Its Applications
 | title = Combinatorics on Words
 | volume = 17
 | year = 1997}}.
*{{citation
 | last = Lothaire | first = M. | author-link = M. Lothaire
 | isbn = 978-0-521-18071-9
 | publisher = [[Cambridge University Press]]
 | series = Encyclopedia of Mathematics and Its Applications
 | title = Algebraic Combinatorics on Words
 | volume = 90
 | year = 2011}}. Reprint of the 2002 hardback.
*{{citation
 | last = de Luca | first = Aldo
 | doi = 10.1016/0020-0190(95)00067-M
 | issue = 6
 | journal = [[Information Processing Letters]]
 | pages = 307–312
 | title = A division property of the Fibonacci word
 | volume = 54
 | year = 1995}}.
*{{citation
 | last1 = Mignosi | first1 = F.
 | last2 = Pirillo | first2 = G.
 | issue = 3
 | journal = Informatique Théorique et Application
 | pages = 199–204
 | title = Repetitions in the Fibonacci infinite word
 | url = https://scholar.archive.org/work/kzxlsp5mirgjhfojzatmrkogii
 | volume = 26
 | year = 1992| doi = 10.1051/ita/1992260301991
 | doi-access = free
 }}.
*{{citation
 | last1 = Ramírez | first1 = José L.
 | last2 = Rubiano | first2 = Gustavo N.
 | last3 = De Castro | first3 = Rodrigo
 | doi = 10.1016/j.tcs.2014.02.003
 | journal = [[Theoretical Computer Science (journal)|Theoretical Computer Science]]
 | mr = 3175078
 | pages = 40–56
 | title = A generalization of the Fibonacci word fractal and the Fibonacci snowflake
 | volume = 528
 | year = 2014| arxiv = 1212.1368
 | s2cid = 17193119
 }}.

== External links ==
*[https://web.archive.org/web/20081218041832/http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibrab.html A detailed and accessible description, on Ron Knott's site]
*{{mathworld|title=Rabbit Sequence|urlname=RabbitSequence|mode=cs2}}
*{{YouTube|id=ZDGGEQqSXew|title=Fibonacci Word (First 200,000 bits)}}

{{DEFAULTSORT:Fibonacci Word}}
[[Category:Binary sequences]]
[[Category:Fibonacci numbers]]