F IB O N A C C I S E Q U E N C E S W IT H ID E N T IC A L C H A R A C T E R IS T IC V A L U E S E U G E N E L E V iN E C . W . Post C o lle g e , L o ...

0 downloads 11 Views 1MB Size

No documents

A Fibonacci sequence is viewed herein as an integer sequence

n=-oo which satisfies the recursion (1)

f

v

= f n

+ f n-i

n

n-2

for all n. Following [ l ] , it is convenient to associate two Fibonacci sequences with each other if one can be transformed into the other by a relabeling of indices. Also, it is apparent that jf [ satisfying (1) implies that j - f j satisfies (1) and it is convenient to associate a sequence with its negative.

These remarks

lead to Definition.

Two Fibonacci sequences jf } and jg !• are equivalent if

and only if there exists an integer k such that either (i) v;

gto = f ?1 n n+k

for all n;

or g v(ii); &

n

= -f ,, n+k

for all n8

In [ l ] , the discussion pertains to Fibonacci sequences such that there is no common divisor d > 1 of every term in the sequence (or equivalently, of any two consecutive terms). In this paper, we will be interested in all integer sequences satisfying (1). However, when there is no common divisor (>1) of the sequence, we will call the sequence primitive,, A well-known identity satisfied by Fibonacci sequences is 75

76

FIBONACCI SEQUENCES

(2)

f __, f - f2 = ±D n+i n-i n

v

[Nov,

where D > 0 and the sign alternates with ne We call the integer D = If ^ f - f2 I n+i n-i n| the characteristic of the sequence \f }. The reader may verify that if (f } is equivalent to \g\

then ff } and \g } have the same characteristic.

A table is presented in [l] of all D < 1000 for which there exists a primitive sequence, Also 3 all primitive sequences (up to equivalence) having these characteristics are provided,

Such a table leads one to ask the following

two questions: (1) For a given integer D > 0$

how many Fibonacci Sequences are

there (up to equivalence) having the characteristic D? (II) For a given D > 0S how many primitive Fibonacci sequences a r e there (up to equivalence) having the characteristic D? This paper is devoted to providing a complete answer to each of these questions. For this purpose 3 we let

a = I±*£ 2 and we consider the field extension U(a) obtained by adjoining a totherationals. The domain of algebraic integers in R(a) then consists of all numbers of the form A + Bo? > where A and B are rational integers. It is well known (see [ 2]) that one has unique factorization in this domain of integers. The units in ±n this domain are precisely numbers of the form ±a and all primes (up to associates) are (I)

Vs" = 2a - 1

(ii) all rational primes of the form 5k ± 2 (Hi) numbers of the form A + BQ! and A + Bo?s where a is the conjugate of o>9 i. e . ,

5 = i-^£

1968]

WITH IDENTICAL CHARACTERISTIC VALUES

77

