# K-nacci Sequences in Finite Triangle Groups

Authors: Erdal Karaduman; Ömür Deveci
Journal: Discrete Dynamics in Nature and Society
 (2009)

---

## Abstract

Ak-nacci sequence in a finite group is a sequence of group elements x0,x1,x2,…,xn,…
for
which, given an initial (seed) set x0,x1,x2,…,xj−1
, each element is defined by
xn=x0x1…xn−1,forj≤n<k,andxn=xn−kxn−k+1…xn−1,forn≥k.
We also require that the initial elements of the sequence, x0,x1,x2,…,xj−1, generate the group, thus forcing the k-nacci sequence to reflect the structure of the group. The K-nacci sequence of a group generated by x0,x1,x2,…,xj−1
is denoted by Fk(G;x0,x1,…,xj−1)
and its period is
denoted by Pk(G;x0,x1,…,xj−1)
. In this paper, we obtain the period of K-nacci sequences in
finite polyhedral groups and the extended triangle groups.


---

## Body

## 1. Introduction

The Fibonacci sequences and their related higher-order (tribonacci, quatranacci,k-nacci) are generally viewed as sequences of integers. In [1] the Fibonacci length of a 2-generator group is defined, thus extending the idea of forming a sequence of group elements based on a Fibonacci-like recurrence relation first introduced by Wall in [2]. There he considered the Fibonacci length of the cyclic group Cn. The concept of Fibonacci length for more than two generators has also been considered, see, for example [3, 4]. Also, the theory has been expanded to the nilpotent groups, see, for example [5–7]. Other works on Fibonacci length are discussed in, for example, [8–12]. Knox proved that the periods of k-nacci (k-step Fibonacci) sequences in dihedral groups are equal to 2k+2 [13]. Campbell and Campbel, examined the behaviour of the Fibonacci length of the finite polyhedral, binary polyhedral groups, and related groups in [14].This paper discusses the period ofk-nacci Fibonacci sequences in the polyhedral groups (2,2,2), (n,2,2), (2,n,2), (2,2,n) for any n and in the extended triangle groups E(2,2,2), E(n,2,2), E(2,n,2), E(2,2,n) for any n>2. We consider  polyhedral groups both as 2-generator and as 3-generator groups. A2-step Fibonacci sequence in the integers modulo m can be written as  F2(Zm;0,1). A 2-step Fibonacci sequence of group elements is called a Fibonacci sequence of a finite group. A finite group G is k-nacci sequenceable if there exists a k-nacci sequence of G such that every element of the group appears in the sequence. A sequence of group elements isperiodic if, after a certain point, it consists only of repetitions of a fixed subsequence. The number of elements in the repeating subsequence is called the period of the sequence. For example, the sequence x0,x1,x2,x3,x4,x1,x2,x3,x4,x1,x2,x3,x4,… is periodic after the initial element x0 and has period 4. A sequence of group elements is simply periodic with period k if the first k elements in the sequence form a repeating subsequence. For example, the sequence x0,x1,x2,x3,x4,x0,x1,x2,x3,x4,… is simply periodic with period 5. It is important to note that the Fibonacci length depends on the chosen generating n- tuple for a group.Definition 1.1.
For a finitely generated groupG=〈A〉 where A={a1,a2,…,an} the sequence xi=ai+1, 0≤i≤n-1, xi+n=∏j=1nxi+j-1, i≥0, is called theFibonacci orbit of G with respect to the generating set A, denoted FA(G).
Notice that the orbit of ak-generated group is a k-nacci sequence. The orbits of (n,2,2), (2,n,2), (2,2,n) for any n>2 and E(2,q,2) for any q>2 are studied in [14].


## 2. The Groups(2,2,2), (n,2,2), (2,n,2), and (2,2,n)

