# On Sequences of Numbers and Polynomials Defined by Linear Recurrence Relations of Order 2

Authors: Tian-Xiao He; Peter J.-S. Shiue
Journal: International Journal of Mathematics and Mathematical Sciences
 (2009)

---

## Abstract

Here we present a new method to construct the explicit formula of a sequence of numbers and polynomials generated by a linear recurrence relation of order 2. The applications of the method to the Fibonacci and Lucas numbers, Chebyshev polynomials, the generalized Gegenbauer-Humbert polynomials are also discussed. The derived idea provides a general method to construct identities of number or polynomial sequences defined by linear recurrence relations. The applications using the method to solve some algebraic and ordinary differential equations are presented.


---

## Body

## 1. Introduction

Many number and polynomial sequences can be defined, characterized, evaluated, and classified by linear recurrence relations with certain orders. A number sequence{an} is called sequence of order 2 if it satisfies the linear recurrence relation of order 2:(1.1)an=pan-1+qan-2,n≥2,
for some nonzero constants p and q and initial conditions a0 and a1. In Mansour [1], the sequence {an}n≥0 defined by (1.1) is called Horadam’s sequence, which was introduced in 1965 by Horadam [2]. The work in [1] also obtained the generating functions for powers of Horadam’s sequence. To construct an explicit formula of its general term, one may use a generating function, characteristic equation, or a matrix method (see Comtet [3], Hsu [4], Strang [5], Wilf [6], etc.) In [7], Benjamin and Quinn presented many elegant combinatorial meanings of the sequence defined by recurrence relation (1.1). For instance, an counts the number of ways to tile an n-board (i.e., board of length n) with squares (representing 1ss) and dominoes (representing 2s) where each tile, except the initial one has a color. In addition, there are p colors for squares and q colors for dominoes. In this paper, we will present a new method to construct an explicit formula of {an} generated by (1.1). The key idea of our method is to reduce the relation (1.1) of order 2 to a linear recurrence relation of order 1:(1.2)an=can-1+d,n≥1,
for some constants c≠0 and d and initial condition a0 via geometric sequence. Then, the expression of the general term of the sequence of order 2 can be obtained from the formula of the general term of the sequence of order 1:(1.3)an={a0cn+dcn-1c-1,ifc≠1;a0+nd,ifc=1.
The method and some related results on the generalized Gegenbauer-Humbert polynomial sequence of order 2 as well as a few examples will be given in Section 2. Section 3 will discuss the application of the method to the construction of the identities of sequences of order 2. There is an extension of the above results to higher order cases. In Section 4, we will discuss the applications of the method to the solution of algebraic equations and initial value problems of second-order ordinary differential equations.


## 2. Main Results and Examples

Letα and β be two roots of of quadratic equation x2-px-q=0. We may write (1.1) as(2.1)an=(α+β)an-1-αβan-2,
where α and β satisfy α+β=p and αβ=-q. Therefore, from (2.1), we have(2.2)an-αan-1=β(an-1-αan-2),
which implies that {an-αan-1}n≥1 is a geometric sequence with common ratio β. Hence,(2.3)an-αan-1=(a1-αa0)βn-1,an=αan-1+(a1-αa0)βn-1.
Consequently,(2.4)anβn=αβ(an-1βn-1)+a1-αa0β.
Let bn:=an/βn. We may write (2.4) as(2.5)bn=αβbn-1+a1-αa0β.
If α≠β, by using (1.3), we immediately obtain(2.6)anβn=a0(αβ)n+a1-αa0β(α/β)n-1(α/β)-1=1βn[αna0+a1-αa0α-β(αn-βn)],
which yields(2.7)an=(a1-βa0α-β)αn-(a1-αa0α-β)βn.
Similarly, if α=β, then (1.3) implies(2.8)an=a0αn+nαn-1(a1-αa0)=na1αn-1-(n-1)a0αn.We may summarize the above result as follows.Proposition 2.1.
Let{an} be a sequence of order 2 satisfying linear recurrence relation (2.1). Then
(2.9)an={(a1-βa0α-β)αn-(a1-αa0α-β)βn,ifα≠β;na1αn-1-(n-1)a0αn,ifα=β.In particular, if{an} satisfies the linear recurrence relation (1.1) with q=1, namely,(2.10)an=pan-1+an-2,
then the equation x2-px-1=0 has two solutions:(2.11)α=p+p2+42,β=-1α=p-p2+42.
From Proposition 2.1, we have the following corollary.Corollary 2.2.
Let{an} be a sequence of order 2 satisfying the linear recurrence relation an=pan-1+an-2. Then
(2.12)an=2a1-(p-p2+4)a02p2+4αn-2a1-(p+p2+4)a02p2+4(-1α)n,
where α is defined by (2.11).
Similarly, let{an} be a sequence of order 2 satisfying the linear recurrence relation an=an-1+qan-2. Then
(2.13)an={2a1-(1-4q+1)a024q+1α1n-2a1-(1+4q+1)a024q+1α2n,ifq≠-14;12n(2na1-(n-1)a0),ifq=-14,
where α1=(1/2)(1+4q+1) and α2=(1/2)(1-4q+1) are solutions of the equation x2-x-q=0.The first special case (2.12) was studied by Falbo in [8]. If p=1, the sequence is clearly the Fibonacci sequence. If p=2 (q=1), the corresponding sequence is the sequence of numerators (when two initial conditions are 1 and 3) or denominators (when two initial conditions are 1 and 2) of the convergent of a continued fraction to 2: {1/1, 3/2, 7/5,17/12,41/29,…}, called the closest rational approximation sequence to 2. The second special case is also a corollary of Proposition 2.1. If q=2 (p=1), {an} is the Jacobsthal sequence (see Bergum et al. [9]).Remark 2.3.
Proposition2.1 can be extended to the linear recurrence relations of order 2 with more general form: an=pan-1+qan-2+ℓ for p+q≠1. It can be seen that the above recurrence relation is equivalent to the form (1.1) bn=pbn-1+qbn-2, where bn=an-k and k=ℓ/(1-p-q).
We now show some examples of the applications of our method including the presentation of much easier proofs of some well-known formulas of the sequences of order2.Remark 2.4.
Denote(2.14)un=[an+1αn],A=[pq10].
We may write relation an=pan-1+qan-2 and an-1=an-1 into a matrix form un-1=Aun-2 with respect to 2×2 matrix A defined above. Thus un-1=An-1u0. To find explicit expression of un-1, the real problem is to calculate An-1. The key lies in the eigenvalues and eigenvectors. The eigenvalues of A are precisely α and β, which are two roots of the characteristic equation x2-px-q=0 for the matrix A. However, an obvious identity can be obtained from (un,un-1)=An-1(u1,u0) by taking determinants on the both sides: an+1an-1-an2=(-q)n-1(a2a0-a12) (see, e.g., [5] for more details).Example 2.5.
Let{Fn}n≥0 be the Fibonacci sequence with the linear recurrence relation Fn=Fn-1+Fn-2, where F0 and F1 are assumed to be 0 and 1, respectively. Thus, the recurrence relation is a special case of (1.1) with p=q=1 and the special case of the sequence in Corollary 2.2, which can be written as (2.1) with
(2.15)α=1+52,β=1-52.
Since α-β=5, from (2.12) we have the expression of Fn as follows:
(2.16)Fn=15{(1+52)n-(1-52)n}.Example 2.6.
We have mentioned above that the denominators of the closest rational approximation to2 form a sequence satisfying the recurrence relation an=2an-1+an-2. With an additional initial condition 0, the sequence becomes the Pell number sequence: {pn=0,1,2,5,12,29,…}, which also satisfies the recurrence relation pn=2pn-1+pn-2. Using formula (2.23) in Corollary 2.2, we obtain the general term of the Pell number sequence:
(2.17)pn=122{(1+2)n-(1-2)n}.
The numerators of the closest rational approximation to 2 are half the companion Pell numbers or Pell-Lucas numbers. By adding in initial condition 2, we obtain the Pell-Lucas number sequence {cn=2,2,6,14,34,82,…}, which satisfies cn=2cn-1+cn-2. Similarly, Corollary 2.2 gives
(2.18)cn=(1+2)n+(1-2)n.
We now consider the sequence of the sums of Pell number: {σn=0,1,3,8,20,…}, which satisfies the recurrence relation
(2.19)σn=2σn-1+σn-2+1.
From Remark 2.3, the above expression can be transfered to an equivalent form
(2.20)bn=2bn-1+bn-2,
where bn=σn+1/2. Using Corollary 2.2, one easily obtain
(2.21)bn=14{(1+2)n+1+(1-2)n+1}.
Thus,
(2.22)σn=14{(1+2)n+1+(1-2)n+1}-12.
If the coefficients of the linear recurrence relation of a function sequence{an(x)} of order 2 are real or complex-value functions of variable x, that is,
(2.23)an(x)=p(x)an-1(x)+q(x)an-2(x),
we obtain a function sequence of order 2 with initial conditions a0(x) and a1(x). In particular, if all of p(x), q(x), a0(x), and a1(x) are polynomials, then the corresponding sequence {an(x)} is a polynomial sequence of order 2. Denote the solutions of
(2.24)t2-p(x)t-q(x)=0
by α(x) and β(x). Then
(2.25)α(x)=12(p(x)+p2(x)+4q(x)),β(x)=12(p(x)-p2(x)+4q(x)).
Similar to Proposition 2.1, we haveProposition 2.7.
Let{an} be a sequence of order 2 satisfying the linear recurrence relation (2.23). Then
(2.26)an(x)={(a1(x)-β(x)a0(x)α(x)-β(x))αn(x)-(a1(x)-α(x)a0(x)α(x)-β(x))βn(x),ifα(x)≠β(x);na1(x)αn-1(x)-(n-1)a0(x)αn(x),ifα(x)=β(x),
where α(x) and β(x) are shown in (2.25).Example 2.8.
Consider the Chebyshev polynomials of the first kind,Tn(x), defined by
(2.27)Tn(x)=cos(narccosx),
which satisfies the recurrence relation
(2.28)Tn(x)=2xTn-1(x)-Tn-2(x)
with T0(x)=1 and T1(x)=x. Thus the corresponding p, q, α, and β are, respectively, 2x, -1, x+x2-1, and x-x2-1, which yields T1(x)-βT0(x)=x2-1, T1(x)-αT0(x)=-x2-1, and α-β=2x2-1. Substituting the quantities into (2.7) yields
(2.29)Tn(x)=12{(x+x2-1)n+(x-x2-1)n}.
All the Chebyshev polynomials of the second kind, third kind, and fourth kind satisfy the same recurrence relationship as the Chebyshev polynomials of the first kind with the same constant initial term 1. However, they possess different linear initial terms, which are 2x, 2x-1, and 2x+1, respectively (see, e.g., Mason and Handscomb [10] and Rivlin [11]). We will give the expression of the Chebyshev polynomials of the second kind later by sorting them into the class of the generalized Gegenbauer-Humbert polynomials. As for the Chebyshev polynomials of the third kind, Tn(3)(x), and the Chebyshev polynomials of the fourth kind, Tn(4)(x), when x2≠1, we clearly have the following expressions using a similar argument presented for the Chebyshev polynomials of the first kind:
(2.30)Tn(3)(x)=x2-1+x-12x2-1(x+x2-1)n+x2-1-x+12x2-1(x-x2-1)n,Tn(4)(x)=x2-1+x+12x2-1(x+x2-1)n+x2-1-x-12x2-1(x-x2-1)n.Example 2.9.
In [12], André-Jeannin studied the generalized Fibonacci and Lucas polynomials defined, respectively, by
(2.31)Un(x;a,b)=Un=(x+a)Un-1-bUn-2,U0(x)=0,U1(x)=1,Vn(x;a,b)=Vn=(x+a)Vn-1-bVn-2,V0(x)=2,V1(x)=x+a,
where a and b are real parameters. Clearly, Vn(2x;0,1)=2Tn(x). Using Proposition 2.7, we obtain
(2.32)Un(x;a,b)=12n(x+a)2-4b{(x+a+(x+a)2-4b)n-(x+a-(x+a)2-4b)n},Vn(x;a,b)=12n{(x+a+(x+a)2-4b)n-(x+a-(x+a)2-4b)n}.
From the last expression, we also see Vn(2x;0,1)=2Tn(x).
A sequence of the generalized Gegenbauer-Humbert polynomials{Pnλ,y,C(x)}n≥0 is defined by the expansion (see, e.g., Gould [13] and He et al. [14]):
(2.33)Φ(t)≡(C-2xt+yt2)-λ=∑n≥0Pnλ,y,C(x)tn,
where λ>0, y and C≠0 are real numbers. As special cases of (2.33), we consider Pnλ,y,C(x) as follows (see [14]):
(2.34)Pn1,1,1(x)=Un(x),Chebyshevpolynomialofthesecondkind,Pn1/2,1,1(x)=ψn(x),Legendrepolynomial,Pn1,-1,1(x)=Pn+1(x),Pellpolynomial,Pn1,-1,1(x2)=Fn+1(x),Fibonaccipolynomial,Pn1,2,1(x2)=Φn+1(x),Fermatpolynomialofthefirstkind,Pn1,2a,2(x)=Dn(x,a),Dicksonpolynomial,
where a is a real parameter and Fn=Fn(1) is the Fibonacci number.Theorem 2.10.
Letx≠±Cy. The generalized Gegenbauer-Humbert polynomials {Pn1,y,C(x)}n≥0 defined by expansion (2.33) can be expressed as
(2.35)Pn1,y,C(x)=C-n-2[x+x2-Cy2x2-Cy(x+x2-Cy)n-x-x2-Cy2x2-Cy(x-x2-Cy)n].Proof.
Taking derivative with respect tox to the two sides of (2.33) yields
(2.36)2λ(x-yt)(C-2xt+yt2)-λ-1=∑n≥1nPnλ,y,C(x)tn-1.
Then, substituting the expansion of (C-2xt-yt2)-λ of (2.33) into the left-hand side of (2.36) and comparing the coefficients of term tn on both sides, we obtain
(2.37)C(n+1)Pn+1λ,y,C(x)=2x(λ+n)Pnλ,y,C(x)-y(2λ+n-1)Pn-1λ,y,C(x).
By transferring n+1↦n, we have
(2.38)Pnλ,y,C(x)=2xλ+n-1CnPn-1λ,y,C(x)-y2λ+n-2CnPn-2λ,y,C(x)
for all n≥2 with
(2.39)P0λ,y,C(x)=Φ(0)=C-λ,P1λ,y,C(x)=Φ′(0)=2λxC-λ-1.
Thus, if λ=1, Pn1,y,C(x) satisfies linear recurrence relation
(2.40)Pn1,y,C(x)=2xCPn-11,y,C(x)-yCPn-21,y,C(x),n≥2,P01,y,C(x)=C-1,P11,y,C(x)=2xC-2.
Therefore, we solvet2-pt-q=0, where p=2x/C and q=-y/C, for t, and obtain solutions:
(2.41)α=1C{x+x2-Cy},β=1C{x-x2-Cy},
where x≠±Cy. Hence, Proposition 2.7 gives the formula of Pn1,y,C(x)(n≥2) as
(2.42)Pn1,y,C(x)=C-2[x+x2-Cy2x2-Cyαn-x-x2-Cy2x2-Cyβn],
where α and β are shown as (2.41). This completes the proof.Remark 2.11.
We may use recurrence relation (2.40) to define various polynomials that were defined using different techniques. Comparing recurrence relation (2.40) with the relations of the generalized Fibonacci and Lucas polynomials shown in Example 2.9, with the assumption of P01,y,C=0 and P11,y,C=1, we immediately know that
(2.43)Pn1,1,1(x)=2xPn-11,1,1(x)-Pn-21,1,1(x)=Un(2x;0,1)
defines the Chebyshev polynomials of the second kind,
(2.44)Pn1,-1,1(x)=2xPn-11,-1,1(x)-Pn-21,-1,1(x)=Un(2x;0,-1)
defines the Pell polynomials, and
(2.45)Pn1,-1,1(x2)=xPn-11,-1,1(x2)+Pn-21,-1,1(x2)=Un(x;0,-1)
defines the Fibonacci polynomials.
In addition, in [15], Lidl et al. defined the Dickson polynomials are also the special case of the generalized Gegenbauer-Humbert polynomials, which can be defined uniformly using recurrence relation (2.40), namely,
(2.46)Dn(x;a)=xDn-1(x;a)-aDn-2(x;a)=Pn1,2a,2(x)
with D0(x;a)=2 and D1(x;a)=x. Thus, the general terms of all of above polynomials can be expressed using (2.35).Example 2.12.
Forλ=y=C=1, using (2.35), we obtain the expression of the Chebyshev polynomials of the second kind:
(2.47)Un(x)=(x+x2-1)n+1-(x-x2-1)n+12x2-1,
where x2≠1. Thus, U2(x)=4x2-1.
Forλ=C=1 and y=-1, formula (2.35) gives the expression of a Pell polynomial of degree n+1:
(2.48)Pn+1(x)=(x+x2+1)n+1-(x-x2+1)n+12x2+1.
Thus, P2(x)=2x.
Similarly, letλ=C=1 and y=-1, the Fibonacci polynomials are
(2.49)Fn+1(x)=(x+x2+4)n+1-(x-x2+4)n+12n+1x2+4,
and the Fibonacci numbers are
(2.50)Fn=Fn(1)=15{(1+52)n-(1-52)n},
which has been presented in Example 2.5.
Finally, forλ=C=1 and y=2, we have Fermat polynomials of the first kind:
(2.51)Φn+1(x)=(x+x2-2)n+1-(x-x2-2)n+12x2-2,
where x2≠2. From the expressions of Chebyshev polynomials of the second kind, Pell polynomials, and Fermat polynomials of the first kind, we may get a class of the generalized Gegenbauer-Humbert polynomials with respect to y defined as follows.Definition 2.13.
The generalized Gegenbauer-Humbert polynomials with respect toy, denoted by Pn(y)(x), are defined by the expansion
(2.52)(1-2xt+yt2)-1=∑n≥0Pn(y)(x)tn,
by
(2.53)Pn(y)(x)=2xPn-1(y)(x)-yPn-2(y)(x),
or equivalently, by
(2.54)Pn(y)(x)=(x+x2-y)n+1-(x-x2-y)n+12x2-y
with P0(y)(x)=1 and P1(y)(x)=2x, where x2≠y. In particular, Pn(-1)(x), Pn(1)(x), and Pn(2)(x) are, respectively, Pell polynomials, Chebyshev polynomials of the second kind, and Fermat polynomials of the first kind.


## 3. Identities Constructed from Recurrence Relations

From (2.2) we have the following result.Proposition 3.1.
A sequence{an}n≥0 of order 2 satisfies linear recurrence relation (2.1) if and only if it satisfies the nonhomogeneous linear recurrence relation of order 1 with the form
(3.1)an=αan-1+dβn-1,
where d is uniquely determined. In particular, if β=1, then an=αan-1+d is equivalent to an=(α+1)an-1-αan-2, where d=a1-αa0.Proof.
The necessity is clearly from (2.1). We now prove sufficiency. If sequence {an} satisfies the nonhomogeneous recurrence relation of order 1 shown in (3.1), then by substituting n=1 into the above equation, we obtain d=a1-αa0. Thus, (3.1) can be written as
(3.2)an-αan-1=(a1-αa0)βn-1,
which implies that {an} satisfies the linear recurrence relation of order 2: an=pan-1+qan-2 with p=α+β and q=-αβ. In particular, if β=1, then p=α+1 and q=-α, which yields the special case of the proposition.An obvious example of the special case of Proposition3.1 is the Mersenne number an=2n-1 (n≥0), which satisfies the linear recurrence relation of order 2: an=3an-1-2an-2 (with a0=0 and a1=1) and the nonhomogeneous recurrence relation of order 1: an=2an-1+1 (with a0=0). It is easy to check that sequence an=(kn-1)/(k-1) satisfies both the homogeneous recurrence relation of order 2, an=(k+1)an-1-kan-2, and the nonhomogeneous recurrence relation of order 1, an=kan-1+1, where a0=0 and a1=1.We now use (3.2) to prove some identities of Fibonacci and Lucas numbers and generalized Gegenbauer-Humbert polynomials. Let {Fn} be the Fibonacci sequence. From (3.2),(3.3)Fn-αFn-1=(F1-αF0)βn-1=βn-1,
where the last step is due to α+β=1. Therefore, we give a simple identity(3.4)Fn=αFn-1+βn-1=1+52Fn-1+(1-52)n-1,
which is shown in  [16, (8.2) page 122] by Koshy. Similarly, we have(3.5)βFn=βαFn-1+βn=βn-Fn-1,
where the last step is due to αβ=-1. The above identity can be written as(3.6)(1-52)n=1-52Fn+Fn-1.
The same argument yields αn=αFn+Fn-1, or equivalently,(3.7)(1+52)n=1+52Fn+Fn-1.
Identities (3.6) and (3.7) were proved by using different method in [16, page 78].Let{Ln} be the Lucas number sequence with L0=2 and L1=1, which satisfies recurrence relation (2.2) with the same α and β for the Fibonacci number sequence. Then, using the same argument, we have(3.8)Ln-αLn-1=(L1-αL0)βn-1=(1-2α)βn-1=-5βn-1.
Thus(3.9)Ln-(1+52)Ln-1=-5(1-52)n-1,
or equivalently,(3.10)-Ln+1+(1+52)Ln=5(1-52)n
(see [16, page 129]).We now extend the above results regarding Fibonacci and Lucas numbers to more general sequences presented by Niven et al. in [17]. Let {Gn}n≥0 and {Hn}n≥0 be two sequences defined, respectively, by the linear recurrence relations of order 2:(3.11)Gn=pGn-1+qGn-2,Hn=pHn-1+qHn-2with initial conditionsG0=0 and G1=1 and H0=2 and H1=p, respectively. Clearly, if p=q=1, then Gn and Hn are, respectively, Fibonacci and Lucas numbers. From (3.2), we immediately have(3.12)Gn-p+p2+4q2Gn-1=(p-p2+4q2)n-1.
Multiplying (p-p2+4q)/2 to both sides of the above equation yields(3.13)p-p2+4q2Gn+qGn-1=(p-p2+4q2)n.
Similarly, we obtain(3.14)p+p2+4q2Gn+qGn-1=(p+p2+4q2)n.
When p=q=1, the last two identities are (3.6) and (3.7), respectively.Using (3.2) we can also obtain the identity(3.15)p+p2+4q2Hn-Hn+1=p2+4q(p-p2+4q2)n,
which implies (3.10) when p=q=1.Aharonov et al. (see [18]) have proved that the solution of any sequence of numbers that satisfies a recurrence relation of order 2 with constant coefficients and initial conditions a0=0 and a1=1 can be expressed in terms of Chebyshev polynomials. For instance, the authors show Fn=i-nUn(i/2) and Ln=2i-nTn(i/2). Thus, we have identities(3.16)(1+52)n=1+52inUn(i2)+i-(n-1)Un(i2),5(1-52)n=2i-nTn(i2)-(1+5in-1)Tn-1(i2).
In [19], Chen and Louck obtained Fn+1=inUn(-i/2). Thus we have identity(3.17)(1+52)n=in-11+52Un-1(-i2)+in-2Un-2(-i2).Identities (3.6) and (3.7) can be used to prove the following radical identity given by Sofo in [20]:(3.18)(αFn+Fn-1)1/n+(-1)n+1(Fn+1-αFn)1/n=1.
Identity (3.7) shows that the first term on the left-hand side of (3.18) is simply α. Assume the sum in the third parenthesis on the left-hand side of (3.18) is c, then(3.19)βc=βFn+1-αβFn=Fn+βFn+1=βn+1,
where the last step is from (3.6) with transform n↦n+1. Thus, we have c=βn. If n is odd, the left-hand side of (3.18) is α+β=1. If n is even, the left-hand side of (3.18) becomes α-|β|=α+β=1, which completes the proof of Sofo’s identity.In general, let{an} be a sequence of order 2 satisfying linear recurrence relation (1.1) or equivalently (2.1). Then we sum up our results as follows.Theorem 3.2.
Let{an}n≥0 be a sequence of numbers or polynomials defined by the linear recurrence relation an=pan-1+qan-2 (n≥0) with initial conditions a0 and a1, and let p=α+β and q=-αβ. Then we have identity
(3.20)an=αan-1+(a1-αa0)βn-1.
In particularly, if {an=Pnλ,y,C(x)}, the sequence of the generalized Gegenbauer-Humbert polynomial is defined by (2.33), then we obtain the polynomial identity:
(3.21)Pn1,y,C(x)=αPn-11,y,C(x)+C-2(2x-αC)βn-1,
where α and β are shown in (2.41). For C=1 (i.e., the generalized Gegenbauer-Humbert polynomials with respect to y), we denote Pn(y)(x)≡Pn1,y,1(x) and have
(3.22)Pn(y)(x)=(x+x2-y)Pn-1(y)(x)+(x-x2-y)n.Actually, (3.22) can also be proved directly. Similarly, for the Chebyshev polynomials of the first kind Tn(x), we have the identity(3.23)(x+x2-1)Tn-1(x)-Tn(x)=x2-1(x-x2-1)n-1.
Let x=cosθ, the above identity becomes(3.24)eiθcos((n-1)θ)-cos(nθ)=isinθe-i(n-1)θ,
which is equivalent to cosnθ=cos(n-1)θcosθ-sin(n-1)θsinθ.Another example is from the sequence{an} shown in Corollary 2.2 with a0=1 and a1=p. Then (3.20) gives the identity an=αan-1+βn, where α=(p+p2+4)/2 and β=-1/α. Similar to (3.6) and (3.7), for those sequences {an} with a0=1 and a1=p, we obtain identities(3.25)(p-p2+42)n+1=p-p2+42an+an-1,(p+p2+42)n+1=p+p2+42an+an-1.
When p=1, the above identities become (3.6) and (3.7), respectively. Similarly, we can prove an+k=αkan+βnak, where α=(p+p2+4)/2 and β=-1/α.It is clear that if1/an is bounded and |β|<1, from (3.20) we have(3.26)limn→∞anan-1=α.
Therefore,(3.27)limn→∞FnFn-1=limn→∞LnLn-1=1+52.The method presented in this paper cannot be extended to the higher-order setting. However, we may use the idea and a similar argument to derive some identities of sequences of order greater than2. For instance, for a sequence {an} of numbers or polynomials that satisfies the linear recurrence relation of order 3:(3.28)an=pan-1+qan-2+ran-3,n≥3,
we set the equation(3.29)t^3-pt^2-qt-r=0.
Using transform t=s+p/3, we can change the equation to the standard form s3+as+b=0, which can be solved by Vieta’s substitution s=u-a/(3u). The formulas for the three roots, denoted by α,β, γ, are sometimes known as Cardano’s formula. Thus, we have(3.30)α+β+γ=p,αβ+βγ+γα=-q,αβγ=r.
Denote yn=an-αan-1. Then (3.28) can be written as(3.31)yn=(β+γ)yn-1-βγyn-2.
From Propositions 2.1 or 2.7, one may obtain(3.32)yn={(y1-βy0γ-β)γn-(y1-γy0γ-β)βn,ifγ≠β;ny1γn-1-(n-1)y0γn,ifγ=β.
Therefore, from the identity yn=γyn-1+βn-1(y1-γy0), we obtain identity in terms of an:(3.33)βn-1(y1-γy0)=an-αan-1-γ(an-1-αan-2)=an-(α+γ)an-1+αγan-2,
or equivalently,(3.34)an=(α+γ)an-1-αγan-2+βn-1(a1-(α+γ)a0+αγa-1),
where a-1 can be found uniquely from y2=(β+γ)y1-βγy0 and y0=a0-αa-1, that is,(3.35)a2-αa1=(β+γ)(a1-αa0)-βγ(a0-αa-1),
or equivalently,(3.36)a-1=a2-pa1-qa0r,r≠0.
We have seen the equivalence between the homogeneous recurrence relation of order 3, in (3.28), and the nonhomogeneous recurrence relation of order 2, in (3.34).Remark 3.3.
Similar to the particular case shown in Proposition3.1, we may find the equivalence between the nonhomogeneous recurrence relation of order 2, an=pan-1+qan-2+k, and the homogeneous recurrence relation of order 3, an=(p+1)an-1+(q-p)an-2+qan-3, where k=a2-pa1-qa0.Example 3.4.
As an example, we consider the tribonacci number sequence generated byan=an-1+an-2+an-3 (n≥3). Solving t3-t2-t-1=0, we obtain
(3.37)β=13+13(19-333)1/3+13(19+333)1/3,α=13-16(1+i3)(19-333)1/3-16(1-i3)(19+333)1/3,γ=13-16(1-i3)(19-333)1/3-16(1+i3)(19+333)1/3.
Substituting α, β, γ, and y0=0 (with the assumption a-1=0) and y1=1 into (3.33), we obtain an identity regarding the tribonacci number sequence {an=0,1,1,2,4,7,13,24,…}:
(3.38)an-13(2-a-b)an-1+19(-3-a-b+a2+b2)an-2=13n-1(1+a+b)n-1,
where a=(19-333)1/3 and b=(19+333)1/3.
For the sequence defined by
(3.39)an=6an-1-11an-2+6an-3,n≥3,
with initial conditions a0=a1=1 and a2=2. Then, the first few numbers of the sequence are {1,1,2,7,26,91,…}. The three roots of t3-6t2+11t-6=0 are α=1, β=2, and γ=3. Therefore, by assuming a-1=7/6, we obtain the corresponding y0=-1/6 and y1=0 and the following identity for the above-defined sequence:
(3.40)an-4an-1+3an-2=2n-2
for all n≥2. From [21] by Haye, an={n+13}+1 (n≥0), where {nk} are Stirling numbers of the second kind. Hence, we obtain an identity of the Stirling numbers of the second kind:
(3.41){n+13}-4{n3}+3{n-13}=2n-2.
The idea to reduce a linear recurrence relation of order3 to order 2 can be extended to the higher order cases. In general, if we have a sequence {an} satisfying the linear recurrence relation of order r:
(3.42)an=∑k=1rpkan-k.
Assume the equation tr-∑k=1rpktr-k=0 has solutions αk (1≤k≤r). Denote yn=an-α1an-1. Then the above recurrence relation can be reduced to
(3.43)yn=yn-1∑k=2rαk-yn-2∑2≤i≠j≤rαiαj+yn-3∑2≤i≠j≠k≤rαiαjαk-⋯+(-1)ryn-r+1∏k=2rαk,
a linear recurrence relation of order r-1 for sequence {yn}. Using this process, we may obtain the explicit formula of an and/or identities in terms of an if we know the solution of the last equation and/or the identities in terms of sequence {yn}.
The process shown in Proposition3.1 can be applied conversely to elevate a nonhomogenous recurrence relation of order n to a homogeneous recurrence relation of order n+1.


## 4. Solutions of Algebraic Equations and Differential Equations

The results presented in Sections2 and 3 have more applications. In this section, we will discuss the applications in the solutions of algebraic equations and initial value problems of second-order ordinary differential equations.First, we consider roots of polynomialsp(x)=xn-xFn-Fn-1 or the solution of p(x)=0, where {Fn}n≥0 is the Fibonacci sequence. Using the identity αn=αFn+Fn-1, we immediately know that the largest root of p(x) is(4.1)x=α=1+52.
Indeed, p(x) only changes its coefficient signs once, which implies that it has only one positive root α and all of its other roots must be negative, for example, β=(1-5)/2. In [22], Wall proved the largest root of p(x) is α using a more complicated manner.We may write the identityαn=αFn+Fn-1 as(4.2)(1+52)n=(1+52)Fn+Fn-1=Ln+5Fn2,
where Ln is the nth Lucas number. Similarly, we have(4.3)(1-52)n=(1-52)Fn+Fn-1=Ln-5Fn2.Multiplying the last two equations side by side yields(-1)n=(Ln2-5Fn2)/4, or equivalently, Ln2=Fn2+4(-1)n. The last expression means 5Fn2+4(-1)n is a perfect square, or equivalently, if n is a Fibonacci number, then 5n2±4 is a perfect square. This result is a part of Gessel’s results in [23], but the method we used seems simpler. In addition, the above result also shows that the Pell’s equation x2-5y2=±4 has a solution (x,y)=(Ln,Fn).The above results on the Fibonacci sequence can be extended to the sequence{Gn}n≥0 shown in [17] and Section 3. Consider polynomial p(x)=xn-xGn-qGn-1 with q≥1. We can see the largest root of p(x) is (p+p2+4q)/2, which implies Wall’s result when p=q=1. In addition, because of(4.4)(p+p2+4q2)n=p+p2+4q2Gn+qGn-1=12(p2+4qGn+Hn),(p-p2+4q2)n=p-p2+4q2Gn+qGn-1=12(-p2+4qGn+Hn),
we have(4.5)(-q)n=14(Hn2-(p2+4q)Gn2),
or equivalently,(4.6)Hn2=(p2+4q)Gn2+4(-q)n.
Hence, (p2+4q)Gn2+4(-q)n is a perfect square, which implies the special case for the Fibonacci sequence that has been presented. Therefore, Pell’s equation x2-(p2+4q)y2=±4qn (p2+4q>0) has a solution (x,y)=(Hn,Gn).We now use the method presented in Section2 to reduce an initial problem of a second order ordinary differential equation:(4.7)y′′-py′-qy=0,y′(0)=A,y(0)=B,
of second-order ordinary differential equation with constant coefficients to the problem of linear equations. Let p,q≠0, and let α and β be solution(s) of x2-px-q=0. Denote(4.8)v(x):=y′(x)-αy(x).
Then v′(x)=y′′(x)-αy′(x), and the original initial problem of the second order is split into two problems of first order by using the method shown in (2.2) for n=2:(4.9)v′(x)=βv(x),v(0)=A-αB;y′(x)-αy(x)=v(x),y(0)=B.
Thus, we obtain the solutions(4.10)v(x)=(A-αB)eβx,y(x)={1α-β((A-βB)eαx-(A-αB)eβx),ifα≠β;eαx((A-αB)x+B),ifα=β.The above technique can be extended to the initial problems of higher-order ordinary differential equations. In this paper, we presented an elementary method for construction of the explicit formula of the sequence defined by the linear recurrence relation of order2 and the related identities. Some other applications in solutions of algebraic and differential equations and some extensions to the higher dimensional setting are also discussed. However, besides those applications, more applications in combinatorics and the combinatorial explanations of our given formulas still remain much to be investigated.



---

*Source: 709386-2009-10-25.xml*