and |(A + Bo?) (A + Bo>) is a rational prime of the form 5k ± l. We may assign to each Fibonacci sequence an integer f in R(a )* namely* the sequence {f | is assigned the Integer

f = f0 + f^.

It Is easily

verified that the assignment of Integers in this manner provides a one-to-one correspondence between Fibonacci sequences and integers in R(o?). f - = A + Bo? be an Integer In R(o?) we denote by S(f) assigned to f

Letting

the unique sequence

(i. e„, the sequence determined by f0 = A, ft = B).

The assignment S(f) preserves addition in the sense that if S(f t) = {fj

and S(f 2 ) = { g j ,

then S ( ^ + f 2 ) = {fn 4 - g J .

It might also be r e -

marked that the correspondence S(f) allows one to define a product of two Fibonacci sequences in a natural way® Namely f for two Fibonacci sequences S(^j) and S(f 2 ),

the product sequence Is defined as S(f 1 f 2 )«

I n this way,

one has a ring of Fibonacci sequences which Is isomorphic to the ring of integers in R(a). Two integers

and f2 in R(a) are called associates If ^ = ef 2 ±n for some unit £ (which i s one of the integers *oi ). It follows that 'two sequences S(^ 1 ) and

f4

S(f 2 ) ^ r © equivalent If and only if

^

and

f2

are

associates* For a given integer

f = A + Ba,

we define the (absolute) norm N(f)

in the usual way as N(f) = if f" I, where

f = A + BcS® One can easily verify

that the characteristic D of a Fibonacci sequence S(f) is simply N(f). As a result of the above remarks, we find that questions (I) and (II) reduce to questions about Integers in R(a).

Namely,

(1) and (II) are equivalent to

asking i (la) (Ha)

How many integers In R(a) (up to associates) have a given norm D? How many Integers In R(a)

(up to associates) with no rational inte-

ger divisor d > 1 have a given norm D ? To resolve these questions we introduces P* = {set of all positive rational Integers n such that every prime divisor of n is of the form 5k ± 1/ and by convention 1 belongs to P*;

o>(n) = number of distinct prime divisors of n;

78

FIBONACCI SEQUENCES

d|n, d > 0 d=±l(mod 5)

[Nov.

dn,d > 0 d=±2(mod 5)

r(n) = d+(n) - d j n ) , where r(0) = 1 by convention. (To illustrate, w(60) = 3, d+(60) = 3,

dJ60)

= 3, r(60) = 0). The answers to (I) and (II) may now be provided in a compact form as follows? Theorem 1. For D > 0, there are exactly r(D) Fibonacci sequences (up to equivalence) having characteristic D. Theorem 2C

There exists a primitive sequence having characteristic

D > 0 if and only if D = n or D = 5n9 where n belongs to P*e For such a characteristic D, the number of (inequivalent) primitive sequences is exactly 2 C0(n) s Proofs; Letting ^ r a hi bo D = 5 p^pg 2 •••

\ Ci Pj^qi1---

c

k qkK

be the prime factorization of D, where p. is a prime of the form 5m ± 1 and q. a prime of the form 5m ± 2 it follows that all integers in R(a)

having

norm D are n A + Ba = €(V5) a n

(3)

i=i

K

(At + B . G O ^ A . + B.5) 1 * fi q ^ A j=i

J

where € is a unit, s. +1. = b., c. of necessity is even, and A. + B.a

is a

prime In R(tx) having norm p.. Thus, the number of integers (up to associates) having norm D Is the number of ways we can vary each s. with 0 < s. < b.. The number of such choices for the s. is the product 11 (1 + b . ) .

The

latter expression (combined with the fact that all c. must be even) is equivalent to Theorem 1. This equivalence is a counting exercise which can be ascertained in the following way. Letting

The factor 5

of D has no effect upon the value of r(D).

WITH IDENTICAL CHARACTERISTIC VALUES h

D

,

1

k

= n pf n q? . J i=i

j=i

one has r(D) = r(D). The divisors of 5 are the terms in the expansion

h , k n ( 1 + P . + - - - + P . 1 ) n (l + qu + °°° +q ] C J) .

(4)

By replacing each p. with the value +1 and each q. with the value -1 in (4), the resulting expansion will yield a term of +1 for each divisor of the form 5m ± 1 and a term of -1 for each divisor of the form 5m ± 29 expansion of the modified expression Is merely r(D).

Thus* the

If any c. is odd the

factor (1 + (-1) + • • • + (-1) 3) Is zero which yields r(D) = 0S If all c. are c* even, then the factor corresponding to q. is (1 + (-1) + • • • + (-1) 3) = 1 and the resulting expression for r(D) becomes n (1 + b.)

which Is the desired

result Theorem 2 is obtained by realizing that for (3) to have no rational integer divisor

f>l),

one must have a = 0 or 1, c. = 0 for all j , and the 3 k only choices for s. are 0 and b.. Thus s tie re are 2 choices for s. f which is theorem 2, As a final note* it should be pointed out that the proofs of Theorems l a n d 2 proceed in a manner analogous to that which one could take in determining the number of representations of an integer N as the sum of two squares (see Theorem 278 of [ 2]) 0 In this latter problem one utilizes the ring of gaussian integers whereas in the problems considered above we have relied upon the ring of integers in R(a).

It would appear that the above results should extend

to other recursions of the form f = af + bf provided one has unique n n-i n-2 factorization in the underlying ring of integers. For a related paper, see Thoro [3]. '

80

FIBONACCI SEQUENCES WITH IDENTICAL CHARACTERISTIC VALUES

Nov. 1968

REFERENCES Brother U„ Alfred, "On the Ordering of the Fibonacci Sequence," Fibonacci Quarterly, Vol. 1, No. 4, Dec. 1963, pp. 43-46. [See Corrections, p. 38, Feb. 1964 Fibonacci Quarterly. ] Hardy and Wright, An Introduction to the Theory of Numbers, Third Edition, 1954, Oxford University P r e s s , pp. 221-223, pp. 240-243. D. E. Thoro, "Application of Unimodular Matrices," Fibonacci Quarterly, Vol. 2, No. 4, Dec. 1964, pp. 291-295. • • * •

•

FIRST QUADRANT GRAPH OF GAUSSIAN PRIMES