# A Matrix Approach for Divisibility Properties of the Generalized Fibonacci Sequence

Authors: Aynur Yalçiner
Journal: Discrete Dynamics in Nature and Society
 (2013)

---

## Abstract

We give divisibility properties of the generalized Fibonacci sequence by matrix methods. We also present new recursive identities for the generalized Fibonacci and Lucas sequences.


---

## Body

## 1. Introduction

The generalized Fibonacci sequence{Un} and the generalized Lucas sequence {Vn} are defined for n>1, by,
(1)Un=pUn-1+Un-2,Vn=pVn-1+Vn-2,
where U0=0, U1=1 and V0=2,V1=p, respectively.Letα and β be the roots of the equation x2-px-1=0. Then the Binet formulas of the sequences {Un} and {Vn} are given by
(2)Un=αn-βnα-β,Vn=αn+βn.
If p=1, then Un=Fn (nth Fibonacci number) and Vn=Ln (nth Lucas number).It is a well-known fact that(3)gcd(Fn,Fm)=Fgcd(n,m).
It is also known that Fkn is a multiple of Fn, for all integers k and n. In [1], the author showed that, for n>2, the Fibonacci number Fm is a multiplication of Fn2 if and only if m is multiplication of nFn (for more details see [2]). Also, in [3], the author obtained the following divisibility properties:(i)
Fkn-1-Fn-1k is divisible by Fn2;(ii)
Fkn-2-(-1)k+1Fn-2k is divisible by Fn2,where n,k≥1. Kiliç [4] generalized these results for a general second-order linear recursion {Un} as follows:
(4)Urk-1Ukn-r-(-1)(r-1)(k+1)Un-rkisdivisiblebyUn2.In this paper, we investigate divisibility properties of the generalized Fibonacci numbers byUnl, where l≥3. For l=3, we show that
(5)U2k-2Ukn-3-U2k-2Un-1k+(-1)k-1Un-2kisdivisiblebyUn3.
We use matrix methods to prove the claim. We recall that matrix methods are useful tools for deriving some properties of linear recurrences (see [4–9]). We consider the quotient
(6)U2k-2Ukn-3-U2k-2Un-1k+(-1)k-1Un-2kUn3
for all positive integers n and k. We define a generating matrix for this quotient for fixed n and increasing values of k. Then we give an explicit statement for the quotient. Also, by considering this explicit statement, we find new recursive identities for the general second-order linear recurrences. Finally, we give divisibility properties of the generalized Fibonacci numbers in the case l>3. Thus we obtain a generalization of the results given in [4].


## 2. Main Results