Definition 2.1.
Thepolyhedral group(l,m,n) for l,m,n>1 is defined by the presentation
(2.1)〈x,y,z:xl=ym=zn=xyz=e〉
or
(2.2)〈x,y:xl=ym=(xy)n=e〉.
The polyhedral group(l,m,n) is finite if and only if the number
(2.3)μ=lmn(1l+1m+1n-1)=mn+nl+lm-lmn
is positive, that is, in the case (2,2,n), (2,3,3), (2,3,3), (2,3,4), (2,3,5). Its order is 2lmn/μ. Using Tietze transformations, we may show that (l,m,n)≅(m,n,l)≅(n,l,m). For more information on these groups see [15] and [16, pages 67–68]. The groups considered in Theorems 2.3 and 2.4 are the same group, namely, Dn, the dihedral group of 2n  elements, except the generators x,y, and z are different from one theorem to the other.Theorem 2.2.
LetG2 be the group defined by the presentation G2=〈x,y,z:x2=y2=z2=xyz=e〉. Then Pk(G2,x,y,z)=k+1.Proof.
Firstly, let us consider the 2-generator case. Notice thatG2 is Z2⊕Z2 and Pk(Z2;0,1)=k+1. Under these identifications, since the period of a Fibonacci sequence in a direct product of groups is the least common multiple of the periods in each the factors we get Pk(G2;x,y)=k+1. On the other hand, since z=xy the formulas in the “three generator case” with recurrences of period  k+1 are the same as the formulas the two generator case as long as k≥4.Theorem 2.3.
LetGn,n>2, be the group defined by the presentation 〈x,y,z:xn=y2=z2=xyz=e〉. Then Pk(Gn;x,y,z)=2k+2.Proof.
Let us consider the 3-generator case. We first note that the orders ofx,y, and z are n,2,2, respectively. If k=2, we have the sequence
(2.4)x,y,z,yz,zyz,z,x,y,…,
which has period 6. If k=3, we have the sequence
(2.5)x,y,z,xyz=e,yz,zyz,z,e,x,y,z,…,
which has period 8. If k≥4, the first k elements of sequence are
(2.6)x0=x,x1=y,x2=z,x3=xyz,x4=(xyz)2,…,xk-1=(xyz)2k-3.
Thus, using the above information the sequence reduces to
(2.7)x0=x,x1=y,x2=z,x3=e,x4=e,…,e,
where  xj=efor3≤j≤k-1. Thus,
(2.8)xk=∏i=0k-1xi=(xy)2k-2=e,xk+1=∏i=1kxi=yz=xn-1,xk+2=∏i=2k+1xi=zyz=xz,xk+3=∏i=3k+2xi=z,xk+4=∏i=4k+3xi=e,…,e.
It follows that xk+j=efor4≤j≤k.  We also have,
(2.9)xk+k+1=∏i=k+1k+kxi=e,xk+k+2=∏i=k+2k+k+1xi=x,xk+k+3=∏i=k+3k+k+2xi=y,xk+k+4=∏i=k+4k+k+3xi=z.
Since the elements succeeding x2k+2,x2k+3,x2k+4, depend on x,y, and z for their values, the cycle begins again with the 2k+2nd element; that is, x0=x2k+2,x1=x2k+3,x2=x2k+4,…. Thus, Pk(Gn;x,y,z)=2k+2.
Similarly, it is easy to show that for 2-generator,Pk(Gn;x,y,z)=2k+2 in (n,2,2), and it can be shown that Pk(Gn;x,y,z)=2k+2 for (2,n,2).
Because of(n,2,2)≅(2,n,2)≅(2,2,n)≅Dn for any n>2 and using Tietze transformations we can obtain the same presentation for this groups, it is easy to show that for 2-generator  Pk(Gn;x,y)=2k+2 in the groups (n,2,2),(2,n,2), and (2,2,n).Theorem 2.4.
LetGn,n>2, be the group defined by the presentation 〈x,y,z:x2=y2=zn=xyz=e〉
(i)P2(Gn;y,x,z)=6:
(ii)
(2.10)P4(Gn;x,y,z)={n(52),n≡0mod4,5n,n≡2mod4,10n,otherwise,
(iii) k≥5.
(1)
If there is not∈[3,k-2] such that t is a odd factor of n, then
(2.11)Pk(Gn;x,y,z)={n(k+12),n≡0mod4,n(k+1),n≡2mod4,2n(k+1),otherwise.(2)
Letα be the biggest odd factor of n in [3,k-2].Then two cases occur:
(i′)
ifα3j∉[3,k-2] for j∈N, then
(2.12)Pk(Gn;x,y,z)={α(n(k+12)),n≡0mod4,α(n(k+1)),n≡2mod4,α(2n(k+1)),otherwise;(ii′)
ifβ is the biggest odd number which is in [3,k-2] and β=α3j for  j∈N, then
(2.13)Pk(Gn;x,y,z)={β(n(k+12)),n≡0mod4,β(n(k+1)),n≡2mod4,β(2n(k+1)),otherwise.Proof.
We considerGn as Dn, the dihedral group of 2n  elements. Now Dn being the group of symmetries of the regular polygon with n elements admits a presentation as the group generated by the two matrices:(2.14)a:=(cos(2πn)-sin(2πn)sin(2πn)cos(2πn)),b:=(100-1).
Under these identifications, we can take z=(cos(2π/n)-sin(2π/n)sin(2π/n)cos(2π/n)),y=(100-1), and x=(cos(2π/n)-sin(2π/n)-sin(2π/n)-cos(2π/n)).(i)
Ifk=2, we have the sequence(2.15)x0=y,x1=x,x2=z,x3=(cos(4πn)-sin(4πn)-sin(4πn)-cos(4πn))=xz,x4=x,x5=(cos(2πn)sin(2πn)-sin(2πn)cos(2πn))=xy,x6=y,x7=x,x8=z,….
Thus we get P2(Gn;y,x,z)=6.(ii)
Ifk=4, we have the sequence(2.16)x,y,z,xyz=(1001)=e,(xyz)2=(1001)=e,(cos(2πn)-sin(2πn)-sin(2πn)-cos(2πn))=x,(100-1)=y,(cos(2πn)sin(2πn)-sin(2πn)cos(2πn))=xy,(cos(4πn)sin(4πn)-sin(4πn)cos(4πn))=z-2,(cos(6πn)sin(6πn)sin(6πn)-cos(6πn))=z4x,(cos(14πn)sin(14πn)sin(14πn)-cos(14πn))=z8x,(100-1)=y,(cos(2πn)-sin(2πn)sin(2πn)cos(2πn))=z,(cos(8πn)-sin(8πn)sin(8πn)cos(8πn))=z4,(cos(24πn)-sin(24πn)sin(24πn)cos(24πn))=z12,(cos(34πn)-sin(34πn)-sin(34πn)-cos(34πn))=xz16,….
Now we consider what happens to the 4-nacci sequence when we have a section of the form …,zτx,zx,z,…:
(2.17)zτx,zx=y,z,zε,zτ+ε,xz2ε+τ,y,xzx=xy,xzε+2x=z-(ε+2),xz3ε+τ+4x=z-(3ε+τ+4),z4ε+τ+8x,zx=y,z,….
The 4-nacci sequence can be said to form layers of length 10. Using the above, the 4-nacci sequence becomes
(2.18)x0=x,x1=y,x2=z,x3=e,…,x10=z8x,x11=zx=y,x12=z,x13=z4,…,x20=z32x,x21=zx=y,x22=z,x23=z8,…,x10i=z8i2x,x10i+1=zx=y,x10i+2=z,x10i+3=z4i,…,
where z8i2=(cos8i2(2π/n)-sin8i2(2π/n)sin8i2(2π/n)cos8i2(2π/n)) and z4i=(cos4i(2π/n)-sin4i(2π/n)sin4i(2π/n)cos4i(2π/n)).
So, we need the smallesti∈N such that 8i2=nv1 and 4i=nv2 for v1,v2∈N.
Ifn≡0(mod4),  z8i2=(1001) and z4i=(1001) for i=n/4.
Thus,10i=(5/2)n and P4=(Gn;x,y,z)=n((k+1)/2)=(5/2)n.
Ifn≡2(mod4), z8i2=(1001) and z4i=(1001) for i=n/2.
Thus,10i=5n and P4=(Gn;x,y,z)=n(k+1)=5n.
Ifn≡1(mod4) or n≡3(mod4), z8i2=(1001) and z4i=(1001) for i=n.
Thus,10i=10n and P4=(Gn;x,y,z)=2n(k+1)=10n.
(iii)
Ifk≥5, the first k+1 elements of the sequence are(2.19)x0=x,x1=y,x2=z,x3=zn,x4=z2n,…,xk=z2k-3n.
Thus, using the above information, the sequence reduces
(2.20)x0=x,x1=y,x2=z,x3=e,x4=e,…,e,
where xj=e for 3≤j≤k.
Now we consider what happens to thek-nacci sequence when we have a section of the form …,zτx,zx,z,…:
(2.21)x2k+2=∏i=k+22k+1xi=zτx,x2k+2+1=∏i=k+32k+2xi=zx=y,x2k+2+2=∏i=k+42k+3xi=z,x2k+2+3=∏i=k+52k+4xi=zε,x2k+2+4=∏i=k+62k+5xi=zc,x2k+2+5=∏i=k+72k+6xi=zu1,…,x2k+2+k=∏i=2k+23k+1xi=zuk-4,….
The k-nacci sequence can be said to form layers of length (2k+2). Using the above, the  k-nacci sequence becomes
(2.22)x0=x,x1=y,x2=z,x3=e,…,xk=z2k-3n=e,…,xi(2k+2)=zτx,xi(2k+2)+1=zx,xi(2k+2)+2=z,xi(2k+2)+3=z4i,xi(2k+2)+4=z8i2+4i,xi(2k+2)+5=zu1,…,xi(2k+2)+k=zuk-4,….
So, we need the smallest i∈N such that 4i=nv1 and 8i2+4i=nv2 for v1,v2∈N. (1)
If there is not∈[3,k-2] such that t is an odd factor of n, there are 3 subcases.Case 1.
Ifn≡0(mod4) and n∣τ,n∣u1,…,n∣uk-4 , z4i=(1001), and z8i2+4i=(1001) for i=n/4.  So, we get Pk=(Gn;x,y,z)=n((k+1)/2) since i(2k+2)=n((k+1)/2) (where by n∣τ we mean that n divides τ).Case 2.
Ifn≡2(mod4)  and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001), and z8i2+4i=(1001) for i=n/2. So, we get Pk=(Gn;x,y,z)=n(k+1) since i(2k+2)=n(k+1).Case 3.
Ifn≡1(mod4) or n≡3(mod4) and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001), and z8i2+4i=(1001) for  i=n. So, we get Pk=(Gn;x,y,z)=2n(k+1) since i(2k+2)=2n(k+1).(2)
Letα odd be the biggest factor of n in [3,k-2]. Then two cases occur:
(i′)
Ifα3j∉[3,k-2] for j∈N, then there are 3 subcases.Case 1.
Ifn≡0(mod4)  and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001), and z8i2+4i=(1001) for i=α(n/4). So, we get Pk=(Gn;x,y,z)=α(n((k+1)/2)) since i(2k+2)=α(n((k+1)/2)).Case 2.
Ifn≡2(mod4)  and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001), and z8i2+4i=(1001) for i=α(n/2). So, we get Pk=(Gn;x,y,z)=α(n(k+1)) since i(2k+2)=α(n(k+1)).Case 3.
Ifn≡1(mod4) or n≡3(mod4) and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001) and z8i2+4i=(1001) for i=αn. So, we get Pk=(Gn;x,y,z)=α(2n(k+1)) since i(2k+2)=α(2n(k+1)).(ii’)
Ifβ is the biggest odd number which is in [3,k-2] and β=α3j for j∈N, then there are 3 subcases.Case 1.
Ifn≡0(mod4)  and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001), and z8i2+4i=(1001) for i=β(n/4). So, we get Pk=(Gn;x,y,z)=β(n((k+1)/2)) since i(2k+2)=β(n((k+1)/2)).Case 2.
Ifn≡2mod4  and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001), and z8i2+4i=(1001) for i=β(n/2). So, we get Pk=(Gn;x,y,z)=β(n(k+1)) since i(2k+2)=β(n(k+1)).Case 3.
Ifn≡1(mod4) or n≡3(mod4)   and n∣τ,n∣u1,…,n∣uk-4, z4i=(1001), and z8i2+4i=(1001) for   i=βn. So, we get Pk=(Gn;x,y,z)=β(2n(k+1)) since i(2k+2)=β(2n(k+1)).This completes the proof.In the case of 2-generator the group has the presentation〈x,y:x2=y2=(xy)n=e〉 and the period is the same as in the 3-generator case and proof is similar.


