On Sequences of Numbers and Polynomials De ned by Linear ...

On Sequences of Numbers and Polynomials

Defined by Linear Recurrence Relations of

Order 2

Tian-Xiao He

?

and

Peter J.-S. Shiue

?

Dedicated to Professor L. C. Hsu on the occasion of his

90th birthday

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.

AMS Subject Classification: 05A15, 65B10, 33C45, 39A70, 41A80.

Key Words and Phrases: sequence of order 2, linear recurrence relation, Fibonacci sequence, Chebyshev polynomial, the

generalized Gegenbauer-Humbert polynomial sequence, Lucas

number.

?

Department of Mathematics and Computer Science, Illinois Wesleyan University, Bloomington, Illinois 61702

?

Department of Mathematical Sciences, University of Nevada Las Vegas, Las

Vegas, Nevada, 89154-4020

1

2

1

T. X. He and P. J.-S. Shiue

Introduction

Many number and polynomial sequences can be defined, characterized,

evaluated, and/or 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:

an = pan?1 + qan?2 ,

n ¡Ý 2,

(1)

for some non-zero constants p and q and initial conditions a0 and a1 . In

Mansour [16], the sequence {an }n¡Ý0 defined by (1) is called Horadam¡¯s

sequence, which was introduced in 1965 by Horadam [12]. [16] 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 [6], Hsu [13], Strang [22], Wilf [24], etc.) In [3], Benjamin and

Quinn presented many elegant combinatorial meanings of the sequence

defined by recurrence relation (1). For instance, an counts the number

of ways to tile an n-board (i.e., board of length n) with squares (representing 1s) 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). The key idea of

our method is to reduce the relation (1) of order 2 to a linear recurrence

relation of order 1:

an = can?1 + d,

n ¡Ý 1,

(2)

for some constants c 6= 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:



n ?1

, if c 6= 1;

a0 cn + d cc?1

(3)

an =

a0 + nd,

if c = 1.

The method and some related results on the generalized GegenbauerHumbert 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. An extension of the above results to higher order cases. In Section

Sequences of numbers and Polynomials

3

4, we shall 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) as

an = (¦Á + ¦Â)an?1 ? ¦Á¦Âan?2 ,

(4)

where ¦Á and ¦Â satisfy ¦Á + ¦Â = p and ¦Á¦Â = ?q. Therefore, from (4),

we have

an ? ¦Áan?1 = ¦Â(an?1 ? ¦Áan?2 ),

(5)

which implies that {an ? ¦Áan?1 }n¡Ý1 is a geometric sequence with common ratio ¦Â. Hence,

an ? ¦Áan?1 = (a1 ? ¦Áa0 )¦Â n?1 ,

and

an = ¦Áan?1 + (a1 ? ¦Áa0 )¦Â n?1 .

Consequently,

¦Á

an

=

n

¦Â

¦Â



an?1

¦Â n?1



+

a1 ? ¦Áa0

.

¦Â

(6)

Let bn := an /¦Â n . We may write (6) as

bn =

a1 ? ¦Áa0

¦Á

bn?1 +

.

¦Â

¦Â

(7)

If ¦Á 6= ¦Â, by using (3), we immediately obtain

 n

¦Á

 n

an

a1 ? ¦Áa0 ¦Â ? 1

¦Á

= a0

+

¦Á

¦Ân

¦Â

¦Â

?1

¦Â





a1 ? ¦Áa0 n

1

n

n

=

¦Á a0 +

(¦Á ? ¦Â ) ,

¦Ân

¦Á?¦Â

which yields



an =

a1 ? ¦Âa0

¦Á?¦Â



n

¦Á ?



a1 ? ¦Áa0

¦Á?¦Â



¦Â n.

(8)

4

T. X. He and P. J.-S. Shiue

Similarly, if ¦Á = ¦Â, then (3) implies

an = a0 ¦Án + n¦Án?1 (a1 ? ¦Áa0 ) = na1 ¦Án?1 ? (n ? 1)a0 ¦Án .

(9)

We may summarize the above result as follows.

Proposition 2.1 Let {an } be a sequence of order 2 satisfying linear

recurrence relation (4). Then

( 

an =



a1 ?¦Âa0

¦Á?¦Â

na1 ¦Án?1





?¦Áa0

¦Án ? a1¦Á?¦Â

¦Â n , if ¦Á 6= ¦Â;

? (n ? 1)a0 ¦Án ,

if ¦Á = ¦Â.

In particular, if {an } satisfies the linear recurrence relation (1) with

q = 1, namely,

an = pan?1 + an?2 ,

then the equation x2 ? px ? 1 = 0 has two solutions

¦Á=

p+

p

p

p ? p2 + 4

p2 + 4

1

and ¦Â = ? =

.

2

¦Á

2

(10)

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

p

p



n

2a1 ? (p ? p2 + 4)a0 n 2a1 ? (p + p2 + 4)a0

1

p

p

an =

¦Á ?

?

,

¦Á

2 p2 + 4

2 p2 + 4

(11)

where ¦Á is defined by (10).

Similarly, let {an } be a sequence of order 2 satisfying the linear

recurrence relation an = an?1 + qan?2 . Then

(

¡Ì

¡Ì

2a1 ?(1+ 4q+1)a0 n

2a1 ?(1? 4q+1)a0 n

¡Ì

¡Ì

¦Á

?

¦Á2 , if q 6= ? 14 ;

1

2 4q+1

2 4q+1

an =

1

(2na1 ? (n ? 1)a0 ),

if q = ? 14 ,

2n

¡Ì

¡Ì

where ¦Á1 = 12 (1 + 4q + 1) and ¦Á2 = 21 (1 ? 4q + 1) are solutions of

equation x2 ? x ? q = 0.

Sequences of numbers and Polynomials

5

The first special case (11) was studied by Falbo in [7]. 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: { 11 , 32 ,

¡Ì

7 17 41

,

,

.

.

.},

called

the

closest

rational

approximation

sequence

to

2.

5 12 29

The second special case is also a corollary of Proposition 2.1. If q =

2 (p = 1), {an } is the Jacobsthal sequence (See Bergum, Bennett,

Horadam, and Moore [4]).

Remark 1 Proposition 2.1 can be extended to the linear recurrence

relations of order 2 with more general form: an = pan?1 + qan?2 + ` for

p+q 6= 1. It can be seen that the above recurrence relation is equivalent

`

.

to the form (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 order 2.

Remark 2 Denote



un =

an+1

an





and A =

p q

1 0



.

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 the 2 ¡Á 2 matrix A defined

above. Thus un?1 = An?1 u0 . 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+1 an?1 ?a2n =

(?q)n?1 (a2 a0 ? a21 ) (See, for example, [22] for more details).

Example 1 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) with p = q = 1 and the special case of the sequence in Corollary

2.2, which can be written as (4) with

¡Ì

¡Ì

1? 5

1+ 5

and ¦Â =

.

¦Á=

2

2

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download