N o te th a t th e firs t, second.and th ird parentheses o f (1 2 ) a re , in fa c t, th e re cu r-rences fo r b ise cte d co p rim e , co p rim e and...

0 downloads 7 Views 1MB Size

No documents

Most of this paper was finished prior to the author's involvement in other work [ 9 , 1 0 ] . It is the purpose of this exegesis to find a self-contained definition of {Gj} which is not dependent on other sequences. Such are (10), (12) and (16). I have defined these numbers in [2,(3)] and [3, (9)]. G numbers of thej'th order are: (1» GJtk = where the Lucas complement is by definition

1+P*k+Pj,2k-l,

(2) Pj,k = PjMi+pj,k-i> and where coprime sequences are by definition,/ an integer, (3)

Pjtk+i

=

JPj,k+Pj,k-l,

and where the initial conditions (IC) are by choice (3a)

Pjt0 = 0

and Pjj = 1

for all /'.

To begin we need the following easily proven identities. The Lucas complement of the Lucas complement is (4) PJMI +Pj,k-i = PjM2 +Wj,k +Pj,k-2 = (4 +j2)Pjtk • Secondly given any two point recurrence/ 3 ^ =aPn +bPn_i the recurrence among its bisection is known to be (5) Pn+2 = (a2+2b)Pn-h2Pn_2 Thirdly we need the central difference operator

.

8 2Pn = (A - V)Pn = Pn+1 - 2Pn +Pn_t

(6)

and fourthly I define a new operator small psi (7)

VjfPJ

[S2-j2]Pn,

=

where j 2 is really j 2 times the identity operator. Note that if B^n is any generalized bisected coprime sequence with any BtQ and Bu whatsoever that xjjj then acts as a null operator, to wit (8)

\\jj(Bj)n)

for a l l / .

=0

Now when / = /then (7) reduces to \\j(Fn) = [82 - l]Fn. Consider

^j(Gj)k) = tyfPlk)-/2

(9)

which is obvious from (1) and (8) and the fact that ^j(V= - / . In (9) elimination of 5 via (6) gives (9a)

4jj(Gj)k)

- (2 +j2)P*k

-j2

.

The recurrence for \pj(Gjfk) is Fibonacci but for the additive constant/" 5 .

Theorem. Proof.

= (4 +j2)Pj>k

Rewrite (9a) as i/'yGy^+i and substitute (3) giving 1>j(GJtk+1) - fj2 +4][jPj)k +Pj,k-lJ ~ ft2 +2][jPlk

<10)

= Mj(Gjtk) +

+

Pj,k~l]

il>j(Gj,k-l)+i3

Eliminating/^ by calculating tyGj^+i - \pGjfk obtains Corollary

1.

^GjM1

= (j+l)^Gjfk

- (j- D^Gj^-i 166

- ^Gj>k„2 •

-J2

APR. 1878

ON GENERALIZED Gj>k NUMBERS

107

Inserting (7), the definition of psi, one finds the general recurrence

(11)

Gj,k+i = (i2+i

+

3)Gj,k-(J3

+J2+3j+2)Gjyk_1+(j3

-j2 +

+ tj2-j

3j-2)Gj}k_2

+

3)Gj}k_3-Gj)k_4.

This recurrence is not messy but instead factors into the crowning equation of this paper (E2-(j2+2)E + !)(E2-jE-l)(E-l)Ghk

(12)

= 0,

where E is the forward shift operator. Note that the first, second.and third parentheses of (12) are, in fact, the recurrences for bisected coprime, coprime and constant sequences respectively! A more useful expression in terms of forward and backward difference operators is

(82-I)(A+V-l)AGj>k

(13)

= 0 = (A3-2A2

+

A-M82)Gj)k

only if/ = 7. Now (12) is more general than (1) and (13) is more general than { ^ j 21,46,108, - . An example of (13) is the sequence (13a)

= .-79,42,10,9,2,4,3,6,10,

0, 0, 0, 0 , 1 , 5, 18, 56, 162,450,1221, 3267,8668, 22880, •••, 60204,158108,414729,

whose falling diagonal, A *, from the first zero is (13b)

0,0,0,0,1,0,3,0,8,0,21,0,-..

Hence to obtain/ order 6 numbers some IC must be introduced. First some simplifications. When/ = 7, then Eqs. (9a), (10) and (11) become

(82-l)Gk

(9b) (10a)

= 5Fk-3Lk-1

=

-(1+2Lk_2)

<\)Gk+1 = \pGk + \PGk_1 + f Gk+i = 5Gk - 7G},.! + G^2 + 3G^3 - Gk-4 >

(11a)

respectively. Note that (13a) was calculated by (13) and checked by (11a). Also note that (11), (12), (13), (11a) are fifth-degree recurrences. Gould [5] found (11a) independently. Directly from (10) one can find the modified recurrence

GjM1 = (j2+j+2)Gj>k-(j3

(14)

+ 2/)Gj)k-l ~ 0'2 ~ J +2)Gj>k_2 + Gj)k_3 +j3 ,