We denote the quotient(U2k-2Ukn-3-U2k-2Un-1k+(-1)k-1Un-2k)/Un3 by s(n,k).Define a second-order linear sequence{An}, for n>1,
(7)An=pAn-1+An-2
with initial conditions A0=p2-1 and A1=p3+3p.By the definitions of{Un} and {An}, we have
(8)An=U2Vn+1+U2Un-Un-1.Define a matrixH(n) by
(9)H(n)=[An-1BnCn(-1)nU23Un-1Un-2100001000010],
where
(10)Bn=(U2Un-2-U22Un-1)Vn+Un-12-Un-22+(-1)n+1U3,Cn=-U22Un-1Un-2Vn+(-1)n+1U22Un-2+(-1)nU23Un-1.We next define a matrixG(n,k) of order 4 as follows: (11)G(n,k)=[s(n,k+3)t(n,k+3)y(n,k+3)(-1)nU23Un-1Un-2s(n,k+2)s(n,k+2)t(n,k+2)y(n,k+2)(-1)nU23Un-1Un-2s(n,k+1)s(n,k+1)t(n,k+1)y(n,k+1)(-1)nU23Un-1Un-2s(n,k)s(n,k)t(n,k)y(n,k)(-1)nU23Un-1Un-2s(n,k-1)].t
(
n
,
k
) and y(n,k) are given by
(12)t(n,k)=[-U2k-2Un-1Un-2δnUkn+(-1)n+1U2k-2(U2Un-1δn+Un-22)Un(k-1)+(-1)3nU2kUn(k-3)+U2k-2Un2(2(-1)nU-n+2+Un+2)Un-1k+(-1)kU2Un2(2(-1)nU-n+1+Un+1)Un-2k]×(Un5)-1,y(n,k)=[-U2k-1Un-12Un-22Ukn+U2k-1(U2Un-1δn+Un-22)Un(k-2)+(-1)3n+1U2kδnUn(k-3)+Un2(2(-1)n+1U2+U2n-2)Un-1k+(-1)kU22Un2(2(-1)n+1-U2n-1)Un-2k]×(Un5)-1,
where
(13)δn=U2Un-1-Un-2.
Thus we give our first main result.Theorem 1.
Forn≥1,
(14)H(n)k=G(n,k).Proof.
We will use induction onk. The result is clear for k=1. Now assume that H(n)k-1=G(n,k-1). Then, by the definitions of s(n,k),t(n,k), and y(n,k), we have
(15)An-1s(n,k+2)+t(n,k+2)=s(n,k+3),Bns(n,k+2)+y(n,k+2)=t(n,k+3),Cns(n,k+2)+(-1)nU23Un-1Un-2s(n,k+1)=y(n,k+3).
Thus the proof is complete.As a consequence of this theorem, we can see that matrixH(n) generates s(n,k). Since the elements of H(n) are integers, the quotient s(n,k) are integers for all positive integers n and k.Lemma 2.
Forn≥1, the eigenvalues of H(n) are U2αn, U2βn, U2Un-1, and -Un-2.Proof.
The characteristic polynomial ofH(n) is
(16)x4-An-1x3-Bnx2-Cnx+(-1)n+1U23Un-1Un-2=0,
and it is factorized as
(17)(x-U2αn)(x-U2βn)(x-U2Un-1)(x+Un-2)=0,
which completes the proof.As another main result, we have the following theorem.Theorem 3.
Forn,k≥1,
(18)(G(n,k))4,1=s(n,k)=(U2k-2Un-1Un-2Ukn+(-1)nU2k-2δnUn(k-1)-U2k-1Un(k-2)-U2k-2Un2Un-1k+(-1)k-1Un2Un-2k)×(Un5)-1,
where δn is defined as shown previously.Proof.
Since the eigenvalues ofH(n) are distinct, H(n) is diagonalizable as
(19)V-1H(n)V=D,
where
(20)V=[U23α3nU23β3nU23Un-13-Un-23U22α2nU22β2nU22Un-12Un-22U2αnU2βnU2Un-1-Un-21111]
and D=diag(U2αn,U2βn,U2Un-1,-Un-2). Therefore, we obtain V-1H(n)kV=Dk. By Theorem 1, we write V-1G(n,k)V=Dk. Then we have the following linear equation system:
(21)gi1U23α3n+gi2U22α2n+gi3U2αn+gi4=U2k-i+4α(k-i+4)n,gi1U23β3n+gi2U22β2n+gi3U2βn+gi4=U2k-i+4β(k-i+4)n,gi1U23Un-13+gi2U22Un-12+gi3U2Un-1+gi4=U2k-i+4Un-1k-i+4,-gi1Un-23+gi2Un-22-gi3Un-2+gi4=(-1)k-i+4Un-2k-i+4.
The solution of the above linear equation system gives the claimed result.By considering the definition ofs(n,k), we have the following consequence of Theorem 3.Corollary 4.
Forn,k≥1,
(22)Un-1Un-2Ukn=Un2Ukn-3+(-1)n+1δnUn(k-1)+U2Un(k-2).The next results generalize the result given by Corollary4.Theorem 5.
For all integersr,
(23)Un-rUn-r-1Ukn=Un2Ukn-2r-1+(-1)n+r(Ur+1Un-r-UrUn-r-1)Un(k-1)+UrUr+1Un(k-2),Un-rUn-r-1Vkn=Un2Vkn-2r-1+(-1)n+r(Ur+1Un-r-UrUn-r-1)Vn(k-1)+UrUr+1Vn(k-2).Proof.
The proof can be seen by the Binet formulas of the sequences{Un} and {Vn}.Forl=3, we give the general case of divisibility properties in the following result.Corollary 6.
For all integersr,
(24)Urk-2Ur+1k-2Ukn-2r-1-(-1)k(r-1)Ur+1k-2Un-rk+(-1)kr-1Urk-2Un-r-1k
is divisible by Un3.


## 3. Generalization of the Divisibility Properties

In this section, for a positive integerl, we generalize divisibility properties. For this purpose we introduce some new notations.Letri be an integer for i=1,…,l-1. Let
(25)ξ1={∑‍1≤i≤mri,m≡1(mod2),∑‍1≤i≤m-1ri,m≡0(mod2),ξ2={∑‍1≤i≤m-1ri,m≡1(mod2),∑‍1≤i≤mri,m≡0(mod2),φ=∑1≤i≤l-1ri,γ=∏1≤j<i≤l-1Uri-rj.
We denote the above product by γm for i,j≠m.Corollary 7.
(a) For an even positive integerl,
(26)(∏1≤i≤l-1Uri)k-l+1γUkn-φ+∑1≤m≤l-1(-1)k(rm-1)+m+ξ1+1γmUn-rmk(∏1≤i≤l-1m≠iUri)k-l+1
is divisible by γUnl.
(b) For an odd positive integerl,
(27)(∏1≤i≤l-1Uri)k-l+1γUkn-φ+∑1≤m≤l-1(-1)k(rm-1)+m+ξ2γmUn-rmk(∏1≤i≤l-1m≠iUri)k-l+1
is divisible by γUnl.As an example, if we takel=4, r1=1, r2=2, r3=3, and p=1, then
(28)F3k-3Fkn-6-F3k-3Fn-1k+(-1)kF3k-3Fn-2k+Fn-3kisdivisiblebyFn4.



---

*Source: 829535-2013-05-26.xml*