# A Method to Construct Generalized Fibonacci Sequences

Authors: Adalberto García-Máynez; Adolfo Pimienta Acosta
Journal: Journal of Applied Mathematics
 (2016)

---

## Abstract

The main purpose of this paper is to study the convergence properties of Generalized Fibonacci Sequences and the series of partial sums associated with them. When the proper values of ans×s real matrix A are real and different, we give a necessary and sufficient condition for the convergence of the matrix sequence A,A2,A3,… to a matrix B.


---

## Body

## 1. Introduction

The Fibonacci Sequence(1)0,1,1,2,3,5,8,13,21,… is an interesting numerical sequence that occurs quite frequently in many parts of nature. This sequence has a special feature; every element of this sequence, starting from the third, is the sum of its two predecessors and can be generated recursively by the formula(2)xn+2=xn+xn+1. It is clear that we need the first two terms x0=0,  x1=1 and the recursive formula to define the sequence.If we want to know the termxk without constructing the previous terms, we can use the unexplainable formula (see [1]):(3)xk=151+52k-1-52k. What do the irrational numbers 5 have to do with the original sequence?The so-calledGolden ratioλ=(1+5)/2 appears in nature very frequently. It is also considered the most esthetic ratio between the basis and height of a rectangle:(4)HBBH=1+52.If we replace the recursive formula by(5)2xn+2=xn+xn+1,we obtain a new sequence 0,1,1/2,3/4,5/8,11/16,21/32,… and this sequence is no longer divergent; in fact, it converges to 2/3.To define aGeneralized Fibonacci Sequence, we fix a natural number s and two elements(6)x0,x1,…,xs-1,a0,a1,…,as-1 in the Euclidean space Rs. The recursive formula is(7)xk+s=a0xk+a1xk+1+⋯+as-1xk+s-1.The main purpose of this paper is to study the convergence properties of Generalized Fibonacci Sequences and the series of partial sums associated with them. When the proper values of an s×s real matrix A are real and different, we give a necessary and sufficient condition for the convergence of the matrix sequence I,A,A2,A3,… to a matrix B: we say Ak→B if for every ordered pair (i,j), where i,j∈{1,2,…,s}, the sequence of the (i,j)-entries of Ak converges to the (i,j)-entry of B. As a particular case, we study when do we have the convergence of the powers φ,φ2,φ3,… of aMoebius transformation to a constant function.Then we would like to list the four published monographs about generalized Fibonacci sequences [1–4] and several more specialized articles [5–8].


## 2. Main Results

