EKE Repository of Publications

Alabán, Ferenc

Irodalom a kommunikáció forgatagában

(Értekezés az irodalom fogalmának alakulásáról)

L. Erdélyi, Margit

Három könyv a kommunikációról

Szántó, Ákos

Boros-Balint, Iuliana

Simon Ugron, Agnes

A rugalmas egészségtudatossági profil (RETP) MODELL

Bíró, Melinda

Széles-Kovács, Gyula

Stregova, Zsolt

Baloga, István

Dobay, Beáta

Az Olimpiák elfeledett labdajátékai

Kiss, Ottó

A Trichopterák rendszerezésének történeti áttekintése és a magyarországi Trichoptera-kutatás

Kiss, Péter

KÖZÖS ELEMEK MÁSODRENDŰ REKURZÍV 
SOROZATOKBAN 
DR. KISS PÉTER 
Legyen G = G (A, B, Go, Gt) egy másodrendű lineáris rekurzív sorozat, 
melyet az A, B, G0 és Gi racionális egészekkel és a 
Gn = AGn-i - BGn-i (n > 1) 
rekurzív formulával definiálunk. Legyenek a és /? a sorozat 
f(x) = x2-Ax+B 
karakterisztikus polinomjának a gyökei és tegyük fel, hogy a sorozat nem 
degenerált, vagyis AB ^ O, Gq és Gi nem mindkettője nulla és a//5 nem egység-
gyök. Jól ismert, hogy a sorozat tagjainak explicit előállítása 
V1) ^n — —7T Ö ' oc — p 
ahol a — Gj — Go ^ és b — Gi—Gu a, továbbá 
(2) ' ]Gnj > c2 • |a|n n —Cs 
ha n > rí, ahol c\, c^ és rí a sorozat adataiból explicit meghatározható kons-
tansok (lásd-pl. [3]-ban). 
A G sorozat speciális esetét, amikor G„ = 0 és Gi = 1, a következőkben; 
R-^rel:jelölj ük. Az R sorozat tagjai (1) alapján 
• - - an - Bn 
(3);.: " 11,= * p 
a - nő -
alakban írhatók fel. 
(2)-ből adódik, hogy minden R és minden G sorozatban, ha a; fi nem 
egységgyök, bármely x valós szám esetén |R n | > x, illetve |G n | > x ha n > 
n0 (A, B, x), illetve n > n0 (A, B, Go, Gi, x). Ebből következik, hogy a sorozatokban 
minden elem csak véges sok elemmel lehet egyenlő. K. K. Kubota [4, 5] ennél, 
többet bizonyított: ha egy G sorozatban a//? nem egységgyök, akkor a sorozat-
ban minden elem legfeljebb négyszer fordulhat elő. F. Beukers [1] javította 
539 
ezt az eredményt, megmutatta, hogy néhány kivételtől eltekintve a négyes 
konstans hárommal helyettesíthető. 
Hasonló probléma a következző. Legyen G = G (A, B, G,0., G|) és H = 
H (A, B, Hn, Hi) két másodrendű lineáris rekurzív sorozat, melyeket ugyanazok 
az A, B konstansok definiálják. A két sorozat közül elemeinek halmaza véges-e 
vagy végtelen? Ha G és H ekvivalens sorozatok (vagyis ha G n + r = H n + s minden 
n 0 egész esetén valamely rögzített r és s természetes számok mellett) akkor 
nyilván végtelen sok közös elem létezik, ezért csak azzal az esettel érdemes 
foglalkozni, amikor G és H nem ekvivalensek. Ebben az esetben, a sorozatok 
tagjainak explicit alakja alapján, G. Revuz [8] egy általános tétele ad választ 
a kérdésre; bebizonyította, hogy ha űj (1 á L á M), bj (1 % j á N), S és cp 
algebrai szárnak, f ) és cp l ineárisan függetlenek az egész számok felett, akkor a 
M . m, N n, 
z = z y 
t - i j = i 1 
egyenletnek csak véges sok m v ríj racionális egész megoldása van, eltekintve 
attól az esettől, mikor mindkét oldal zérus. Ebből pedig következik, hogy a 
G x = H y egyenlet (x, y) megoldásainak száma is véges, vagyis valamely m0 
konstans esetén G x Hy , h a x > m,0. 
Hasonló eredményt bizonyított M. Mignotte [7]. ö a tételét tetszőleges 
rendű lineáris rekurzív sorozatokra mondta ki. állítása a mi esetünkre leszű-
kítve a következőt mondja ki: Ha D > 0 és nem egységgyök, akkor létezik 
egy effektív meghatározható m 0 konstans úgy, hogy G x 4= H y ha x, y > m 0 . 
F. Mátyás [6] különböző A, B konstansokkal generált másodrendű sorozatok 
esetéén ezeket a konstansokat explicit alakban is megadta, azonban ezek nagy-
ságrendje jelenleg még számítógéppel sem érhető el. 
Az A = —B = 1 esetre (általános Fibonacci sorozatokra) M. D.. Hirsch [2] 
konkrétabb eredményt bizonyított: Ha G (1,—l,Gr>, Gi) és H (1,—1,H0 , Hí) 
nem ekvivalens sorozatok, akkor a G és a H sorozatoknak nincs c(j/5~_ 1) -nél 
nagyobb abszolút ér tékű közös elemük, ahol c = maxOGiGg — G| | ,\HÍH2 — H\\) 
A következőkben általánosítjuk M. D. Hirsch eredményét a D = A2 —4 B > 0 
feltételnek eleget tevő általános másodrendű sorozatokra, és egyben javí t juk 
Revuz és Mignotte eredményeinek másodrendű sorozatokra vonatkozó állítá-
sát, megadva az mn konstans explicit értékét. 
Vezessük be a következő jelöléseket. Legyenek A és B rögzített nem zérus 
egészek, G = G (A, B, G0 , G() és H = H (A, B, H0 , H}) két másodrendű lineáris 
rekurzív sorozat, melyekre D = A 2 — 4 B > 0, és G 0 , Gi, illetve H0 , H t nem 
mindket tője zérus. Legyen G és H tagjainak explicit előállítása 
_a<xn-b/9n 
és 
pcLn—qfin 11
 „= Q 
