Fibonacci Word - Other Properties

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.
• In the infinite Fibonacci word, the ratio (number of letters)/(number of zeroes) is, the golden ratio, 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 (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.
• 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 transcendental.
• 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 critical exponent for the infinite Fibonacci word is repetitions. 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.