Egy negyedrend˝u rekurz´ıv sorozatcsal´adr´ol Peth˝o Attila∗ Eml´ek¨ ul Kiss P´eternek, a rekurz´ıv sorozatok f´aradhatatlan kutat´oj´ anak. 1. Bevezet´ es
Legyenek a, b ∈ Z ´es δ ∈ {1, −1} olyanok, hogy a2 − 4(b − 2δ) 6= 0, bδ 6= 2 ´es ha δ = 1, akkor b 6= 2a − 2, . Legyen tov´abb´a a Gn = Gn (a, b, δ), n ≥ 0 sorozat a G0 = 0, G1 = 1, G2 = a, G3 = a2 − b − δ kezd˝o´ert´ekkel ´es a Gn+4 = aGn+3 − bGn+2 + δaGn+1 − Gn ,
n≥0
(1)
rekurzi´oval defini´alva. bn = G b n (a, b, δ), n ≥ 0 sorozat a G b 0 = 4, G b 1 = a, Hasonl´ok´eppen legyen a G b 2 = a2 −2b, G b 3 = a3 −3ab+3aδ kezd˝otagokkal ´es ugyancsak az (1) rekurzi´oval G defini´alva. ol Dolgozatunkban megmutatjuk, hogy a {Gn }∞ n=0 sorozat bizonyos szempontb´ b hasonl´ok´eppen viselkedik, mint a Fibonacci, m´ıg a Gn , mint a Lucas sorozat. Pontosabban igaz os´ agi sorozat, azaz ha d|n, akkor Gd |Gn . 1. T´ etel. A {Gn }∞ n=0 oszthat´ b d |G bn . 2. T´ etel. Ha n p´ aratlan ´es d|n, akkor G Az 1. T´etelt a b = 1, 3, δ = 1 speci´alis esetekben [2] dolgozatban bizony´ıtottam. A fenti negyedfok´ u sorozatok szoros kapcsolatban ´allnak a g0 = 0, g1 = 1, illetve a gb0 = 2, gb1 = a kezd˝o´ert´ekekkel ´es gn+2 = agn+1 − (b − 2δ)gn ,
n≥0
(2)
rekurzi´oval defini´alt m´asodrend˝ u rekurz´ıv sorozatokkal. A pontos ¨osszef¨ ugg´eseket a 4. T´etelben fogalmazzuk meg. b n } ´es {b V´egezet¨ ul megmutatjuk, hogy a {Gn } ´es {gn } illetve a {G gn } sorozatok p pr´ımsz´am szerinti reduk´altjai is ¨osszef¨ uggnek. am. Akkor 3. T´ etel. Legyen p pr´ımsz´ Gp (a, b, δ) ≡ gp (a, b, δ) ∗A
(mod p) ´es
dolgozat az OTKA T42985 s T38225 p´ aly´ azatok t´ amogat´ as´ aval k´ esz¨ ult.
1
(3)
b p (a, b, δ) ≡ gbp (a, b, δ) G
(mod p).
(4)
Az 5. t´etelben megfogalmazott kongurenci´ak pr´ımsz´amok tesztel´es´ere is alkalmasak, erre a k´erd´esre azonban most nem t´er¨ unk ki.
2. Kapcsolat a {Gn } ´ es {gn } sorozatok karakterisztikus polinomjai k¨ oz¨ ott b n } karakterisztikus polinomja A {Gn } ´es persze a {G PG (x) = x4 − ax3 + bx2 − δax + 1. K¨onnyen bel´athat´o, hogy 1 PG (x) = x2
µ µ ¶2 ¶ δ δ x+ −a x+ + b − 2δ, x x
azaz az x12 PG (x) racion´alis t¨ortf¨ uggv´enyben az y = x + hajtva a Pg (y) = y 2 − ay + b − 2δ
δ x
helyettes´ıt´est v´egre-
polinomot kapjuk, amelyik a {gn } ´es {b gn } sorozatok karakterisztikus polinomja. Az a2 −4(b−2δ) 6= 0 felt´etel miatt Pg (y)-nak k´et k¨ ul¨onb¨oz˝o gy¨oke van, melyeket ε ´es ε0 -vel fogunk jel¨olni. A bδ 6= 2 felt´etel miatt b − 2δ 6= 0, ´ıgy εε0 6= 0. A kezd˝o´ert´ekek megv´alaszt´asa miatt gn =
εn − ε0n ε − ε0
´es gbn = εn + ε0n
(5)
teljes¨ ul minden n ≥ 0-ra. Legyen η a PG (x) egy gy¨oke, akkor η 6= 0 ´es ηδ is gy¨oke PG (x)-nek. A b 6= 2a − 2, ha δ = 1 felt´etel miatt η 6= ηδ . A PG (x) ´es Pg (y) polinomok k¨oz¨otti ¨osszef¨ ugg´es miatt η + ηδ gy¨oke Pg (y)-nak. Feltehet˝o, hogy η + ηδ = ε. Mivel ε 6= ε0 , ´ıgy PG (x)-nek van olyan ϑ-val jel¨olt gy¨oke, amelyre ϑ + ϑδ = ε0 . Eredm´enyeinket az al´abbi ´all´ıt´asokban foglaljuk ¨ossze. 1. Lemma. Legyen a, b, ∈ Z ´es δ ∈ {1, −1} olyanok, hogy a2 − 4(b − 2δ) 6= 0, bδ 6= 2 ´es b 6= 2a − 2, ha δ = 1. Akkor (i) Pg (x)-nek k´et null´ at´ ol k¨ ul¨ onb¨ oz˝ o gy¨ oke van ε ´es ε0 . (ii) PG (x)-nek n´egy k¨ ul¨ onb¨ oz˝ o gy¨ oke van: η, ul, hogy (iii) Teljes¨ ε=η+
δ η
´es
2
δ η,
ϑ ´es
ε0 = ϑ +
δ ϑ.
δ . ϑ
Az 1. Lemm´aban megfogalmazott tulajdons´agokat valamint a {Gn } ´es a b {Gn } sorozatok kezd˝o´ert´ekeit felhaszn´alva k¨onyen bel´athat´o, hogy ³ ´n ¡ ¢n η n + ηδ − ϑn − ϑδ Gn = ´es (6) η + ηδ − ϑ − ϑδ bn = ηn + G
µ ¶n µ ¶n δ δ + ϑn + η ϑ
(7)
teljes¨ ul minden n ≥ 0-ra.
3. Az 1. ´ es 2. T´ etel bizony´ıt´ asa Az 1. T´etel bizony´ıt´ asa. Vegy¨ uk ´eszre el˝osz¨or az µ ¶n µ ¶n µ µ ¶n ¶ δ δ δ n n n n η + −ϑ − = (η − ϑ ) 1 − η ϑ ηϑ rel´aci´ot, amelyik minden n ≥ 0-ra teljes¨ ul. Ebb˝ol ´es (6)-b´ol k¨ovetkezik, hogy ³ ´n δ n n 1 − ηϑ η −ϑ Gn = · . (8) δ η−ϑ 1 − ηϑ Az η ´es ϑ a PG (x) gy¨okei, ´ıgy egys´egek valamely algebrai sz´amtestben. Ebb˝ol δ k¨ovetkezik, hogy ηϑ is egys´eg. A definici´ob´ol nyilv´anval´o, hogy Gn ∈ Z minden n ≥ 0-ra. Legyen d ∈ N olyan, hogy d | n. Akkor Gn /Gd ∈ Q. M´asr´eszt (8)-b´ol k¨ovetkezik, hogy ³ ´n δ n n 1 − ηϑ Gn η −ϑ = d · ³ ´d . Gd η − ϑd δ 1 − ηϑ Ellemi algebrai azonoss´ag szerint η n − ϑn = η n−d + η n−2d ϑd + · · · + η d ϑn−2d + ϑn−d . η d − ϑd A jobb oldali ¨osszeadand´ok mindegyike algebrai eg´esz, ´ıgy az ¨osszeg¨ uk is az. Ugyan´ıgy l´athat´o be, hogy a m´asodik faktor is algebra eg´esz, ´ıgy Gn /Gd egy olyan algebrai eg´esz sz´am, amelyik Q-ban van. Ez pedig csak akkor lehets´eges, ha Gn /Gd ∈ Z. ¤ Az 2. T´etel bizony´ıt´ asa. Ez hasonl´o, mint az 1. T´etel bizony´ıt´asa. Azt kell csak ´eszrevenn¨ unk, hogy µ ¶n µ ¶n µ µ ¶n ¶ δ δ δ n n n n , (9) η + +ϑ + = (η + ϑ ) 1 + η ϑ ηϑ 3
valamint ha n p´aratlan ´es d | n, akkor ³ n
n
η +ϑ η d + ϑd
illetve
1+ ³ 1+
δ ηϑ δ ηϑ
´n ´d
algebrai eg´eszek.
¤
1. Megjegyz´es. Az oszthat´o rekurz´ıv sorozatokat Beziven, Peth˝o ´es van der b n } sorozatoknak Poorten [1] karakteriz´alt´ak. Az ´altalunk defini´alt {Gn } ´es {G az az ´erdekess´ege, hogy b´ar (8) illetve (9) szerint felbomlanak k´et m´asodrend˝ u line´aris rekurziv sorozat szorzat´ara, a faktorok azonban ´altal´aban nem racion´alis eg´eszek. Ez t¨ort´enik p´eld´aul, ha b = −1 vagy −3 ´es δ = −1. Az F0 = 0, F1 = 1, Fn+2 = Fn+1 + Fn kezd˝o´ert´ekekkel, illetve rekurzi´oval defini´alt Fibonacci sorozat jelenti az iskolap´eld´at oszthat´o rekurz´ıv sorozatokra. Erre k¨ony˝ u olyan bizony´ıt´ast adni (ld. pl. [3]), amelyik csak az eg´esz sz´amok b n } sorozatokra nem aritmetik´aj´at haszn´alja. Hasonl´o bizony´ıt´ast a {Gn } ´es a {G siker¨ ult tal´alnom. n
n
−β 2. Megjegyz´es. A Fibonacci sorozatokra, s˝ot az ´altal´anosabb Rn = αα−β 2 sorozatokra, ahol α ´es β az α x − r1 x − r0 , r1 , r0 ∈ Z polinom gy¨okei, az 1. T´eteln´el er˝osebb (Rn , Rd ) = R(n,d) rel´aci´o is teljes¨ ul. Ez ´altal´aban nem igaz az ´altalunk defini´alt {Gn } sorozatokra. Tekints¨ uk p´eld´aul az
n Gn
0 0
1 1
2 1
3 5
4 7
5 20
6 35
7 83
8 161
9 355
10 720
sorozatot, amelyik a Gn+4 = Gn+3 + 3Gn+2 − Gn+1 − Gn rekurzi´onak tesz eleget. Akkor p´eld´aul (G3 , G5 ) = 5 6= G1 ´es (G4 , G6 ) = 7 6= G2 . K¨onnyen lehet persze tov´abbi p´eld´akat is tal´alni, ez´ert ´erdekes k´erd´es a {Gn } b n } sorozatokra a tagok legnagyobb k¨oz¨os oszt´oj´anak jellemz´ese. ´es {G
4. A 3. T´ etel bizony´ıt´ asa Az 3. T´etel bizony´ıt´ asa. A (8), (9) valamint a 1. Lemma (iii) rel´aci´okat haszn´aljuk a bizony´ıt´asban. Legyen p egy pr´ımsz´am. Ha p = 2, akkor (3) ´es (4) a sorozatok kezd˝o´ert´ekei megv´alaszt´ asa miatt teljes¨ ul. A tov´abbiakban teh´at feltehet˝o,
4
hogy p p´aratlan. Akkor ´p ¡ ³ ¢p δ − ϑ + ϑδ η + p 0p η ε −ε = ε − ε0 ε − ε0 ¡ ¢p−2i ´ P ¡p¢ i ³ p−2i ¡ δ ¢p−2i − ϑp−2i − ϑδ η + ϑ i δ
p−1 2
=
i=0
p−1 p−2i 2 µ ¶ + X p iη = δ i i=0
ε − ε0 ³ ´p−2i δ η
η+
δ η
− ϑp−2i − −ϑ−
¡ δ ¢p−2i ϑ
δ ϑ
p−1 2 µ ¶ X p i = δ Gp−2i . i i=0
Mivel
¡p¢ i
minden 1 ≤ i ≤ p − i-re oszthat´o p-vel , ´ıgy az el˝oz˝o azonoss´agb´ol gp ≡ Gp
(mod p),
azaz (3) k¨ovetkezik. A (4) kongruencia hasonl´ok´eppen ellen˝orizhet˝o.
¤
3. Megjegyz´es. A (3) ´es (4) kongruenci´ak nem pr´ımkrit´eriumok, azaz vannak olyan ¨osszetet sz´amok, amelyekre (3) illetve (4) teljes¨ ul. A Fibonacci sorozat ´es a 2. Megjegyz´esben megadott sorozat p´eld´aul az (a, b, δ) = (1, −3, −1) param´eterekkel vannak defini´alva. A 0 ≤ n ≤ 10000 intervallumban az n = 15, 25, 45, 121, 125, 375, 525, 625, 1125, 1605, 2205, 2375, 3125, 4375, 5425, 8925 ´es 9375 ¨osszetett sz´amokra is teljes¨ ul (3).
5. Tov´ abbi ¨ osszef¨ ugg´ esek a {Gn } bn } ´ ´ es {gn } illetve a {G es {b gn } sorozatok k¨ oz¨ ott b n } ´es {b Az el˝obbiekben l´athattuk, hogy a {Gn } ´es {gn } illetve {G gn } sorozatok k¨oz¨ott szoros kapcsolat van. A 4. r´eszben p´eld´aul bel´attuk, hogy p´aratlan p eg´eszre gp kifejezhet˝o Gp , Gp−2 , . . . , G1 eg´esz egy¨ utthat´os line´aris kombin´aci´ojab p ) szeretn´enk k´ent. Most az ellenkez˝o ir´any´ u kapcsolatot vizsg´aljuk, azaz Gp -t (G kifejezni a {gn } ({b gn }) sorozat elemei line´aris kombin´aci´ojak´ent. A k¨ovetkez˝o ´all´ıt´as biztosan ismert, de nem siker¨ ult referenci´at tal´alnom. (j)
2. Lemma. Defini´ aljuk a {λi } i≥0 sorozatot a k¨ ovetkez˝ ok´eppen: j≥2
(0)
(0)
(1)
(1)
λ0 = 2, λ1 = 0, λ0 = 1, λ1 = 0 ´es (2k+2)
λ0
(2k)
= −λ0
(2k+2)
, λk+1
(2k+1)
= λk
(2k+2)
, λi 5
(2k+1)
= λi−1
(2k)
− λi
, 1≤i≤k
´es
(2k+3)
λ0
(2k+3)
= 0, λk+1
(2k+2)
= λk+1
(2k+3)
, λi
(2k+2)
= λi
(2k+1)
− λi
, 1 ≤ i ≤ k.
Ha 0 ≤ n = 2k + e, ahol e ∈ {0, 1}, akkor Xn + Y n =
k X
(n)
λi (X + Y )2i+e (XY )k−i .
i=0
Bizony´ıt´ as. Egyszer˝ u teljes indukci´o, felhaszn´alva az X n+1 + Y n+1 = (X n + Y n )(X + Y ) − XY (X n−1 + Y n−1 ) azonoss´agot.
¤ (n)
[n 2 ]−i
3. Lemma. B´ armely n ≥ 0 ´es 0 ≤ i ≤ [ n2 ]-re λi (−1)
≥ 0.
Bizony´ıt´ as. A 2. Lemm´aban le´ırtak miatt ( 2(−1)[n/2] , ha n p´aros (n) (n) λ[n/2] = 1 ´es λ0 = . 0, ha n p´aratlan ´Igy az ´all´ıt´as igaz minden n-re ´es i = 0, [ n ]-re. Tegy¨ uk fel, hogy igaz minden 2 m < n-re ´es legyen 0 < i < [ n2 ]. Ha n p´aros, mondjuk n = 2k + 2 ´es 0 < i < k + 1, akkor (2k+2)
λi
(2k+1)
(−1)k+1−i − λi
(2k+1)
(−1)[
(−1)k+1−i = λi−1 = λi−1
(2k)
(−1)k+1−i
2k+1 2 ]−(i−1)+2
(2k)
+ λi
(−1)k−i+2 .
A jobb oldalon ´all´o kifejez´esben az indukci´os hipot´ezis szerint mindk´et ¨osszeadand´o nem negat´ıv, ´ıgy az ¨osszeg¨ uk is az. Ha pedig n p´aratlan, p´eld´aul n = 2k + 3 ´es 0 < i < k + 1, akkor (2k+3)
λi
(2k+2)
(−1)k+1−i − λi
(2k+2)
(−1)[
(−1)k+1−i = λi = λi
(2k+1)
2k+2 2 ]−i
(−1)k+1−i
(2k+1)
+ λi
(−1)[
2k+1 2 ]−i+2
´es az el˝obbi esethez hasonl´oan k¨ovetkeztethet¨ unk arra, hogy a kifejez´es nem negat´ıv. ¤ 4. T´ etel. Legyenek a, b, δ a Bevezet´esben megfogalmazott felt´eteleknek eleget tev˝ o eg´esz sz´ amok ´es 0 ≤ n = 2k + e, ahol e ∈ {0, 1}. Akkor k P (n) ha δ = 1 λi g2i+e (a, b, δ), Gn (a, b, δ) = i=0 k P |λ(n) | g2i+e (a, b, δ), ha δ = −1, i i=0
´es b n (a, b, δ) = G
k P (n) λi gb2i+e (a, b, δ),
ha δ = 1
ha δ = −1.
i=0 k P
i=0
(n)
|λi
| gb2i+e (a, b, δ),
6
Bizony´ıt´ as. Csak az els˝o ´all´ıt´ast bizony´ıtjuk, mert a m´asodik bizony´ıt´asa teljesen hasonl´o. Az a, b ´es δ argumentumokat elhagyjuk a tov´abbiakban. A (6) azonoss´agot ´es a 2. Lemma ´all´ıt´as´at felhaszn´alva ³ ´n ³ ¡ ¢n ´ η n + ηδ − ϑn + ϑδ Gn = ε − ε0 Ã k ¶2i+e µ ¶k−i X ¶2i+e µ ¶k−i ! µ k X (n) µ 1 δ δ δ δ (n) = η − ϑ λi ϑ+ λ η+ ε − ε0 i=0 i η η ϑ ϑ i=0 = =
k ¢ 1 X (n) k−i ¡ 2i+e λi δ ε − ε02i+e 0 ε − ε i=0 k X
(n)
λi δ k−i g2i+e .
i=0
Felhaszn´alva v´eg¨ ul a 3. Lemm´at, kapjuk az ´all´ıt´ast.
¤
References ´zivin, A. Petho ˝ and A.J. van der Poorten, A full characteri[1] J.P. Be zation of divisibility sequences, Amer. J. Math., 112 (1990), 985-1001. ˝ , Complete solutions to a family of quartic diophantine equations, [2] A. Petho Math. Comp. 57 (1991), 777-798. [3] N.N. Vorobjev, Fibonacci Numbers (in Russian), sixth edition, Nauka Moskau, 1978. Debreceni Egyetem Sz´am´ıt´og´eptudom´anyi Tansz´ek H-4010 Debrecen, Pf. 12 e-mail:
[email protected]
7
