Acta Polytechnica doi:10.14311/AP.2015.55.0050 Acta Polytechnica 55(1):50–58, 2015 © Czech Technical University in Prague, 2015 available online at http://ojs.cvut.cz/ojs/index.php/ap BIPERIODIC FIBONACCI WORD AND ITS FRACTAL CURVE José L. Ramíreza, ∗, Gustavo N. Rubianob a Departamento de Matemáticas, Universidad Sergio Arboleda, Bogotá, Colombia b Departamento de Matemáticas, Universidad Nacional de Colombia, Bogotá, Colombia ∗ corresponding author: josel.ramirez@ima.usergioarboleda.edu.co Abstract. In the present article, we study a word-combinatorial interpretation of the biperiodic Fibonacci sequence of integer numbers (F (a,b)n ). This sequence is defined by the recurrence relation aF (a,b) n−1 + F (a,b) n−2 if n is even and bF (a,b) n−1 + F (a,b) n−2 if n is odd, where a and b are any real numbers. This sequence of integers is associated with a family of finite binary words, called finite biperiodic Fibonacci words. We study several properties, such as the number of occurrences of 0 and 1, and the concatenation of these words, among others. We also study the infinite biperiodic Fibonacci word, which is the limiting sequence of finite biperiodic Fibonacci words. It turns out that this family of infinite words are Sturmian words of the slope [0,a,b]. Finally, we associate to this family of words a family of curves with interesting patterns. Keywords: Fibonacci word, biperiodic Fibonacci word, biperiodic Fibonacci curve. 1. Introduction The Fibonacci numbers and their generalizations have many interesting properties and combinato- rial interpretations, see, e.g., [13]. The Fibonacci numbers Fn are defined by the recurrence relation Fn = Fn−1 + Fn−2, for all integer n ≥ 2, and with initial values F0 = 1 = F1. Many kinds of generalizations of the Fibonacci se- quence have been presented in the literature. For example, Edson and Yayenie [12] introduced the biperi- odic Fibonacci sequence { F (a,b) n } n∈N. For any two nonzero real numbers a and b, this is defined recur- sively by F (a,b) 0 = 0, F (a,b) 1 = 1, F (a,b)n = { aF (a,b) n−1 + F (a,b) n−2 , if n ≥ 2 is even, bF (a,b) n−1 + F (a,b) n−2 , if n ≥ 2 is odd. To avoid cumbersome notation, let us denote F (a,b)n by qn. The first few terms are {qn}∞n=0 = {0, 1,a,ab + 1,a 2b + 2a, a2b2 + 3ab + 1,a3b2 + 4a2b + 3a,. . .}. Note that if a = b = 1, then qn is the nth Fibonacci number. A Binet-like formula to the biperiodic Fi- bonacci sequence is qn = ( a1−ξ(n) (ab)bn2 c ) αn −βn α−β , (1) where α = ab + √ (ab)2 + 4ab 2 , β = ab− √ (ab)2 + 4ab 2 , and ξ(n) := n− 2 ⌊n 2 ⌋ . On the other hand, there exists a well-known word- combinatorial interpretation of the Fibonacci sequence. Let fn be a binary word defined inductively as follows f0 = 1, f1 = 0, fn = fn−1fn−2, for n ≥ 2. It is clear that |fn| = Fn, i.e., the length of the word fn is the nth Fibonacci number. The words fn are called finite Fibonacci words. The infinite Fibonacci word, f = 0100101001001010010100100101 · · · is defined by the limit sequence of the infinite sequence {fn}n∈N. It is the archetype of a Sturmian word [2, 14], and one of the most studied examples in the combinatorial theory of infinite words; see, e.g., [3, 5, 6, 8, 10, 15, 17]. The word f can be associated with a curve from a drawing rule, which has geometric properties obtained from the combinatorial properties of f [4, 16]. The curve produced depends on the rules given. We read the symbols of the word in order and depending on what we read, we draw a line segment in a certain direction; this idea is the same as that used in L- Systems [18]. In this case, the drawing rule is called the “odd-even drawing rule” [16]. This is defined as shown in Table 1. The nth-curve of Fibonacci, denoted by Fn, is ob- tained by applying the odd-even drawing rule to the word fn. The Fibonacci word fractal F, is defined as F = limn→∞Fn. For example, in Figure 1, we show the curve F10 and F17. The graphics in the present article were generated using the Mathematica 9.0 software, [19, 21]. f10 = 0100101001001010010100100101001 0010100101001001010010100100101 001001010010100100101001001. 50 http://dx.doi.org/10.14311/AP.2015.55.0050 http://ojs.cvut.cz/ojs/index.php/ap vol. 55 no. 1/2015 Biperiodic Fibonacci Word and Its Fractal Curve Figure 1. Fibonacci curves F10 and F17 corresponding to the words f10 and f17. Symbol Action 1 Draw a line forward. 0 Draw a line forward and if the symbol 0 is in an even position, then turn left and if 0 is in an odd position, then turn right. Table 1. Odd-even drawing rule. Ramírez et al. [22] introduced a generalization of the Fibonacci word, the i-Fibonacci word. Specifi- cally, the (n,i)-Fibonacci words are words over {0,1} defined inductively as follows: f[i]0 = 0, f [i] 1 = 0 i−11, f [i] n = f [i] n−1f [i] n−2, for n ≥ 2 and ≥ 1. The infinite word f [i] := limn→∞f [i] n is called the i-Fibonacci word. For i = 2, we have the classical Fibonacci word. Note that |f[i]n | = F [i] n , where F [i] n is the inte- ger sequence defined recursively by F [i]0 = 1,F [i] 1 = i,F [i] n = F [i] n−1 + F [i] n−2, for n ≥ 2, and i ≥ 1. For i = 1, 2 we have the Fibonacci numbers. Ramírez and Rubiano [20] studied a similar binary word to f[i]n , which is denoted by fk,n. The initial values are the same, i.e., fk,0 = 0,fk,1 = 0k−11. How- ever, the recurrence relation is defined by fk,n = fkk,n−1fk,n−2, for n ≥ 2, and k ≥ 1. The infi- nite word fk is the limit sequence of the infinite sequence {fk,n}n∈N. For k = 1, we have the word f = 1011010110110 . . .. Here the overline is short- hand for the morphism that maps 0 to 1 and 1 to 0. It is clear that |fk,n| = Fk,n+1, where Fk,n+1 is the integer sequence defined recursively by Fk,0 = 0,Fk,1 = 1,Fk,n+1 = kFk,n + Fk,n−1, for n ≥ 1. By analogy with the Fibonacci word fractal, when we apply the odd-even drawing rule to the words f[i]n and fk,n, we obtain the nth word fractal F [i] n and Fk,n, respectively. Moreover, we have the curves F[i] and Fk, which are defined as F[i] = limn→∞F [i] n and Fk = limn→∞Fk,n. In Table 2, we show some curves F[i]16 and Fk,n, and their associated words. In this paper, we study a word-combinatorial inter- pretation of the biperiodic Fibonacci sequence [12]. This problem was recently proposed by Ramírez et al. [22]. We study a family of infinite words f(a,b) that generalize the Fibonacci word and the word fk. Specifically, the nth biperiodic Fibonacci words are words over {0,1} defined inductively as follows f(a,b,0) = �, f(a,b,1) = 0, f(a,b,2) = 0a−11, f(a,b,n) = { fa(a,b,n−1)f(a,b,n−2), if n ≥ 3 is even, fb(a,b,n−1)f(a,b,n−2), if n ≥ 3 is odd, for all a,b ≥ 1. It is clear that |f(a,b,n)| = F (a,b) n = qn. The infinite word f(a,b) := lim n→∞ f(a,b,n), is called the biperiodic Fibonacci word. In addition to this definition, we investigate some new combinatorial properties and we associate a family of curves with interesting geometric properties. These properties are obtained from the combinatorial properties of the word f(a,b). 2. Definitions and Notation The terminology and notations are mainly those of Lothaire [14] and Allouche and Shallit [1]. 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 Σ, i.e., the free monoid generated by Σ, is denoted by Σ∗. The identity ele- ment � of Σ∗ is called the empty word. For any word w ∈ Σ∗, |w| denotes its length, i.e., the number of symbols occurring in w. The length of � is taken to be equal to 0. If a ∈ Σ and w ∈ Σ∗, then |w|a denotes the number of occurrences of a in w. For two words u = a1a2 · · ·ak and v = b1b2 · · ·bs in Σ∗ we denote by uv the concatenation of the two words, that is, uv = a1a2 · · ·akb1b2 · · ·bs. If v = �, then u� = �u = u. Moreover, by un we denote the word uu · · ·u (n times). A word v is a factor or subword of u if there exist x,y ∈ Σ∗ such that u = xvy. If x = � (y = �), then v is called a prefix (suffix) of u. The reversal of a word u = a1a2 · · ·an is the word uR = an · · ·a2a1 and �R = �. A word u is a palindrome if uR = u. An infinite word over Σ is a map u : N → Σ. It is written u = a1a2a3 . . .. The set of all infinite words over Σ is denoted by Σω. 51 José L. Ramírez, Gustavo N. Rubiano Acta Polytechnica f [1] = 1011010110110 · · · = f f [2] = 0100101001001 · · · = f f [3] = 0010001001000 · · · F[1]16 F [2] 16 F [3] 16 f1 = 1011010110110 · · · = f f5 = 0000100001000 · · · f6 = 0000010000010 · · · F1,18 F5,6 F6,6 Table 2. Some curves F[i]16 and Fk,n. Example 1. Let p = (pn)n≥1 = 0110101000101 · · · be an infinite word, where pn = 1 if n is a prime number and pn = 0 otherwise. The word p is called the characteristic sequence of the prime numbers. Let Σ and ∆ be alphabets. A morphism is a map h : Σ∗ → ∆∗ such that h(xy) = h(x)h(y) for all x,y ∈ Σ∗. It is clear that h(�) = �. Furthermore, a morphism is completely determined by its action on single symbols. For instance, the Fibonacci word f satisfies limn→∞σn(1) = f, where σ : {0,1} → {0,1}∗ is the morphism defined by σ(0) = 01 and σ(1) = 0. This morphism is called the Fibonacci morphism. The Fibonacci word f can be defined in several different ways, see, e.g., [3]. There is a special class of infinite words, with many remarkable properties, the so-called Sturmian words. These words admit several equivalent definitions (see, e.g. [1, 2, 14]). Let w ∈ Σω. We define P(w,n), the complexity function of w, to be the map that counts, for all integer n ≥ 0, the number of subwords of length n in w. An infinite word w is a Sturmian word if P(w,n) = n + 1 for all integers n ≥ 0. Since for any Sturmian word P (w, 1) = 2, Sturmian words are over two symbols. The word p, in Example 1, is not a Sturmian word because P(p, 2) = 4. Given two real numbers θ,ρ ∈ R with θ irrational and 0 < θ < 1, 0 ≤ ρ < 1, we define the infinite word w = w1w2w3 · · · by wn = b(n + 1)θ + ρc−bnθ + ρc. The numbers θ and ρ are called the slope and the intercept, respectively. Words of this form are called lower mechanical words and are known to be equivalent to Sturmian words [14]. As a special case, when ρ = 0, we obtain characteristic words. Definition 2. Let θ be an irrational number with 0 < θ < 1. For n ≥ 1, define wθ(n) := b(n + 1)θc− bnθc, and w(θ) := wθ(1)wθ(2)wθ(3) · · · . Then w(θ) is called the characteristic word with slope θ. Note that every irrational θ ∈ (0, 1) has a unique continued fraction expansion θ = [0,a1,a2,a3, . . .] = 1 a1 + 1 a2 + 1 a3 + · · · , where each ai is a positive integer. Let θ = [0, 1 + d1,d2, . . . ] be an irrational number with d1 ≥ 0 and dn > 0 for n > 1. We use the continued fraction expan- sion of θ as a directive sequence in the following way. We associate a sequence (sn)n≥−1 of words defined by s−1 = 1, s0 = 0, sn = sdnn−1sn−2, for n ≥ 1. 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 n ≥ 0, sn is a prefix of sn+1, which gives meaning to limn→∞sn as 52 vol. 55 no. 1/2015 Biperiodic Fibonacci Word and Its Fractal Curve a b f(a,b) 1 2 1101110111011011101110111011011 · · · 2 1 0100100101001001001010010010010 · · · 2 3 0101010010101001010101001010100 · · · 3 2 0010010001001000100100010010010 · · · 3 5 0010010010010010001001001001001 · · · Table 3. Some biperiodic Fibonacci words. an infinite word. In fact, one can prove [14] that each sn is a prefix of w(θ) for all n ≥ 0 and w(θ) = lim n→∞ sn. (2) 3. Biperiodic Fibonacci Words Let f(a,b,n) and f(a,b) be the nth biperiodic Fibonacci word and the infinite biperiodic Fibonacci word, re- spectively. Note that, for a = b = 1 we have the word f = 1011010110110 . . .. If a = b = k, we obtain k-Fibonacci words, i.e., f(k,k) = fk. Definition 3. The (a,b)-Fibonacci morphism σ(a,b) : {0,1} → {0,1}∗ is defined by σ(a,b)(0) = (0a−11)b0 and σ(a,b)(1) = (0a−11)b0a1. Theorem 4. For all n ≥ 0, σn(a,b)(0) = f(a,b,2n+1) and σn(a,b)(0 a−11) = f(a,b,2n+2). Hence, the biperiodic Fibonacci word f(a,b) satisfies that lim n→∞ σn(a,b)(0) = f(a,b). Proof. We prove the two assertions about σn(a,b) by induction on n. They are clearly true for n = 0, 1. Now assume the result holds for n, and let us prove it for n + 1: σn+1(a,b)(0) = σ n (a,b)((0 a−11)b0) = (σn(a,b)(0 a−11))bσn(a,b)(0) = fb(a,b,2n+2)f(a,b,2n+1) = f(a,b,2n+3), and σn+1(a,b)(0 a−11) = σn(a,b)(((0 a−11)b0)a−1(0a−11)b0a1) = σn(a,b)(((0 a−11)b0)a0a−11) = ((σn(a,b)(0 a−11))bσn(a,b)(0)) aσn(a,b)(0 a−11) = (fb(a,b,2n+2)f(a,b,2n+1)) af(a,b,2n+2) = fa(a,b,2n+3)f(a,b,2n+2) = f(a,b,2n+4). Example 5. In Table 3 we show some biperiodic Fibonacci words for specific values of a and b. Proposition 6. The number of occurrences of 1 and 0 in the finite biperiodic Fibonacci words are given by pn and hn, where pn and hn satisfy the following recurrences: p0 = 0, p1 = 0, p2 = 1, pn = { apn−1 + pn−2, if n ≥ 3 is even, bpn−1 + pn−2, if n ≥ 3 is odd. (3) Moreover, pn = ( b1−ξ(n−1) (ab)b n−1 2 c ) αn−1 −βn−1 α−β , for n ≥ 1, (4) and h0 = 0, h1 = 1, h2 = a− 1, hn = { ahn−1 + hn−2, if n ≥ 3 is even, bhn−1 + hn−2, if n ≥ 3 is odd. (5) Moreover, for n ≥ 1, hn = (a− 1)F (b,a) n−1 + (a b )ξ(n−1) F (b,a) n−2 . (6) Proof. Recurrences (3) and (5) are clear from defini- tion of f(a,b,n). Equation (4) is clear from the Binet- like formula; see Equation (1). We obtain Equation (6) from [12, Theorem 8]. Proposition 7. One has (1.) limn→∞ |f(a,b,n)| |f(a,b,n)|1 = α b = ab+ √ (ab)2+4ab 2b . (2.) limn→∞ |f(a,b,n)| |f(a,b,n)|0 = a(α+1) α(a−1)+a. (3.) limn→∞ |f(a,b,n)|0 |f(a,b,n)|1 = a ( 1 + 1 α ) − 1. Proof. (1.) From Equations (1) and (4) we obtain lim n→∞ |f(a,b,n)| |f(a,b,n)|1 = lim n→∞ qn pn = lim n→∞ ( a1−ξ(n) (ab)b n 2 c ) αn−βn α−β( b1−ξ(n−1) (ab)b n−1 2 c ) αn−1−βn−1 α−β = lim n→∞ (ab)b n−1 2 c(a1−ξ(n))(αn −βn) (ab)bn2 c(b1−ξ(n−1))(αn−1 −βn−1) . If n is even, then lim n→∞ |f(a,b,n)| |f(a,b,n)|1 = 1 b lim n→∞ αn −βn αn−1 −βn−1 = 1 b lim n→∞ α 1 − ( β α )n 1 − ( β α )n−1 = αb . If n is odd, the limit is the same. 53 José L. Ramírez, Gustavo N. Rubiano Acta Polytechnica (2.) From Equations (1) and (6) we obtain lim n→∞ |f(a,b,n)| |f(a,b,n)|0 = lim n→∞ qn pn = lim n→∞ ( a1−ξ(n) (ab)b n 2 c ) αn−βn α−β (a− 1)B(n) + ( a b )ξ(n−1) B(n− 1) , where B(n) = ( b1−ξ(n) (ab)b n−2 2 c ) αn−2−βn−2 α−β . If n is even, then lim n→∞ |f(a,b,n)| |f(a,b,n)|0 = a lim n→∞ αn −βn (a−1)(ab)(αn−1−βn−1)+a2b(αn−2−βn−2) = a 1 1 α (a− 1)(ab) + a2b 1 α2 = a(α + 1) α(a− 1) + a . If n is odd, the limit is the same. (3.) The proof runs like in the previous two items. The previous proposition is a particular result re- lated to the incidence matrix of a substitution, see, e.g., [7]. Proposition 8. The biperiodic Fibonacci word and the nth biperiodic Fibonacci word satisfy the following properties. (1.) Word 11 is not a subword of the biperiodic Fi- bonacci word, for a ≥ 2, and b ≥ 1. (2.) Let xy be the last two symbols of f(a,b,n). For n,a ≥ 2, and b ≥ 1, we have xy = 01 if n is even, and xy = 10 if n is odd. (3.) The concatenation of two successive biperiodic Fibonacci words is “almost commutative”, i.e., f(a,b,n−1)f(a,b,n−2) and f(a,b,n−2)f(a,b,n−1) have a common prefix of length qn−1 + qn−2 − 2, for all n ≥ 3. Proof. (1.) It suffices to prove that 11 is not a sub- word of f(a,b,n), for all n ≥ 0. We proceed by induc- tion on n. For n = 0, 1, 2 it is clear. Now, assume that it is true for an arbitrary integer n ≥ 2. If n+ 1 is even, we know that f(a,b,n+1) = fa(a,b,n)f(a,b,n−1), so by the induction hypothesis we have that 11 is not a subword of f(a,b,n) and f(a,b,n−1). Therefore, the only possibility is that 1 is a suffix and a prefix of f(a,b,n) or 1 is a suffix of f(a,b,n) and a prefix of f(a,b,n−1), but these are impossible by the definition of the word f(a,b,n). If n + 1 is odd the proof is analogous. (2.) We proceed by induction on n. For n = 2 it is clear. Now, assume that it is true for an arbitrary integer n ≥ 2. If n + 1 is even, we know that f(a,b,n+1) = fa(a,b,n)f(a,b,n−1), and by the induction hypothesis the last two symbols of f(a,b,n−1) are 01, therefore the last two symbols of f(a,b,n+1) are 01. Analogously, if n + 1 is odd. (3.) We proceed by induction on n. For n = 3, 4 it is clear. Now, assume that it is true for an arbitrary integer n ≥ 4. If n is even, then by definition of f(a,b,n), we have f(a,b,n−1)f(a,b,n−2) = fb(a,b,n−2)f(a,b,n−3) ·fa(a,b,n−3)f(a,b,n−4) = (f a (a,b,n−3)f(a,b,n−4)) b ·fa(a,b,n−3)f(a,b,n−3)f(a,b,n−4), and f(a,b,n−2)f(a,b,n−1) = fa(a,b,n−3)f(a,b,n−4) ·f b (a,b,n−2)f(a,b,n−3) = fa(a,b,n−3)f(a,b,n−4) · (f a (a,b,n−3)f(a,b,n−4)) b ·f(a,b,n−3) = (fa(a,b,n−3)f(a,b,n−4)) b fa(a,b,n−3)f(a,b,n−4)f(a,b,n−3). Hence the words have a common prefix of length b(aqn−3 + qn−4) + aqn−3 = bqn−2 + aqn−3. By the induction hypothesis f(a,b,n−3)f(a,b,n−4) and f(a,b,n−4)f(a,b,n−3) have a common prefix of length qn−3 +qn−4−2. Therefore the words have a common prefix of length bqn−2 + aqn−3 + qn−3 + qn−4 −2 = qn−1 + qn−2 −2. If n is odd the proof is analogous. The above proposition is a particular result related to Sturmian words, see, e.g., [14]. Definition 9. Let Φ : {0, 1}∗ → {0, 1}∗ be a map such that Φ deletes the last two symbols, i.e., Φ(a1a2 · · ·an) = a1a2 · · ·an−2, if n > 2, and Φ(a1a2 · · ·an) = � if n ≤ 2. Corollary 10. The nth biperiodic Fibonacci word satisfies for all n ≥ 2, and x,y ∈{0, 1} that (1.) Φ(f(a,b,n−1)f(a,b,n−2)) = Φ(f(a,b,n−2)f(a,b,n−1)). (2.) Φ(f(a,b,n−1)f(a,b,n−2)) = f(a,b,n−2)Φ(f(a,b,n−1)) = f(a,b,n−1)Φ(f(a,b,n−2)). (3.) If f(a,b,n) = Φ(f(a,b,n))xy, then Φ(f(a,b,n−2))xyΦ(f(a,b,n−1)) = f(a,b,n−1)Φ(f(a,b,n−2)). (4.) If f(a,b,n) = Φ(f(a,b,n))xy, then Φ(f(a,b,n)) =   Φ(f(a,b,n−2))(10Φ(f(a,b,n−1)))a, if n is even. Φ(f(a,b,n−2))(01Φ(f(a,b,n−1)))b, if n is odd. Proof. (1.) and (2.) follow immediately from Proposi- tion 8.(3.) and |f(a,b,n)| ≥ 2 for all n ≥ 2. For (3.), in 54 vol. 55 no. 1/2015 Biperiodic Fibonacci Word and Its Fractal Curve Symbol Action 1 Draw a line forward. 0 Draw a line forward and if the symbol 0 is in a position even, then turn θ degree and if 0 is in a position odd, then turn −θ degrees. Table 4. Odd-even drawing rule with turn angle θ. fact, if f(a,b,n) = Φ(f(a,b,n))xy, then from Proposition 8.(2.) we have f(a,b,n−2) = Φ(f(a,b,n−2))xy. Hence Φ(f(a,b,n−2))xyΦ(f(a,b,n−1)) = f(a,b,n−2)Φ(f(a,b,n−1)) = f(a,b,n−1)Φ(f(a,b,n−2)). Item (4.) is clear from (3.) and the definition of f(a,b,n). Theorem 11. Φ(f(a,b,n)) is a palindrome for all n,a ≥ 2 and b ≥ 1. Proof. We proceed by induction on n. If n = 2, 3, then Φ(f(a,b,2)) = 0a−1 and Φ(f(a,b,3)) = (0a−11)b0 are palindromes. Now, assume that it is true for an arbi- trary integer n ≥ 3. If n is even, then from Corollary 10 (Φ(f(a,b,n)))R = (Φ(fa(a,b,n−1)f(a,b,n−2))) R = (fa(a,b,n−1)Φ(f(a,b,n−2))) R = Φ(f(a,b,n−2))R(fa(a,b,n−1)) R = Φ(f(a,b,n−2))(fR(a,b,n−1)) a = Φ(f(a,b,n−2))(Φ(f(a,b,n−1)10)R)a = Φ(f(a,b,n−2))(01Φ(f(a,b,n−1)))a = (Φ(f(a,b,n))). If n is odd, the proof is analogous. Corollary 12. (1.) If f(a,b,n) = Φ(f(a,b,n))xy, then yxΦ(f(a,b,n))xy is a palindrome. (2.) If u is a subword of the biperiodic Fibonacci word, then so is its reversal, uR. The above propositions are particular results related to palindromes of Sturmian words, see, e.g., [9]. Theorem 13. Let ζ = [0,a,b] be an irrational num- ber, with a and b positive integers, then w(ζ) = f(a,b). Proof. Let ζ = [0,a,b] be an irrational number, then its associated standard sequence is s−1 = 1, s0 = 0, s1 = sa−10 s−1 = 0 a−11, and sn = { sbn−1sn−2, if n ≥ 2 is even, san−1sn−2, if n ≥ 2 is odd. Hence {sn}n≥0 = {f(a,b,n+1)}n≥0 and from Equation (2), we have w(ζ) = lim n→∞ sn = f(a,b). Remark. Note that ζ = [0,a,b] = 1 a+ 1 b+ 1 a+ 1··· = −ab+ √ (ab)2+4ab 2a = − α 2 . From the above theorem, we conclude that biperiodic Fibonacci words are Sturmian words. A fractional power is a word of the form z = xny, where n ∈ Z+, x ∈ Σ+ and y is a prefix of x. If |z| = p and |x| = q, we say that z is a p/q-power, or z = xp/q. In the expression xp/q, the number p/q is the power’s exponent. For example, 01201201 is an 8/3-power, 01201201 = (012)8/3. The index of an infinite word w ∈ Σω is defined by Ind(w) := sup{r ∈ Q≥1 : w contains an r-power.} For example, Ind(f ) > 3 because the cube (010)3 occurs in f at position 6. Mignosi and Pirillo [15] proved that Ind(f ) = 2 + φ ≈ 3.618, where φ is the golden ratio. Ramírez and Rubiano [20] proved that the index of the k-Fibonacci word is given by Ind(fk) = 2+k+1/rk,1, where rk,1 = (k+ √ k2 + 4)/2. A general formula for the index of a Sturmian word was given by Damanik and Lenz [11]. Theorem 14 [11]. If w is a Sturmian word of slope θ = [0,a1,a2,a3, . . . ], then Ind(w) = sup n≥0 {2 + an+1 + rn−1 − 2 rn }, where rn is the denominator of θ = [0,a1,a2, a3, . . . ,an] and satisfies r−1 = 0,r0 = 1,rn+1 = an+1rn + rn−1. Corollary 15. The index of the biperiodic Fibonacci word is Ind(f(a,b)) = max { 2 + a + a α , 2 + b + b α } , (7) where α = (ab + √ (ab)2 + 4ab)/2. Proof. The word f(a,b) is a Sturmian word of slope ζ = [0,a,b], then from the above theorem rn = qn+1, and Ind(f(a,b)) = supn≥0{hn}, where hn = { 2 + b + qn−1−2 qn , if n is even, 2 + a + qn−1−2 qn , if n is odd. Then Ind(f(a,b)) = max { sup n≥0 { 2 + a + q2n−2 q2n+1 } , sup n≥0 { 2 + b + q2n−1−2 q2n }} . Since q2n+1/q2n → α/a and q2n/q2n−1 → α/b as n → ∞, then Equation (7) follows. 55 José L. Ramírez, Gustavo N. Rubiano Acta Polytechnica F(2,5)9 , θ = 90 ◦ F(5,5)7 , θ = 90 ◦ F(6,6)6 , θ = 90 ◦ F(2,5)10 , θ = 90 ◦ F(2,3)10 , θ = 60 ◦ F(6,6)5 , θ = 60 ◦ Table 5. Some curves F(a,b)n with an angle θ. 4. The Biperiodic Fibonacci Word Curve The odd-even drawing rule can be extended from a parameter θ, where θ is the turn angle, see Table 4. If θ = 90◦, then we obtain the drawing rule in Table 1. Definition 16. The nth-biperiodic curve of Fi- bonacci, denoted by F(a,b)n , is obtained by applying the odd-even drawing rule to the word f(a,b,n). The biperiodic Fibonacci word fractal F(a,b), is defined as F(a,b) := limn→∞F (a,b) n . In Table 5, we show some curves F(a,b)n with a given angle θ. Proposition 17. The biperiodic Fibonacci word curve and the curve F(a,b)n have the following proper- ties: (1.) The biperiodic Fibonacci curve F(a,b) is com- posed only of segments of length 1 or 2. (2.) The curve F(a,b)n is symmetric. (3.) The number of turns in the curve F(a,b)n is hn. Proof. (1.) It is clear from Proposition 8.(1.), because 110 and 111 are not subwords of f (a,b)n . (2.) It is clear from Theorem 11, because f(a,b,n) = Φ(f(a,b,n))xy, where Φ(f(a,b,n)) is a palindrome. (3.) It is clear from the definition of the odd-even drawn rule and because |f(a,b,n)|0 = hn; see Propo- sition 6. Proposition 18 (Monnerot-Dumaine [16]). The curve F(1,1)n = Fn is similar to the curve F (1,1) n+3 = Fn+3. Proposition 19 (Ramírez and Rubiano [20]). If a is even, then the curve F(a,a)n = Fa,n is similar to the curve F(a,a)n+2 = Fa,n+2. If n is odd, then the curve F(a,a)n = Fa,n is similar to the curve F (a,a) n = Fa,n+3. Theorem 20. (1.) If a is even, then the curve F(a,b)n is similar to the curve F(a,b)n+2 , i.e., they have the same shape except for the number of segments. (2.) If a 6= b, and a,b are odd, then the curve F(a,b)n is similar to the curve F(a,b)n+6 . (3.) If a is odd, and b is even, then the curve F(a,b)n is similar to the curve F(a,b)n+4 . Proof. Suppose a is even. Then it is clear that σ(a,b)(f(a,b,n)) = f(a,b,n+2); see Theorem 4. We are going to prove that σ(a,b) preserves the odd-even alter- nation required by the odd-even drawing rule. In fact, σ(a,b)(0) = (0a−11)b0, and σ(a,b)(1) = (0a−11)b0a1. As a is even, then |σ(a,b)(0)| and |σ(a,b)(1)| are odd. 56 vol. 55 no. 1/2015 Biperiodic Fibonacci Word and Its Fractal Curve Figure 2. Curves F(2,6)7 ,F (2,6) 9 ,F (2,6) 11 with θ = 72 ◦. Hence if |w| is even (odd), then |σ(a,b)(w)| is even (odd). Since σ(a,b) preserves parity of length then any subword in a biperiodic Fibonacci word preserves parity of position. Finally, let A(w) be the function that gives the ending or resulting angle of an associate curve to the word w through the odd-even drawing rule of angle θ. We have to prove that the resulting angle of a curve must be preserved or inverted by σ(a,b). Note that A(00) = 0, A(01) = −θ and A(10) = +θ. Therefore • A(σ(a,b)(00)) = A((0a−11)b0(0a−11)b0) = A((0a−11)b) + A(0a) + A((10a−1)b−1) + A(10) = A((0a−11)b) + A(0a) + A(10) + A(0a−2) + A(10) + A(0a−2) + · · ·+A(10) = b(−θ) + 0 + θ + 0 + θ + · · · + θ = 0. • A(σ(a,b)(01)) = A((0a−11)b0(0a−11)b0a1) = A((0a−11)b) + A(0a) + A(10) + A(0a−2) + · · · + A(10)A(0a−11) = 0 −θ = −θ. • A(σ(a,b)(10)) = A((0a−11)b0a1(0a−11)b0) = A((0a−11)b) + A(0a) + A(10) + A(0a−2) + A(10) + A(0a−2) +· · ·+A(10) = bθ+ 0 +θ+ 0 +θ+· · ·+θ = bθ + (b + 1)θ = +θ. Then σ(a,b) preserves the resulting angle, i.e., A(w) = A(σ(a,b)(w)) for any word w of even length. Therefore the image of a pattern by σ(a,b) is the rotation of this pattern by an angle of +θ. Since σ(a,b)(f(a,b,n)) = f(a,b,n+2), then the curve F(a,b,n) is similar to the curve F(a,b,n+2). If a 6= b, and a,b are odd the proof is similar, but using σ3(a,b). If a is odd, and b is even the proof is similar, but using σ2(a,b). An open problem is try to find a characterization of similar word curves in terms of words. Example 21. In Figure 2, F(2,6)7 is similar to F(2,6)9 ,F (2,6) 11 and so on. In Figure 3, F (3,4) 5 is sim- ilar to F(3,4)9 and so on. Acknowledgements The authors thank the anonymous referees for their careful reading of the manuscript and their fruitful comments and suggestions. This research is for the Observatorio de Resti- tuciÃşn y RegulaciÃşn de Derechos de Propiedad Agraria. Moreover, it was supported in part by the equipment dona- tion from the German Academic Exchange Service-DAAD to the Faculty of Science at the Universidad Nacional de Colombia. 57 José L. Ramírez, Gustavo N. Rubiano Acta Polytechnica Figure 3. Curves F(3,4)5 ,F (3,4) 9 with θ = 120 ◦. References [1] Allouche, J., Shallit, J., Automatic Sequences, Cambridge University Press, Cambridge, 2003. [2] Baláži, P., Various properties of Sturmian words, Acta Polytech. 45(5), 2002, 19–23. [3] Berstel, J., Fibonacci words-a survey, in: G. Rosenberg, A. Salomaa (Eds.), The Book of L, Springer, Berlin, 1986, 11–26. [4] Blondin-Massé, A., Brlek, S., Garon, A., Labbé, S., Two infinite families of polyominoes that tile the plane by translation in two distinct ways, Theoret. Comput. Sci. 412, 2011, 4778–4786. [5] Cassaigne, J., On extremal properties of the Fibonacci word, RAIRO - Theor. Inf. Appl., 42(4), 2008, 701–715. [6] Chuan, W., Fibonacci words, Fibonacci Quart., 30(1), 1992, 68–76. [7] Fuchs, C., Tijdeman, R., Substitutions, abstract number systems and the space filling property, Ann. Inst. Fourier, 56(7), 2006, 2345–2389. [8] De Luca, A., A division property of the Fibonacci word, Inform. Process. Lett., 54, 1995, 307–312. [9] De Luca, A., Mignosi, F., Some combinatorial properties of Sturmian words, Theoret. Comput. Sci. 136, 1994, 361–385. [10] Droubay X., Palindromes in the Fibonacci word, Inform. Process. Lett., 55, 1995, 217–221. [11] Damanik, D., Lenz, D., The index of Sturmian sequences, European J. Combin., 23(1), 2002, 23–29. [12] Edson, M., Yayenie, O., A new generalization of Fibonacci sequence and extended Binet’s formula, Integers, 9(6), 2009, 639–654. [13] Koshy, T., Fibonacci and Lucas Numbers with Applications, A Wiley-Interscience Publication, 2001. [14] Lothaire, M., Algebraic combinatorics on words, Encyclopedia of Mathematics and its Applications, Cambridge University Press, Cambridge, 2002. [15] Mignosi, F., Pirillo, G., Repetitions in the Fibonacci infinite word, RAIRO Inform. Theor. Appl., 26, 1992, 199–204. [16] Monnerot-Dumaine, A., The Fibonacci word fractal, preprint, http: //hal.archives-ouvertes.fr/hal-00367972/fr/, 2009 [2014-12-01]. [17] Pirillo, G., Fibonacci numbers and words, Discrete Math., 173, 1997, 197–207. [18] Prusinkiewicz, P., Lindenmayer, A.: The algorithmic beauty of plants, Springer-Verlag. Nueva York, 2004. [19] Ramírez, J., Rubiano, G., Generating fractals curves from homomorphisms between languages [with Mathematicar] (in Spanish), Revista Integración 30(2), 2012, 129–150. [20] Ramírez, J., Rubiano, G., On the k-Fibonacci words, Acta Univ. Sapientiae Infor., 5(2), 2013, 212–226. [21] Ramírez, J., Rubiano, G., Properties and generalizations of the Fibonacci word fractal. Exploring fractal curves, The Mathematica Journal, 16, 2014. [22] Ramírez, J., Rubiano, G., De Castro, R., A generalization of the Fibonacci word fractal and the Fibonacci snowflake, Theoret. Comput. Sci., 528, 2014, 40–56. 58 http://hal.archives-ouvertes.fr/hal-00367972/fr/ http://hal.archives-ouvertes.fr/hal-00367972/fr/ Acta Polytechnica 55(1):50–58, 2015 1 Introduction 2 Definitions and Notation 3 Biperiodic Fibonacci Words 4 The Biperiodic Fibonacci Word Curve Acknowledgements References