which, when/= 7, becomes

(14a)

Gk+1 = 4Gh-3Gk_l-2Gk_2

+ Gk_3 + 1

and from this latter it is easy to derive the exquisite (14b) 84Gk+2 = 382Gk+1-Gk +l . At this point the reader should study Tables 1 and 2. Now a curious fact results from Corollary 1 which I rewrite as Corollary

1.

\p (Gj}k+i

+ Gj)k_2) = (1 +MGj>k

+ (1 ~

MGj>k-i

This says that making both / and k negative reproduces the same recurrence. To be specific replace/ by - / a n d let n = (1 - k) and the Corollary regenerates itself. Thus 4, 3, 6,10,21,46, - has the same recurrence as 4 , 4 , 9 , 1 8 , 4 2 , 101,--.See Table 1. Lemma.

The zeroth term of all {Gj} equals the constant 4.

The proof is direct from Eqs. (1) through (3a). Omitting the subscript/for simplicity and recalling that Pjj = 1 for all/we have:

Go = 1+Po+P-l

= 1+Pi+P-i+P-i

(15)

= 1+3Pi =4

Gj>0 = 4.

From (12) of paper [3] one may easily find (16a,b)

Gjfl = (j+2)

and b2Gji0

=

Gj}1AGjy0

168

[APR.

ON GENERALIZED Gjtk NUMBERS

Table 1 Array of G^k Numbers j/k 6 5 4 3 2 1 0 -1 -2 -3

-4 2027452 510354 98532 13090 1020 42 4 42 1020 13090

- 3 53120 18761 5392 1154 156 10 2 18 184 1226

- 2 - 1 0 1444 32 4 729 22 4 324 14 4 121 8 4 36 4 4 9 2 4 4 2 4 9 4 4 36 8 4 121 14 4

1

2

3 76 1640 54 843 36 382 22 146 12 44 6 10 2 4 2 1 6 2 0 12 16 -1 22 74 8 ti 6 5 4 3

4 54796 19629 5796 1309 204 21 4 21 204 1309

5 2034896 513402 99574 13364 1068 46

6

2 24 804 12578

108 4 108

TabSe 2 The Table of D ifferences of Gk 9-

2 -7

4 2

9

3

6

-1

- 3 -12

3 4

7 -10 -29

14

108 ••• 62

37 23

16

-8 -27

46 25

7 r

9

48 123

7 6

19

-75 -200

21 11

1 -3

19 46

10 4

15 23

-75

2 -21

323 leaving a fourth initial condition to be chosen in order to define Gj^. We may now take this to be

32Gj}1 = 2Gj_1.

(16c)

One can also show from (1) or from (12) of paper [3] that

(17)

Gj}_2 = (I2 +2)2

and

Gjt_i = j(j - 1) + 2 = G^+U.t

for all integer/. At this point it will help the reader to go through an example such as t h e / = 3 case beginning with 3,k='®. 1»3,10,33,109,360,1189,3927,-. In fact relations stronger than Corollary 1 exist as is evident from Table 1 where we see that

p

(18)

Gj)k+Gj„k = G^k+G.j.y,

for all integer/ and k and indeed a special case follows if e is even

(19)

Gj>e = G.jt€

Now (18) and (19) are easily proven from (1) and the odd/even properties of F and L sequences. DIVISIBILITY PROPERTIES For the study of divisibility properties we are able to rewrite (1) by substituting (6) of [ 3 ] , P

2n-1

=

PnPn-1

~ COS (iw) ,

into it giving

(20) (20a)

1+ Gjtk = Plk(l+Pj,k-l> + (-1>k+l Gk = Lkd + Fk.tJ+l + f-V^1 .

Hence the divisibility properties of the even Gk are known since Jarden [4, p. 97] has tabulated the divisors of (1 + Fn). The divisibility of the odd G^ is involved. Three divides G^ at intervals of eight starting with

1878]

ON GENERALIZED Gj}k NUMBERS

k = •••-/,

160

1,9,17,25,33,-

and five divides G^ at intervals of twenty starting with k = — 3 , 17, 37, ---and proceeding in both directions. Divisibility properties are left for a later paper. Conjecture

1.

If Gk is prime then \k\ is prime.

Conjecture

2.

The number of primes in [GI } is infinite.

The known primes are G_$ = 79, G_i =2, G± =3, Gj = 263. G$i may be prime. The sequence of G_£ is interesting. The first thirteen G_k numbers are placed immediately below their corresponding Gk numbers beginning with k = 1 in both cases. (21 )

3,6,10,21,46,108,263, 658,1674, 4305,11146, 28980, 75547,2,9,10,42,79,252, 582,1645,4106,11070,28459, 75348,195898, -.

A glance at these G numbers provide another symmetry property, (22)

G-2n-G2n

and

= F4n

for d odd.

Gd + G„d = L2d+2

And more generally it is rather easy to show via (20) that (23)

=

Gj-2n ~ Gj}2n = Pj,2n(Pj,2n+l ~Pj,2n-lt

(24)

Gj,d + Gj}„d = P*2d+2