## 3. The GroupsE(2,2,2),  E(n,2,2),  E(2,n,2), and E(2,2,n)

Definition 3.1.
Theextended triangle groupE(p,q,r), for p,q,r>1, is defined by the presentation
(3.1)〈x,y,z:x2=y2=z2=(xy)p=(yz)q=(zx)r=e〉.
The extended triangle groups are a very important class of groups closely linked to automorphism groups of regular maps, see [17]. The triangle groups (polyhedral groups), (p,q,r) are index two subgroups of extended  triangle groups. To see this, let X=xy,Y=yz and Z=zx in E(p,q,r) and then use the obvious epimorphism. We get the following three cases for E(p,q,r):(1)
the Euclidean case if1/p+1/q+1/r=1,(2)
the elliptic case if1/p+1/q+1/r>1,(3)
the hyperbolic case if1/p+1/q+1/r<1.The group E(p,q,r) is finite if and only if  1/p+1/q+1/r>1.
For more information on these groups, see [14, 18].Theorem 3.2.
LetE2 be the group defined by the presentation 〈x,y,z:x2=y2=z2=(xy)2=(yz)2=(zx)2=e〉. Then Pk(E2;x,y,z)=k+1 for k>2.Proof.
SinceE2 can be identified with Z2⊕Z2⊕Z2 and x,y,z with (1,0,0),(0,1,0),and(0,0,1), respectively, from a similar argument applied to Theorem 2.2, we get Pk(E2;x,y,z)=k+1.Theorem 3.3.
LetEn,n>2, be the group defined by the presentation 〈x,y,z:x2=y2=z2=(xy)2=(yz)2=(zx)n=e〉(i)
(3.2)P4,5(En;x,y,z)={n(k+12),n≡0mod4,n(k+1),n≡2mod4,2n(k+1),otherwise;(ii)
letk≥6.(1)
If  there is not∈[3,k-3] such that t is an odd factor of n, then
(3.3)Pk(En;x,y,z)={n(k+12),n≡0mod4,n(k+1),n≡2mod4,2n(k+1),otherwise.(2)
Letα be the biggest odd factor of n in [3,k-3]. Then two cases occur:
(i′)
ifα3j∉[3,k-3] for j∈N, then
(3.4)Pk(En;x,y,z)={α(n(k+12)),n≡0mod4,α(n(k+1)),n≡2mod4,α(2n(k+1)),otherwise;(ii′)
ifβ is be the biggest odd number which is in [3,k-3] and β=α3j for j∈N, then(3.5)Pk(Er;x,y,z)={β(n(k+12)),n≡0mod4,β(n(k+1)),n≡2mod4,β(2n(k+1)),otherwise.Proof.
Sincey has order 2 and commutes with x and z it follows that En=Z2⊕Dn. As a group of matrices, the can be identified with a group of 3×3 matrices of form
(3.6)(±100a),
where a is a 2×2 matrix in dihedral group generated by a and b shown at (2.14). Here,
(3.7)x=(1000cos(2πn)-sin(2πn)0-sin(2πn)-cos(2πn)),y=(-100010001),z=(10001000-1).
Now, since the period of a Fibonacci sequence in a direct product of groups is the least common multiple of the periods in each the factors and from a similar argument applied to Theorem 2.4 the proof is done.



---

*Source: 453750-2009-11-05.xml*