in it ia l v a l u e s f o r h o m o g e n e o u s l in e a r r e c u r r e n c e s o f s e c o n d o r d e r O ne can easily com pute w hich is the c...

0 downloads 22 Views 1MB Size

No documents

0. INTRODUCTION A homogeneous linear recurrence of second order with constant coefficients is a sequence of equations for fixed complex numbers a,b*0. A solution {un}n>Q is completely determined by (0) and the two initial values u0,ux. C. Kimberling [1] raised the following problem: under what conditions on two nonnegative integers i,j does every complex pair z/z, Uj determine the whole recurrence sequence {un} with (0)? In this article, I give two answers to this question (Theorems 1 and 2; the second corrects Theorems 2 and 6 of [1]) and apply them to the properties of the initial pairs. In Theorem 3 I discuss how they are distributed, while in Theorem 4 I discuss which initial values generate a periodic sequence. 1. A FIRST CRITERION FOR INITIAL PAIRS Given a recurrence (0), we call two nonnegative numbers / < j an "initial pair" if, for all complex numbers ci9Cj, there exists one and only one solution {un} of (0) with ui -c,, Uj =Cj. An initial pair is always /,/ + l. Most pairs i,j will be initial, but there are exceptions: 0,2 is not an initial pair of un+2 = un. Theorem 1 ([1], Theorem 1): Given the recurrence (0) with b * 0, for every pair of nonnegative integers i,j with / +1 < j , the following two conditions are equivalent: ij is an initial pair for (0); the (J-i-1)-rowed

(1)

