This article implements some combinatorial properties of the Fibonacci word and generalizations that can be generated from the iteration of a morphism between languages. Some graphic properties of the fractal curve are associated with these words; the curves can be generated from drawing rules similar to those used in L-systems. Simple changes to the programs generate other interesting curves.

1. Introduction

The infinite Fibonacci word,

is certainly one of the most studied words in the field of combinatorics on words [1–4]. It is the archetype of a Sturmian word [5]. The word can be associated with a fractal curve with combinatorial properties [6–7].

This article implements Mathematica programs to generate curves from and a set of drawing rules. These rules are similar to those used in L-systems.

The outline of this article is as follows. Section 2 recalls some definitions and ideas of combinatorics on words. Section 3 introduces the Fibonacci word, its fractal curve, and a family of words whose limit is the Fibonacci word fractal. Finally, Section 4 generalizes the Fibonacci word and its Fibonacci word fractal.

2. Definitions and Notation

The terminology and notation are mainly those of [5] and [8]. Let be a finite alphabet, whose elements are called symbols. A word over is a finite sequence of symbols from . The set of all words over , that is, the free monoid generated by , is denoted by . The identity element of is called the empty word. For any word , denotes its length, that is, the number of symbols occurring in . The length of is taken to be zero. If and , then denotes the number of occurrences of in .

For two words and in , denote by the concatenation of the two words, that is, . If , then ; moreover, by denote the word ( times). A word is a subword (or factor) of if there exist such that . If , then and is called a prefix of ; if , then and is called a suffix of .

The reversal of a word is the word and . A word is a palindrome if .

An infinite word over is a map , written as . The set of all infinite words over is denoted by .

Example 1

The word , where if is a prime number and otherwise, is an example of an infinite word. The word is called the characteristic sequence of the prime numbers. Here are the first 50 terms of .

Definition 1

Let and be alphabets. A morphism is a map such that, for all , .

There is a special class of words with many remarkable properties, the so-called Sturmian words. These words admit several equivalent definitions (see, e.g. [5], [8]).

Definition 2

Let . Let , the complexity function of , be the map that counts, for all integer , the number of subwords of length in . An infinite word is a Sturmian word if for all integer .

For example, .

Since for any Sturmian word, , Sturmian words have to be over two symbols. The word in example 1 is not a Sturmian word because .

Given two real numbers , with irrational and , , define the infinite word as . The numbers and are the slope and the intercept, respectively. This word is called mechanical. The mechanical words are equivalent to Sturmian words [5]. As a special case, gives the characteristic words.

Definition 3

Let be irrational, . For , define and ; then is called a characteristic word with slope .

On the other hand, note that every irrational has a unique continued fraction expansion

where each is a positive integer. Let be an irrational number with and for . To the directive sequence , associate a sequence of words defined by , , , .

Such a sequence of words is called a standard sequence. This sequence is related to characteristic words in the following way. Observe that, for any , is a prefix of , which gives meaning to as an infinite word. In fact, one can prove that each is a prefix of for all and [5].

3. Fibonacci Word and Its Fractal Curve

Definition 4

Fibonacci words are words over defined inductively as follows: , , and , for . The words are referred to as the finite Fibonacci words. The limit

(1)

It is clear that , where is the Fibonacci number, recalling that the Fibonacci number is defined by the recurrence relation for all integer and with initial values . The infinite Fibonacci word is a Sturmian word [5]; exactly, , where is the golden ratio.

Here are the first 50 terms of .

Definition 5

The Fibonacci morphism is defined by and .

The Fibonacci word satisfies and for all .

Here are the first nine finite Fibonacci words.

Definition 6

Let be the map such that deletes the last two symbols.

The following proposition summarizes some basic properties about the Fibonacci word.

Proposition 1

1. The words 11 and 000 are not subwords of the Fibonacci word.
2. Let be the last two symbols of . For , if is even and if is odd.
3. The concatenation of two successive Fibonacci words is almost commutative; that is, and have a common prefix of length , for all .
4. is a palindrome for all .
5. For all , , where ; that is, exchanges the two last symbols of .

The Fibonacci Word Fractal

The Fibonacci word can be associated with a curve using a drawing rule. A particular action follows on the symbol read (this is the same idea as that used in L-systems [9]). In this case, the drawing rule is called “the odd-even drawing rule” [7].

Definition 7

