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 nth digit of the word is Discussion The word is related to the famous sequence of the same name (the Fibonacci sequence) 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&hairsp;+2, the (n&hairsp;+2)nd Fibonacci number. Also the number of 1s in Sn is Fn and the number of 0s in Sn is Fn&hairsp;+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: 01S4 = 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 (number of letters)/(number of zeroes) 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 (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",