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**

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**

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**

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**

(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 word satisfies and for all .

Here are the first nine finite Fibonacci words.

**Definition 6**

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

**Proposition 1**

- The words 11 and 000 are not subwords of the Fibonacci word.
- Let be the last two symbols of . For , if is even and if is odd.
- The concatenation of two successive Fibonacci words is almost commutative; that is, and have a common prefix of length , for all .
- is a palindrome for all .
- 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 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**

- is composed only of segments of length 1 or 2.
- The number of turns in the curve is the Fibonacci number .
- The curve is similar to the curve .
- The curve is symmetric.
- 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**

(2) |

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 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**

(3) |

**Definition 10**

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 word 11 is not a subword of the -Fibonacci word, .
- Let be the last two symbols of . For , if is even and if is odd, .
- The concatenation of two successive -Fibonacci words is almost commutative; that is, and have a common prefix of length for all and .
- is a palindrome for all .
- For all , , where .

**Theorem 1**

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**

Here are the curves for .

**Proposition 5**

- The Fibonacci fractal is composed only of segments of length 1 or 2.
- The curve is similar to the curve .
- The curve is composed of five curves: .
- The curve is symmetric.
- 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**

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

[1] | J. Cassaigne, “On Extremal Properties of the Fibonacci Word,” RAIRO—Theoretical Informatics and Applications, 42(4), 2008 pp. 701-715. doi:10.1051/ita:2008003. |

[2] | W. Chuan, “Fibonacci Words”, Fibonacci Quarterly, 30(1), 1992 pp. 68-76. www.fq.math.ca/Scanned/30-1/chuan.pdf. |

[3] | W. Chuan, “Generating Fibonacci Words,” Fibonacci Quarterly, 33(2), 1995 pp. 104-112. www.fq.math.ca/Scanned/33-2/chuan1.pdf. |

[4] | F. Mignosi and G. Pirillo, “Repetitions in the Fibonacci Infinite Word,” RAIRO—Theoretical Informatics and Applications, 26(3), 1992 pp. 199-204. |

[5] | M. Lothaire, Applied Combinatorics on Words (Encyclopedia of Mathematics and its Applications), Cambridge: Cambridge University Press, 2005. |

[6] | A. Blondin Massé, S. Brlek, A. Garon, and S. Labbé, “Two Infinite Families of Polyominoes That Tile the Plane by Translation in Two Distinct Ways,” Theoretical Computer Science, 412(36), 2011 pp. 4778-4786. doi:10.1016/j.tcs.2010.12.034. |

[7] | A. Monnerot-Dumaine, “The Fibonacci Word Fractal,” preprint, 2009. hal.archives-ouvertes.fr/hal-00367972/fr. |

[8] | J.-P. Allouche and J. Shallit, Automatic Sequences: Theory, Applications, Generalizations, Cambridge: Cambridge University Press, 2003. |

[9] | P. Prusinkiewicz and A. Lindenmayer, The Algorithmic Beauty of Plants, New York: Springer-Verlag, 1990. |

[10] | E. Weisstein. “Lindenmayer System” from Wolfram MathWorld—A Wolfram Web Resource. mathworld.wolfram.com/LindenmayerSystem.html. |

[11] | J. Ramírez, G. Rubiano, and R. de Castro, “A Generalization of the Fibonacci Word Fractal and the Fibonacci Snowflake,” 2013. arxiv:1212.1368v2. |

[12] | OEIS Foundation, Inc. “The On-Line Encyclopedia of Integer Sequences.” (Aug 9, 2013) oeis.org. |

J. L. Ramírez and G. N. Rubiano, “Properties and Generalizations of the Fibonacci Word Fractal,” The Mathematica Journal, 2014. dx.doi.org/doi:10.3888/tmj.16-2. |

### 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*