a — p 
540 
ahol a = G| — Go/?, b = Gt — G0 a, p = Hi — H0 q = Ht — H0 a és tegyük 
fel, hogy a//? nem egységgyök. Továbbá legyen 
m = max( |G 0 | , \H0\ , | G j | , l i / ^ ) , 
w = max( |6 | , \q\), 
^QgÍP/Ql 
log |a | 
és 
f = min I i - l q / p l - M [ z l |q/pI • l«l|,1+1 - 1 
4' 4 ' 4 
A feltételek miatt a és fi valós és |a| 4= |/?[, ezért a továbbiakban feltehetjük, 
hogy |a| > \fi\ + 0 . 
Ezen jelöléseket felhasználva a következőket bizonyítjuk. 
2. Tétel. Ha a G és H sorozatok nem ekvivalensek és \fí\ < 1, akkor nincs olyan 
közös elemük, melyek indexei nagyobbak mint n0 + 1. 
Következmény. Az F = F (1, — 1,0, 1) Fibonacci és az L = L (1, —1, 2, 1) Lucas 
sorozatoknak csak 1 ( = F| = Fo = Lj) és 3 ( = F/, = L2) a közös elemük. Ugyanis 
ebben az esetben « = ( 1 + 5)/2, fi = (1— /5), 2 és w= Y 5, és könnyű 
ellenőrizni, hogy nn < 3. így F{ = Lj csak akkor teljesülhet az 1. Tétel miatt, 
ha i < 3 vagy j < 3. Ezekben az esetekben pedig közvetlenül belátható, hogy 
csak a felsoroltak a közös elemek. 
2 .Tétel. Ha a G és H sorozatok nem ekvivalensek, B < 0 és |/?| < 1, akkor 
nincs olyan közös elemük, melyek abszolút értéke legalább 6 mw |B|n°. 
3. Tétel. Ha a 4= 0, p =t= 0 és a G és H sorozatok nem ekvivalensek, akkor nincs 
olyan közös elemük, melyek indexei nagyobbak mint 
Megjegyezzük, hogy a 3. Tétel nem igaz. ha elhagyjuk az a 4= 0, p 4= 0 
feltételeket. Ugyanis G = G (6,8,1,4) és H = H (6, 8, 1, 2) sorozatok esetén 
A = 6, B = 8 miatt a =4, = 2 és p = H t — H() fi = 0, a tagok explicit elő-
állítása pedig Gn — 22n, Hn = 2n. így a G x = Hy egyenletnek végtelen sok meg-
oldása van, de a két sorozat nem ekvivalens. 
541 
1. Tétel bizonyítása. n 0 megválasztása miatt 
V 
a 
(az n(1 konstansnak van értelme, mert w = 0 és G x = H y esetén G és H ekviva-
lens sorozatok lennének), így \f}\ < 1 miatt 
(4) V 
a 
es V L 1 
« I 2 
ha n > n0 . Legyen G r + i = H s + ) = Q és r, s > n0 . Könnyű belátni (1) segítsé-
gével, hogy 
« « 
minden n természetes szám index esetén, ezért (4) alapján 
0 
- G , 
es 
Q
- H . — V a ' X 
Q adódik. Ebből következik, hogy G r és H s a v a l ó s számhoz legközelebbi egészek 
így G r = H s . De ez G n + i = H s + t egyenlőséggel együtt azt mutat ja , hogy a G és 
H sorozatok ekvivalensek, tehát igaz a tétel állítása. 
2. Tétel bizonyítása. Először belát juk, hogy a tétel feltételei mellett 
(5) |R n | ^ |a | 
minden n > 0 természetes szám esetén. A bizonyítást n-re teljes indukcióval 
végezzük el. n = 1 és n — 2 esetén Rí = 1 és R2 = A miat t igaz az állítás, mert 
a és különböző előjelű és így |A| = |a + < [a|. 
Ha (5) fennáll valamely n és n + 1 esetén, akkor A = a + és B = a/3 < 0 
miatt 
| Rn+21 = | ARq+1 -BRn l - l ( \A I . H - a/?) = 
cc + p 
= i/*;»+i í 
y a « J 
- H 1 = 1 « |» + 1 
a 
542 
u 
mivel —1 < — < 0, ezért (5) valóban teljesül minden n > 0 esetén. 
a 
Ezek után rátérünk a tételben szereplő állítás bizonyítására. Az n() kons-
tans megválasztása miatt 
w " (6) I /? 
a 
< 1 h a 
2 
1 . 
h a
 n
—
n
o 
(1) és (3) alapján könnyű belátni, hogy 
G n = G() a n + (G| — Go a) • R n , 
ezért (5) felhasználásával 
N = max ( |Gn | , |H n | ) ^ m | a | n + w |R n | ^ m | a | n + w l a ^ " 1 
adódik. De ha n ^ n 0 + 1 , akkor a fi = B miatt (6)-ból 
M° = I« I • W°_1 =l"|- i | ^ = J^L-w|Bi"->s2w| B !-> 
adódik. így n ~ n0 + 1 esetén, felhasználva hogy w = m m \a\ és | a | > l , 
N^ 2mw\ B | n _ I + — • 2w| B | n _ 1 =i2w| B i M w 
locl 
5 2mw| B , n . | 1 + 1 j~J ^ j < Gmw| B jno 
Ebből már következik az állítás az 1. Tétel miatt . 
3. Tétel bizonyítása. Először belátjuk, hogy a G x = Hy, vagy ami ezzel ekvi-
valens, az 
(7) a ax — b /3X = p a^ — q fiv 
egyenletnek, csak véges sok (x; y) egész megoldása van, ha G és H nem ekviva-
lens sorozatok. Tegyük fel az állítás ellenkezőjét, vagyis hogy végtelen sok 
(x; y) megoldása van (7)-nek. a + 0 és p + 0 miat t (7)-ből 
(8) - « = 
1 -Eli)' 
a *->' q\ a ) 
P 
a a 
következik. A bal oldal egész x, y esetén 1 környezetében csak diszkrét érté-
keket vehet fel, a jobb oldal határértéke viszont 1, ha x és y a végtelenhez 
tiairt, ezért végtelen sok (x;y) egész értékpárra csak akkor állhat fenn az 
egyenlőség, ha 
a
 x
~y , 
—x = 1, 
P 
vagyis 
noc = pot 
valamely (x; y) esetén. Ebből azonban b y?x = q fi? és G x + , n = H y + n adódik min-
den n természetes számra, vagyis G és H ekvivalens sorozatok. 
Tehát ha G és H nem ekvivalensek, akkor létezik olyan n\ valós szám 
úgy, hogy Gx 4= Hy, ha x, y > n^. A következőkben belátjuk, hogy a tételben 
megadott n\ rendelkezik ezzel a tulajdonsággal. 
i i a 
z megválasztása miatt jp~ ö = * z n e m efíész szám, mert ha z egész 
lenne, akkor az előzőekhez hasonlóan következne, hogy G és H ekvivalensek. 
Ekkor azonban lal > 1 miatt . 
1 
a J 
— a 
P 
ha i ^ [z] és j ^ [z] +1. Legyen 
log e — log \b/a 
es 
y 
log \P/a\ 
log £ — log q/p| 
log|/?/«| 
Nyilván x, y > nj is teljesül, ahol n\ a tételben definiált konstans. Ekko 
p l * 
b 
u 
es 
Ezeket felhasználva (8)-ból 
1 — £ 
1—4e 
1 + e 
a x-y 
—fi p 
1+e 
l—e 1 -+ 4e 
adódik, ami viszont egész x, y esetén nem teljesülhet e választása miatt. Ebből 
már következik az állítás. 
544 
IRODALOM 
1. F. Beurkers , T h e mult ipl ici ty of b ina ry recurrences , Comp. Math. , 40 (1980), 
251—267. 
2. M. D. Hirsch, Addi t ive sequences, Math , Mag., 50 (1977), 262. 
3. P. Kiss, Zero t e r m s in second o rde r l inear recur rences Math. Sem. Not. (Kobe 
Univ. Japan) , 7 (1979), 145—152. 
4. K. K. Kubota , On a con jec ture of Morgan Ward I, Acta Arithm., 33 (1977), 11—28. 
5. K. K. Kubota , On a conjec ture of Morgan Ward II, Acta Arithm., 33 (1977), 29—48. 
6. F. Mátyás, On common terms of second order l inear recurrences , Mat . Sem. 
Not. (Kobe Univ. Jappan) , 9 (1981), 89—97. 
7. M. Mignotte, Intersect ion des images de cer ta ines suites r ecur ren tes l ineaires. 
Theoret ica l Comput . Sci, 7 (1978), 117,—122 
8. G. Revuz, Equa t ions de iphant ines exponent ie l les , Bull . Soc. Math. France , Mém., 
37 (1974), 139—156. 
32* 545 
COMMON TERMS IN SECOND ORDER RECURRENCES 
by Péter Kiss 
(Summary) 
Let G = G (A, B, G0 , G[) be a second order linear recurrence defined by 
rational integers A, B, G0 , Gt and by recursion G n = AGn_|— B G n _ 2 f o r n > 1. 
We denote the roots of polynomial x2 — Ax + B by a and ft. Let us suppose 
that AB + 0, G n and G| are not both zero, D = A2 — 4B > 0, a/ft is not a root 
of unity and |a[ > | f t \ . Let H = H (A, B, Ho. H]) be also a second order linear 
recurrence with similar conditions. The sequences G and H are called equiva-
lent if there exist integers r and s such that G n + r = H n + S for every integer 
n = 0. 
The following three theorems are proved in the paper. 
Theorem 1. If the sequences G and H are not equivalent and \ft\ < 1 then the 
equation Gx = H y has no solutions with condition x,y>n{)-\-l. Theorem 2. 
If the sequences G and H are not equivalent, B < 0 and \ft\ < 1 then the 
equation G x — H y has no solutions with condition |GX | = 6 mw |B|n<> Theorem 3. 
Let the explicit fo rm of the te rms of sequences G and H be 
G n = (a an — b ftn) /(a —ft) and H n = ( p a n - q ftn) / (a — ft) 
respectively. Suppose that the sequences G and H are not equivalent and 
ap 4= 0. Then the equation G x = H y has no solutions for which x, y > n\. 
The constants n0, ni, m and w in the theorems are given in the paper and 
they depend only on the parameters of sequences G and H. 
546 


Eszterházy Károly College

Not a member yet

Irodalom a kommunikáció forgatagában (Értekezés az irodalom fogalmának alakulásáról)

Három könyv a kommunikációról

A rugalmas egészségtudatossági profil (RETP) MODELL

Az Olimpiák elfeledett labdajátékai

A Trichopterák rendszerezésének történeti áttekintése és a magyarországi Trichoptera-kutatás

Közös elemek másodrendű rekurzív sorozatban

Négyesy László verselméleti munkáinak jelentőségéről

Az elemzés kérdése az általános iskolában

Eger természeti földrajzi környezete

Kossuth adó-koncepciója a reformkorban

7,262

7,405