Consider a Generalized Fibonacci Sequence (GFS) with initial termsx0,x1,…,xs-1 and recursive formula (7). Define the matrices s×s:(8)C=010⋯0001⋯0⋮⋮⋮⋮⋮000⋯1a0a1a2⋯as-1,Dk=xkxk+1⋯xk+s-1xk+1xk+2⋯xk+s⋮⋮⋮⋮xk+s-1xk+s⋯xk+2s-2,k∈N∪0.The characteristic polynomial of the matrix C is(9)φx=xs-as-1xs-1-as-2xs-2-⋯-a0.Suppose all the roots λ1,λ2,…,λs of φ(x) are real and pairwise different; that is, λi≠λj, for i≠j. ConsiderVandermonde's matrix:(10)V=11⋯1λ1λ2⋯λsλ12λ22⋯λs2⋮⋮⋮⋮λ1s-1λ2s-1⋯λss-1.Since V=±∏1≤i<j≤s(λi-λj), we deduce that V≠0 and, hence, V is invertible. We need the following matrix relation.Theorem 1.
Vand C are related by the following formula:(11)VEV-1=C,where E is the diagonal matrix:(12)E=λ10⋯00λ2⋯0⋮⋮⋱⋮00⋯λs.Proof.
Letv1,v2,…,vs∈Rs be the proper vectors of the matrix C. We have then viC=λivi for each i=1,2,…,s. If w=v1+v2+⋯+vs and k∈N, we have wCk=λ1kv1+λ2kv2+⋯+λskvs,  k=0,1,…,s-1. Since V≠0, we deduce that the vectors w,wC,wC2,…,wCs-1 are linearly independent and hence they constitute a basis for Rs. Calling B={v1,v2,…vs}, B'={w,wC,…,wCs-1}, we have V=m(Id,B',B). On the other hand, consider the linear transformation T:Rs→Rs defined by the formula T(v)=vC. Clearly,(13)C=mT,B',B'. Therefore,(14)C=mT,B′,B′=mId,B′,BmT,B,BmId,B,B′=VEV-1.In the next theorem, we relateV and C with Dk.Theorem 2.
One has the following formulas:(a)
CDk=Dk+1 and CkD0=Dk  for every k∈N.(b)
Dk=VEkV-1D0  for every k∈N.Proof.
(a) It is straightforward.
(b) Using (36), we have(15)Dk=CkD0=VEV-1kD0=VEkV-1D0.Using the formulaDk=VEkV-1D0, we obtain any member of the corresponding Generalized Fibonacci Sequence.Theorem 3.
Consider(16)xk=-1s-1Vλ1kλ2k⋯λsk011⋯1x0λ1λ2⋯λsx1⋮⋮⋱⋮⋮λ1s-1λ2s-1⋯λss-1xs-1.Proof.
The first row of the matrixVEk is the following: (λ1k,λ2k,…,λsk). The first column of the matrix V-1D0 is(17)1V∑j=1sVj1xj-1∑j=1sVj2xj-1⋮∑j=1sVjsxj-1,where Vij is the cofactor of the entry of V in the (i,j) position. xk is the entry in the (1,1) position of the matrix Dk. Therefore,(18)xk=1Vλ1k∑j=1sVj1xj-1+λ2k∑j=1sVj2xj-1+⋯+λsk∑j=1sVjsxj-1.The expression inside the square brackets coincides with(19)-1s-1λ1kλ2k⋯λsk011⋯1x0λ1λ2⋯λsx1⋮⋮⋮⋮⋮λ1s-1λ2s-1⋯λss-1xs-1.To see this, develop this determinant by the first row and the last column. The coefficient of λikxj-1 is then(20)-1i-1-1s+j11⋯11λ1⋯λi-1λi+1⋯λs⋮⋮⋮⋮⋮λ1j-1⋯λi-1j-1λi+1j-1⋯λsj-1λ1j+1⋯λi-1j+1λi+1j+1⋯λsj+1⋮⋮⋱⋮⋮λ1s-1⋯λi-1s-1λi+1s-1⋯λss-1=-1s-1Vji. This completes the proof.In the particular casek=2, we obtain(21)xk=-1λ2-λ1λ1kλ2k011x0λ1λ2x1.If we further assume that x0=0 and x1=1, we obtain(22)xk=1λ1-λ2λ1k-λ2k.In the original Fibonacci sequence, we have(23)C=0111 and hence φ(x)=x2-x-1. The roots of this polynomial are λ1=(1+5)/2 and λ2=(1-5)/2. We justify then the mythical formula xk=(1/5)1+5/2k-1-5/2k.In the casea0=a1=1/2, we obtain(24)C=011212,φx=x-1-12x-12=x2-12x-12.The roots of φ(x) are λ1=1 and λ2=-1/2. Hence, xk=(2/3)1--1/2k. It is now clear that this last GFS converges to 2/3.We give next a sufficient condition for the convergence of the series of a GFS.Theorem 4 (main theorem).
Suppose the roots of the characteristic polynomialφ(x) of a GFS {xk} are pairwise different and all of them lie in the open interval (-1,1). Then the series of {xk} converges to(25)-1s-1V11-λ111-λ2⋯11-λs011⋯1x0λ1λ2⋯λsx1⋮⋮⋮⋮⋮λ1s-1λ2s-1⋯λss-1xs-1.Proof.
This is a consequence of the identity(26)x0+x1+⋯+xk=-1s-1V1+λ1+λ12+⋯+λ1k-1⋯1+λs+λs2+⋯+λsk-101⋯1x0λ1⋯λsx1⋮⋮⋮⋮λ1s-1⋯λss-1xs-1and the convergence ∑j=0∞λij to 1/(1-λi).We give now two examples.Example 5.
One hass=3, x0=x1=0, x2=1, a0=1/6, a1=-1, and a2=11/6.
The characteristic polynomialφ(x) of the corresponding GFS is(27)φx=x-100x-1-161x-116=x3-116x2+x-16=x-1x-12x-13. Therefore, λ1=1,  λ2=1/2,  λ3=1/3, and(28)V=1111121311419=-118. Hence(29)xk=-13-1-1812-k3-k01110112130114191=-1812-k3-k11111213. Clearly(30)xk⟶-1810011111213=3.Example 6.
One hass=3,  x0=x1=0,  x2=1,  a0=1/18,  a1=-11/8,  and a2=3/2. In this case, φ(x)=x3-(3/2)x2+(11/18)x-1/18=(x-1/2)(x-1/3)(x-2/3). Therefore, λ1=1/2,  λ2=1/3,  λ3=2/3, and V=-1/108. Hence,(31)
x
k
=
-
108
1
2
k
1
3
k
2
3
k
0
1
1
1
0
1
2
1
3
2
3
0
1
4
1
9
4
9
1
.In this case, xk→0, but(32)
∑
k
=
1
∞
x
k
=
-
108
1
1
-
1
/
2
1
1
-
1
/
3
1
1
-
2
/
3
0
1
1
1
0
1
2
1
3
2
3
0
1
4
1
9
4
9
1
=
9
.
Givens different real numbers λ1,λ2,λ2,…,λs, we may construct, for every (x0,x1,…,xs-1)∈Rs, a GFS; namely,(33)xk=-1s-1∏1≤j<i≤sλi-λjλ1kλ2k⋯λsk011⋯1x0λ1λ2⋯λsx1⋮⋮⋱⋮⋮λ1s-1λ2s-1⋯λss-1xs-1. The missing sequence (a0,a1,…,as-1) may be obtained from the coefficients of the polynomial:(34)φx=x-λ1x-λ2⋯x-λs. For instance, as-1=λ1+λ2+⋯+λs and as-2=-∑1≤j<i≤sλiλj.With the help of this remark, we prove the following.Theorem 7.
Let(aij) be an invertible s×s matrix. Suppose the characteristic polynomial φ(x) of A factors into the form:(35)φx=x-λ1x-λ2⋯x-λs,where λ1,λ2,…,λs are pairwise different real numbers. Let aij(k) be the entry in the (i,j) position of the matrix Ak. Then(36)aijk=-1s-1Vλ1kλ2k⋯λsk011⋯1aij0λ1λ2⋯λsaij1λ12λ22⋯λs2aij2⋮⋮⋮⋮⋮λ1s-1λ2s-1⋯λss-1aijs-1.Proof.
Let(xk) be the GFS determined by (36). It is clear that xk=aij(k) for k≤s-1. Proceeding by induction, suppose xt=aij(t) for every t≤k, where k≥s-1. We clearly have(37)aijk+1=ai1k,ai2k,…,aisk·a1j1,a2j1,…,asj1=ai1ka1j+ai2ka2j+⋯+aiskasj.Be induction, the terms ai1(k),…,ais(k) may be obtained using determinants of type (36). We consider the last columns of determinants (36) and we obtain(38)a1j0ai10ai11⋮ai1s-1+a2j0ai20ai21⋮ai2s-1+⋯=0aij1aij2⋮aijs.
Therefore(39)aijk+1=-1s-1Δλ1kλ2k⋯λsk011⋯1aij1λ1λ2⋯λsaij2λ12λ22⋯λs2aij3⋮⋮⋮⋮⋮λ1s-1λ2s-1⋯λss-1aijs.The GFS on the right side of this equation starts with y0=aij(1),  y1=aij(2),…,ys-1=aij(s) and has the same proper values of the GFS (xk). Hence aij(k+1)=yk=xk+1 and the proof is complete.As an exercise, we calculate the powers of a2×2 matrix:(40)A=abhk,whereΔ=ak-hb≠0. In this case we have a11(0)=1, a12(0)=0, a21(0)=0, a22(0)=1, a11(1)=a, a12(1)=b, a21(1)=h, a22(1)=k. Hence(41)aijt=-111λ1λ2λ1tλ2t011aij0λ1λ2aij1. Therefore(42)a11t=1λ1-λ2λ1tλ2t0111λ1λ2a;a12t=1λ1-λ2λ1tλ2t0110λ1λ2b;a21t=1λ1-λ2λ1tλ2t0110λ1λ2h;a22t=1λ1-λ2λ1tλ2t0111λ1λ2k,where λ1=1/2a+k-(a-k)2+4hb and λ2=(1/2)a+k+(a-k)2+4hb. If λ1=1 and |λ2|<1, we have(43)At⟶11-λ2a-λ2bhk-λ2. This limit matrix has determinant =0. So in the case of a Moebius transformation(44)φz=a+bzh+kz,ak≠hb we have the following corollary.Corollary 8.
If 1 is a proper value of the matrixA=abhk and if  ak-hb<1, then the powers φt converge to the constant map ϕ(z)=(a-λ2)/h(1-λ2)=b/(1-λ2)(k-λ2).



---

*Source: 4971594-2016-02-14.xml*