# On Period of the Sequence of Fibonacci Polynomials Modulom

Authors: İnci Gültekin; Yasemin Taşyurdu
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

It is shown that the sequence obtained by reducing modulom coefficient and exponent of each Fibonacci polynomials term is periodic. Also if p is prime, then sequences of Fibonacci polynomial are compared with Wall numbers of Fibonacci sequences according to modulo p. It is found that order of cyclic group generated with Q2 matrix (x110) is equal to the period of these sequences.


---

## Body

## 1. Introduction

In modern science there is a huge interest in the theory and application of the Fibonacci numbers. The Fibonacci numbersFn are the terms of the sequence 0,1,1,2,3,5,…, where Fn=Fn-1+Fn-2,  n≥2, with the initial values F0=0 and F1=1. Generalized Fibonacci sequences have been intensively studied for many years and have become an interesting topic in Applied Mathematics. Fibonacci sequences and their related higher-order sequences are generally studied as sequence of integer. Polynomials can also be defined by Fibonacci-like recurrence relations. Such polynomials, called Fibonacci polynomials, were studied in 1883 by the Belgian mathematician Eugene Charles Catalan and the German mathematician E. Jacobsthal. The polynomials Fn(x) studied by Catalan are defined by the recurrence relation
(1)Fn(x)=xFn-1(x)+Fn-2(x),n≥3,
where F1(x)=1, F2(x)=x. The Fibonacci polynomials studied by Jocobstral are defined by
(2)Jn(x)=Jn-1(x)+xJn-2(x),n≥3,
where J1(x)=J2(x)=1. The Fibonacci polynomials studied by P. F. Byrd are defined by
(3)φn(x)=2xφn-1(x)+φn-2(x),n≥2,
where φ0(x)=0, φ1(x)=1. The Lucas polynomials Ln(x), originally studied in 1970 by Bicknell and they are defined by
(4)Ln(x)=xLn-1(x)+Ln-2(x),n≥2,
where L0(x)=2, L1(x)=x [1].Hoggatt and Bicknell introduced a generalized Fibonacci polynomials and their relationship to diagonals of Pascal’s triangle [2]. Also after investigating the generalized Q-matrix, Ivie introduced a special case [3]. Nalli and Haukkanen introduced h(x)-Fibonacci polynomials that generalize both Catalan’s Fibonacci polynomials and Byrd’s Fibonacci Polynomials and the k-Fibonacci number. Also they provided properties for these h(x)-Fibonacci polynomials where h(x) is a polynomial with real coefficients [1].Definition 1.
The Fibonacci polynomials are defined by the recurrence relation(5)Fn(x)={0,ifn=0,1,ifn=1,xFn-1(x)+Fn-2(x),ifn≥2,
that the Fibonacci polynomials are generated by a matrix Q2,
(6)Q2=(x110),Q2n=(Fn+1(x)Fn(x)Fn(x)Fn-1(x))
can be verified quite easily by mathematical induction. The first few Fibonacci polynomials and the array of their coefficients are shown in Table 1 [2].Table 1
Fibonacci polynomials
Coefficient array
F
0
(
x
)
=
0
0
F
1
(
x
)
=
1
1
F
2
(
x
)
=
x
1
F
3
(
x
)
=
x
2
+
1
1
1
F
4
(
x
)
=
x
3
+
2
x
1
2
F
5
(
x
)
=
x
4
+
3
x
2
+
1
1
3
1
F
6
(
x
)
=
x
5
+
4
x
3
+
3
x
1
4
3
F
7
(
x
)
=
x
6
+
5
x
4
+
6
x
2
+
1
1
5
6
1
⋮
⋮
⋮
⋮
⋮A sequence isperiodic if, after a certain point, it consists of only repetitions of a fixed subsequence. The number of elements in the repeating subsequence is called the period of the sequence. For example, the sequence a,b,c,d,e,b,c,d,e,b,c,d,e,…, is periodic after the initial element a and has period 4. A sequence is simplyperiodic with period k if the first k elements in the sequence form a repeating subsequence. For example, the sequence a,b,c,d,a,b,c,d,a,b,c,d,…, is simply periodic with period 4 [4]. The minimum period length of (Fimodn)i=-∞∞ sequence is stated by k(n) and is named Wall number of n [5].Theorem 2.
k
(
n
) is an even number for n≥3 [5].


## 2. The Generalized Sequence of Fibonacci Polynomials Modulom

Reducing the generalized sequence of coefficient and exponent of each Fibonacci polynomials term by a modulusm, we can get a repeating sequence, denoted by
(7){F(x)m}={F0(x)m,F1(x)m,…,Fn(x)m,…},
where Fi(x)m=Fn(x)(modm). Let hF(x)m denote the smallest period of {F(x)m}, called the period of the generalized Fibonacci polynomials modulo m.Theorem 3.
{
F
(
x
)
m
}  is a periodic sequence.Proof.
LetS2={(x1,x2):1≤xi≤2} where xi is reduction coefficient and exponent of each term in Fn(x) polynomials modulo m. Then, we have |S2|=(mm)2 being finite, that is, for any i>j, there exist natural numbers i and j(8)Fi+1(x)m=Fj+1(x)m,Fi+2(x)m=Fj+2(x)m,…,Fi+k(x)m=Fj+k(x)m.
By definition of the generalized Fibonacci polynomials we have that Fi(x)m=xFi-1(x)m+Fi-2(x)m and Fj(x)m=xFj-1(x)m+Fj-2(x)m. Hence, Fi(x)m=Fj(x)m, and then it follows that
(9)Fi-1(x)m=Fj-1(x)m,Fi-2(x)m=Fj-2(x)m,…,Fi-j(x)m=Fj-j(x)m=F0(x)m
which implies that the {F(x)m} is a periodic sequence.Example 4.
Form=2, {F(x)2} sequence is F0(x)2=0, F1(x)2=1, F2(x)2=x, F3(x)2=x2+1=x0+1=2=0,  F4(x)2=0x+x=x, F5(x)2=x2+0=x0+0=1, F6(x)2=x+x=2x=0, F7(x)2=0x+1=1. We have{F(x)2}={0,1,x,0,x,1,0,1,…}, and then repeat. So, we get hF(x)2=6.Given a matrixA=(hij(x)) where hij(x)’s being polynomials with real coefficients, A(modm) means that every entry of A is modulo m, that is, A(modm)=(hij(x)(modm)). Let 〈Q2〉m={Q2i(modm)∣i≥0} be a cyclic group and |〈Q2〉m| denote the order of 〈Q2〉m whereQ2i(modm) is reduction coefficient and exponent of each polynomial in Q2i matrix modulo m.Theorem 5.
One hashF(x)m=|〈Q2〉m|.Proof.
Proof is completed if it is thathF(x)m is divisible by |〈Q2〉m| and that |〈Q2〉m| is divisible by hF(x)m. Fibonacci polynomials are generated by a matrix Q2,
(10)Q2=(x110),Q2n=(Fn+1(x)Fn(x)Fn(x)Fn-1(x)).
Thus, it is clear that |〈Q2〉m| is divisible by hF(x)m. Then we need only to prove that hF(x)m is divisible by |〈Q2〉m|. Let hF(x)m=t. It is seen that Q2t=(Ft+1(x)Ft(x)Ft(x)Ft-1(x)). Hence Q2t=I(modm). We get that |〈Q2〉m| is divisible by t. That is, hF(x)m is divisible by |〈Q2〉m|. So, we get hF(x)m=|〈Q2〉m|.Theorem 6.
h
F
(
x
)
p
=
p
k
(
p
) where p is a prime number.Proof.
It is completed if it is thathF(x)p is divisible by pk(p) and that pk(p) divisible by hF(x)p. From Theorem 5  Q2n=(Fn+1(x)Fn(x)Fn(x)Fn-1(x)),  Q2hF(x)p=I(modp) for Q2=(x110). Also, Q2pk(p)=(Fpk(p)+1(x)Fpk(p)(x)Fpk(p)(x)Fpk(p)-1(x)). So, we get Q2pk(p)=I(modp). Thus pk(p) is divisible by hF(x)p.  Moreover pk(p) is divisible by hF(x)p. Since |〈Q2〉p|=hF(x)p, hF(x)p is divisible by pk(p). Therefore hF(x)p=pk(p).Theorem 7.
h
F
(
x
)
p is an even number where p is a prime number.Proof.
It has been shown thathF(x)p=pk(p) in Theorem 6. If it is stated that pk(p) is an even number then proof is completed. By Theorem 2, k(p) is an even number and p is an even number for p≥3. Hence pk(p) is always an even number. That is, hF(x)p is an even number.
Table2 shows some periods of sequence of coefficient and exponent of Fibonacci polynomials modulo, which is a prime number, by using k(p).Table 2
Periods of the sequence of Fibonacci polynomials modulop.
p
k
(
p
)
h
F
(
x
)
p
Result
2
3
6
h
F
(
x
)
2
=
2
k
(
2
)
7
16
112
h
F
(
x
)
7
=
7
k
(
7
)
37
76
2812
h
F
(
x
)
37
=
37
k
(
37
)
103
208
21424
h
F
(
x
)
103
=
103
k
(
103
)
181
90
16290
h
F
(
x
)
181
=
181
k
(
181
)
241
240
57840
h
F
(
x
)
241
=
241
k
(
241
)
373
748
279004
h
F
(
x
)
373
=
373
k
(
373
)
653
1308
854124
h
F
(
x
)
653
=
653
k
(
653
)
853
1708
1456924
h
F
(
x
)
853
=
853
k
(
853
)



---

*Source: 731482-2013-03-11.xml*