The Fibonacci curve, denoted by , is the result of applying the odd-even drawing rule to the word . The Fibonacci word fractal is defined as

The program LShow is adapted from [10] to generate L-systems.

Figure 1 shows an L-system interpretation of the odd-even drawing rule.

Figure 1. Interpretation of the odd-even drawing rule.

Here are the curves for .

The next proposition about properties of the curves and comes directly from the properties of the Fibonacci word from Proposition 1. More properties can be found in [7].

Proposition 2

The Fibonacci word fractal and the curve have the following properties:

1. is composed only of segments of length 1 or 2.
2. The number of turns in the curve is the Fibonacci number .
3. The curve is similar to the curve .
4. The curve is symmetric.
5. The curve is composed of five curves: , where is the result of applying the odd-even drawing rule to the word .

The next figure shows the curve and the five curves; here .

Some Variations

The Fibonacci word and other words can be derived from the dense Fibonacci word, which was introduced in [7].

Definition 8

The dense Fibonacci word comes from the Fibonacci word by applying the morphism

(2)

so that .

Given a drawing rule, the global angle is the sum of the successive angles generated by the word through the rule. With the natural drawing rule, , , , then .

For a drawing rule, the resulting angle of a word is the function that gives the global angle. A morphism preserves the resulting angle if for any word , ; moreover, a morphism inverts the resulting angle if for any word , .

The dense Fibonacci word is strongly linked to the Fibonacci word fractal because can generate a whole family of curves whose limit is the Fibonacci word fractal [7]. All that is needed is to apply a morphism to that preserves or inverts the resulting angle.

Here are some examples.

Here are some examples with other angles.

4. Generalized Fibonacci Words and Fibonacci Word Fractals

This section introduces a generalization of the Fibonacci word and the Fibonacci word fractal [11].

Definition 9

The -Fibonacci words are words over defined inductively by , , and , for and . The infinite word

is called the -Fibonacci word.

The 2-Fibonacci word is the classical Fibonacci word. Here are the first six -Fibonacci words.

The following proposition relates the Fibonacci word to .

Proposition 3

Let be the morphism defined by and , ; then

(3)

for all .

Definition 10

The -Fibonacci number is defined recursively by , , and , for all and .

The -Fibonacci numbers are the Fibonacci numbers and the -Fibonacci numbers are the Fibonacci numbers shifted by one. The following table shows the first terms in the sequences and their reference numbers in the On-Line Encyclopedia of Sequences (OIES) [12].

Proposition 4

The -Fibonacci word and the -Fibonacci word satisfy the following:

1. The word 11 is not a subword of the -Fibonacci word, .
2. Let be the last two symbols of . For , if is even and if is odd, .
3. The concatenation of two successive -Fibonacci words is almost commutative; that is, and have a common prefix of length for all and .
4. is a palindrome for all .
5. For all , , where .

Theorem 1

Let be an irrational number, with a positive integer; then .

For the proof, see [11]. This theorem implies that -Fibonacci words are Sturmian words.

Note that

where is the golden ratio.

The -Fibonacci Word Fractal

Definition 11

The Fibonacci curve, denoted by , is the result of applying the odd-even drawing rule to the word . The -Fibonacci word fractal is defined as

Here are the curves for .

Proposition 5

The -Fibonacci word fractal and the curve have the following properties:

1. The Fibonacci fractal is composed only of segments of length 1 or 2.
2. The curve is similar to the curve .
3. The curve is composed of five curves: .
4. The curve is symmetric.
5. The scale factor between and is .

Other Characteristic Words

This section applies the above ideas to generate new curves from characteristic words (see
Definition 3).

Conjecture 1

If , then the curve displays the Fibonacci word fractal pattern.

Here are seven examples.

Acknowledgments

The first author was partially supported by Universidad Sergio Arboleda under grant number USA-II-2012-14. The authors would like to thank Borut Jurčič-Zlobec from Ljubljana University for his help during the development of this article.

References

About the Authors

José L. Ramírez
Instituto de Matemáticas y sus Aplicaciones
Universidad Sergio Arboleda
Calle 74 no. 14 – 14 Bogotá, Colombia
josel.ramirez@ima.usergioarboleda.edu.co

Gustavo N. Rubiano
Departamento de Matemáticas
Universidad Nacional de Colombia
AA 14490, Bogotá, Colombia
gnrubianoo@unal.edu.co