JPj,4n

for d odd

DIFFERENCES OF Gk We need the following: (25) (26) (27)

VkHn = Hn_2k 2k

l Bn

= Bn.k k

V An

lkHh

and so and

V

2k+1

= signum

Bn

= H_k = MBn.k

(An)\An+k\,

where Bn is any bisection of Hn, and where (25) and (26) are easily derivable from (28)

Hn+1 = Hn + Hn_i,

any H0 and Ht,

and where An is a two-point sequence with alternating signs satisfying (29)

An+1

=

-An+An-i

corresponding to j = -1 in (3), and signum is the sign function. Then application of (25) and (26) to (1) immediately gives (30)

VkGk =

Fk-i+(-UkLk,

which becomes -Pk+i in the odd k case. Note that these numbers lie along a falling diagonal from GQ = 4 in Table 2. Equation (30) introduces a significant simplicity into the Gk numbers. Note that (30) is reminiscent of the definition of the Bell numbers, to wit: (31)

V ^ B e l l , , = Bell n _i,

n > 2.

Likewise one may also show that (32)

V ^ G f e = Fk-4

for odd k > 3

and these numbers 1,1,2,5, - a r e a bisection of the falling diagonal from Gi = 3. Note that all falling diagonals :3FE two bisected sequences, Bn, and satisfy for all k and all n > 1, (33)

An+4Gk

= 3An+2Gk-AnGk

.

I did not expect to find upon glancing at the central differences of GQ that they would be: - 3 , 1 9 , - 7 5 , ••• almost Lucas numbers. We may write (34) d2nG0 = l2nGn = 1 + (-1)nL3n .

170

ON GENERALIZED Gj)k NUMBERS

APR.1978

This may be easily derived from (1) withy = 1 by applying (25). The critical step is V2kLk according to (25). We obtain (35a)

V^Gu 2k

(35b)

(35c)

V Gk

V

2k+1

Gk

= Lk_4k = L-3k = L_3k+2,

k > 1 k > 1

= L_3k+F_u

- U3k-2 + ^2,

k>U,

where, of course, F_2 = - 1 and F_f = 1. Equations (35) prove what is obvious by looking at Table 2, namely if we make a zig-zag below the 4 entry we obtain the sequence: - 1 , 2 , - 3 , 7 , - 1 2 , 1 9 , - 2 9 , 4 6 , - 7 5 , 123, - w h i c h is almost the Lucas sequence. This makes the whole sequence easy to generate by hand. Finally the choice of letter for these sequences was Gould's [1] who suggested my name for them after seeing my paper [ 6 ] , The author appreciates some comments by Zeitlin [8] concerning (14) and (23). Zeitlin [7] has also pointed out that the subscript of the subscript of the last term of Eq. (12) of [6] should be (k - 1) and not (k - 2). This mis? print is obvious from the expansion in (13) of [ 6 ] . Having found that the messy looking G^y, sequence actually satisfies the near Fibonacci relationships (10) and (12) and further that the Lucas numbers have made their presence known, I am impelled to write down an old haiku of mine in which even the numbers of syllables in each line, namely 3, 2, 5, 7 are themselves a Fibonacci sequence. PHI Multiply Or add We always reach phi Symmetries we perpetrate. REFERENCES 1. 2. 3. 4. 5. 6. 7. 8. 9. 10.

H.W.Gould, Letter to V. E. Hoggatt, Jr., 1976, Nov. 18. W. E. Greig, "Sums of Fibonacci Reciprocals," The Fibonacci Quarterly, Vol. 15 (Feb. 1977), pp. 46-48. W. E. Greig, "On Sums of Fibonacci-Type Reciprocals," The Fibonacci Quarterly, Vol. 15 (Dec. 1977), 356-58. Dov Jarden, Recurring Sequences, 3rd Ed., 1973, Riveon Lematematika, Jerusalem. H. W. Gould, Note to the author dated 1976, Dec. W. E. Greig, "On Fibonacci and Triangular Numbers," The Fibonacci Quarterly, Vol. 15,1977, pp. 176-177. David Zeitlin, Letter to H. W. Gould, 1977, May 18. David Zeitlin, Letter to the Author, 1977, June 8. H.W. Gould and W.E. Greig, "The Lucas Primality Criterion," Amer. Math. Soc. Notices, Vol.24,1977, p. A231. H.W. Gould and W.E. Greig, "The Lucas Triangle Primality Criterion,"./ Combin. Theory, 1978, in press.

[Continued from page 165.]

*******

where the / ^ c o l u m n of Cn is t h e / ^ row of Pascal's triangle adjusted to the main diagonal and the other entries are 0's. Find Cn-AT. n n Solution by P. Bruckman, University of Illinois at Chicago, Chicago, Illinois. A. Let Bn = An-A^. Let a^ and b{j be the entries in the ith row ar\djth column of An and Bn, respectively. Similarly, let a?/ be t h e / ^ entry of AT. Then ' i ~ 1 > if i>j; = o

elsewhere;

therefore,

< = ({=!)'"

- elsewhere.