matrix (a b 0 D

M

-1 0 a -1 b a (2)

=

L

b 0

a -1 b a

is regular. Proof: The pair /', / + 2 is initial iff a * 0, since aui+l = ui+2 - but. So let j>i + 2. If uf - c; and Uj - Cj are given, then the equations bun + aun+l - un+2 = 0, for n = /, i +1,..., j - 2, give us the system 24

[FEB.

INITIAL VALUES FOR HOMOGENEOUS LINEAR RECURRENCES OF SECOND ORDER

auM-

= -bc, =0 =0

ui+2

bui+1+aui+2-

M,+3

bui+2+aui+3- -«,+4 bu_3+au_2-

u_x=0

bUj_2+aUj_l

=Cj.

Now, 7,7 is an initial pair iff this system of 7 - 7 - 1 linear equations has a unique solution w/+1, ui+2, ...,Uj-i (and hence all un,n>0, are determined) for all c7, c.. A necessary and sufficient condition for this is that the associated homogeneous linear system is only trivially soluble, hence the regularity of the coefficient matrix DjH, Q Remark: This criterion can be extended to sequences of higher order (see [1], Theorem 7). Condition (1) is equivalent to the following: the monoms z\zJ are a basis of the complex vectorspace C[z] of polynomials modulo the subspace C[z](z2 -az -h). This was generalized by M. Peter [2] to recurrences of several variables of higher order. 2. A SECOND CRITERION FOR INITIAL PAIRS Let n: = 7 - i. We compute dn: = det Dn by expanding the determinant of Dn+2 a la Laplace: d

n+2=adn+l+bdn,

d

o'=°,

d

(3)

V=^-

Let £ i : = l ( a + Va 2 +46)

and £ 2 : = j ( a - Va2 + 46)

be the zeros of the companion polynomial z -az-b of (0), then the solution of the initial problem (3) has the Binet representation 1 n r_r-(Ci-C 2) d=

x&*C2,

,

for all n GN. Hence we get dn = 0<=>£x *£ 2 ,

(4)

C\-Ci-

The last condition is equivalent to

31a + Va2+4Z> =expi2m—

\(a-ja2+4b)

<=><%la2 +4h exp 2^7—1 + 1 \ = a exp\2m— -

This finally means 1997]

m <=>Va2 +4Z> cos ;r— =-7a sin I ;r— n

25

INITIAL VALUES FOR HOMOGENEOUS LINEAR RECURRENCES OF SECOND ORDER

a2 = -4b cos2 n—

3\

Theorem 2: Suppose we have a recurrence (0) with b & 0 and a pair of nonnegative integers / < j . Then the following three properties are equivalent: ij is an initial pair of (0);

(1)

if ^ and <^2 are the zeros of the polynomial z2 -az-h,

then C,x - <^2 or £{~~l * £J2~';

(5)

a2 2( m 1 n . . ,^x —-^-coshTr for every \

= 0: a = -b: a2 = -2b: a2 = -36:

a

2

j-i^0 j-i=£0 j-i^0 7- i # 0

mod2; mod3; mod4; mod 6.

If a2 = -&6 with A: e Z - {0,1,2,3}, then every pair i < j is initial. 3. DISTRIBUTION OF INITIAL PAIRS IN RESIDUE CLASSES In the examples of initial pairs / < j given above, j-i next theorem explains why.

lies outside of some residue class. The

Theorem 3: a) Suppose that the recurrence (0) with b * 0 has a pair that is not initial, then there exists an integer m > 2 such that, for every pair / < j of nonnegative integers, we have that ij is initial for (0) <=> j -i # 0 mod/w. b) For every natural number m > 2, there is a recurrence (0) such that 0,y' is initial for (0) o j ^ O mod m. Proof: a) By Theorem 1, there exists a natural number n>2 with dn = Q. Let m:=min{n>2: dn - 0} and 8.-dm+l. From (4), we deduce that dgm+r = 8qdr for all geN 0 , 0

* : = - £ , then rf, = ( ^ - l ) / ( £ - l ) , ; e N , so that

Theorem 3 is proved. D

26

[FEB.

INITIAL VALUES FOR HOMOGENEOUS LINEAR RECURRENCES OF SECOND ORDER

4. PERIODIC SEQUENCES If ij is an initial pair for (0), we now seek conditions under which two complex numbers q, Cj generate aperiodic recurrence sequence {un} with ut - q and Uj = Cj. Theorem 4: Given a recurrence (0) with h * 0, a pair ij in N0 with /

(c) a

(d) Here again, £h £2 a r e ^ e

zeros

°f z2

=1

^=<>lf

J-*

-az-b.

Proof: Because of Theorem 2, each of the four conditions implies that i,j is an initial pair for (0). Hence, it suffices to show under which condition the unique solution {un} of (0) with ut - c{ and Uj = Cj has period m. 1) ^ & C,2. In this case,

However, the property un+m =un, n> 0, is equivalent to

o<

[(cy-^rx

^ = \,Cj = c^r,

|(b)

& = \,cj = <£{-*,

kc) [(d)

cr=^=i, cy=^-'=^r-

<=>i

Since <£f"7 ^ <^~7, case (d) is impossible. 2) Ci = C2- H e r e ^ = ^ [ ( * - i > y + a ^ ^

1997]

27

INITIAL VALUES FOR HOMOGENEOUS LINEAR RECURRENCES OF SECOND ORDER

One can easily compute

which is the case (d) of (8), and Theorem 4 is proved. • REFERENCES 1. 2.

C. Kimberling. "Sets of Terms that Determine All the Terms of a Linear Recurrence Sequence." The Fibonacci Quarterly 29.3 (1991):244-48. M. Peter. "Rekurrente zahlentheoretische Funktionen in mehreren Variablen." (To be published.)

AMS Classification Numbers: 11A25, 11B37, 11B39

Announcement EIGHTH INTERNATIONAL CONFERENCE ON FIBONACCI NUMBERS AND THEIR APPLICATIONS June 21-June 26,1998 Rochester Institute of Technology Rochester, New York LOCAL COMMITTEE Peter G. Anderson, Chairman John Biles Stanislaw Radziszowski

INTERNATIONAL COMMITTEE A. F. Horadam (Australia), Co-chair M. Johnson (U.S.A.) A.N. Philippou (Cyprus), Co-chair P. Kiss (Hungary) G. E. Bergum (U.S.A.) G.M. Phillips (Scotland) P. Filipponi (Italy) J. Turner (New Zealand) H. Harborth (Germany) M. E. Waddill (U.S.A.) Y. Horibe (Japan) LOCAL INFORMATION For information on local housing, food, tours, etc., please contact: Professor Peter G. Anderson Computer Science Department Rochester Institute of Technology Rochester, New York 14623-0887 [email protected] Fax: 716-475-7100 Phone: 716-475-2979

CALL FOR PAPERS Papers on all branches of mathematics and science related to the Fibonacci numbers, number theoretic facts as well as recurrences and their generalizations are welcome. Thefirstpage of the manuscript should contain only the title, name and address of each author, and an abstract. Abstracts and manuscripts should be sent in duplicate by May 1,1998, following the guidelines for submission of articles found on the inside front cover of any recent issue of The Fibonacci Quarterly to: Professor F.T. Howard, Organizer Box 117,1959 North Peace Haven Road Winston-Salem, NC 27106 e-mail: [email protected] 28

[FEB.