Separatum
ACTA ACADEMIAE PAEDAGOGICAE AGRIENSIS NOVA SERIES TOM. XXII.
SECTIO MATEMATICAE
´ ACS ´ TOM TIBOR Egy rekurz´ıv sorozat tagjainak ´ atlag´ ar´ ol
EGER, 1994
Egy rekurz´ıv sorozat tagjainak ´ atlag´ ar´ ol ´ ACS ´ TOM TIBOR
Abstract. (Avarage order of the terms of a recursive sequence) For a fixed positive integer k ≥ 2 let the sequence Gk (n) of natural numbers be defined by Gk (0) = 0 and
Gk (n) = n − Gk Gk . . . Gk (n − 1) . . . , (n ≥ 1) with k iterations of Gk on the right-hand side. Denote by α1 = α, α2 , α3 , . . . , αk the roots of the characteristic polynomial f (x) = xk − xk−1 − 1 of the generalized Fibonacci sequence bn . It is known that these roots are distinct and that there is a positive root among them with the greatest modulus, thus we can suppose that α > |α2 | ≥ |α3 | ≥ · · · ≥ |αk | > 0 (see e. g. [1]). In [2] P. Kiss proved that for any positive integer n, large enough, and PN k ≥ 2 we have N1 i=1 Gk (i) = v1 N + v2 αn2 + v3 αn3 + o(αn2 ) + O(1), where N = bn+1 and v1 , v2 , v3 are constants depending only on k. In this paper we generalize this result.
Legyen k ≥ 2 r¨ ogz´ıtett eg´esz sz´ am. Defini´ aljuk a term´eszetes sz´amok egy Gk (n), n = 0, 1, 2, . . . sorozat´ at a Gk (0) = 0 kezd˝ o elemmel ´es a Gk (n) = n − Gk Gk . . . Gk (n − 1) . . .
rekurz´ıv formul´ aval n > 0 esetre, ahol a jobb oldalon Gk -nak k-szoros iter´ aci´ oja van. Bel´ athat´ o, hogy a sorozat minden tagja j´ ol defini´ alt term´eszetes sz´ am (l´ asd Zay B. [4]). Legyen n, ha n = 1, 2, . . . , k, bn = bn−1 + bn−k , ha n > k a Fibonacci sorozat k-adrend˝ u a´ltal´ anos´ıtott sorozata. Egy m pozit´ıv eg´esz eset´en tekints¨ uk azt a legnagyobb i1 eg´esz sz´ amot, melyre bi1 ≤ m teljes¨ ul. Legyen m1 = m − bi1 . Ha m1 6= 0, v´ alasszuk a legnagyobb i2 eg´esz sz´ amot, melyre bi2 ≤ m1 . Legyen m2 = m1 − bi2 . Ha m2 6= 0, folytassuk az elj´ ar´ ast. Ez az algoritmus v´eges sok l´ep´esben befejez˝ odik. ´Igy minden pozit´ıv eg´esz sz´ am egy´ertelm˝ uen fel´ırhat´ o bn sorozatbeli elemek o¨sszegek´ent (1)
m=
j X i=1
ai bi
32
T´ om´ acs Tibor
alakban, ahol ai = 1 vagy 0. Jel¨ olj¨ uk ezt r¨ oviden m = aj aj−1 . . . a1 m´ odon. Defini´ aljuk a Tk (m) sorozatot Tk (0) = Tk (1) = 0 kezd˝ o ´ert´ekkel ´es a (2)
Tk (m) = aj aj−1 . . . a2 =
j X
ai bi−1
(m > 1)
i=2
formul´ aval, ahol az ai sz´ amok m-nek (1)-ben difini´ alt el˝ oa´ll´ıt´ as´ aban szerepl˝ o egy¨ utthat´ oi. A Gk (n) ´es Tk (n) sorozatok szoros kapcsolatban vannak egym´ assal, D. S. Meek ´es G. H. J. Van Rees [3]-ban bizony´ıtott´ ak, hogy (3)
Gk (n) = Tk (n − 1) + 1
(n ≥ 1).
Jel¨ olj¨ uk α1 = α, α2 , α3 , . . . , αk -val a bn sorozat karakterisztikus polinomj´ anak — az xk − xk−1 − 1 polinomnak — a gy¨ okeit. Ismert, hogy van a gy¨ ok¨ ok k¨ oz¨ ott egy legnagyobb abszol´ ut ´ert´ek˝ u pozit´ıv val´ os gy¨ ok, ez´ert feltehetj¨ uk, hogy (4)
α > |α2 | ≥ |α3 | ≥ · · · ≥ |αk | > 0,
ahol α > 1 val´ os sz´ am (l´ asd K. Dilcher [1]). Kiss P´eter [2]-ben a Gk (n) sorozat tagjainak a´tlag´ at vizsg´ alta, ´es bizony´ıtotta, hogy el´eg nagy n eg´eszek eset´en (5)
N 1 X Gk (i) = v1 N + v2 αn2 + v3 αn3 + o(αn2 ) + O(1), N i=1
ahol N = bn+1 ´es a v1 , v2 , v3 csak k-t´ ol f¨ ugg˝ o val´ os konstansok. u eg´eszek Ezen dolgozat c´elja megmutatni, hogy nemcsak N = bn+1 alak´ eset´en igaz az (5) formula. A k¨ ovetkez˝o t´eteleket bizony´ıtjuk: 1. T´ etel. Legyenek k ≥ 2 ´es t r¨ ogz´ıtett pozit´ıv eg´eszek. Ekkor el´eg nagy pozit´ıv n eg´eszek eset´en N 1 X 1 Gk (i) = v1 N + v2 αn2 + v3 αn3 + O(1) + o(αn2 ) , N i=1 1 + o(1)
33
Egy rekurz´ıv sorozat tagjainak a ´tlag´ ar´ ol
ahol N = bn+1 + t ´es a v1 , v2 , v3 csak k-t´ ol f¨ ugg˝ o konstansok. 2. T´ etel. Legyenek k ≥ 2 ´es t ≥ k r¨ ogz´ıtett eg´eszek. Ekkor el´eg nagy pozit´ıv n eg´eszek eset´en N 1 1 X Gk (i) = v1′ N + v2′ αn2 + v3′ αn3 + O(1) + o(αn2 ) , N i=1 1 + o(1)
ahol N = bn+1 + bn−t+1 , ´es a v1′ , v2′ , v3′ csak k-t´ ol ´es t-t˝ ol f¨ ugg˝ o konstansok. Megjegyz´ es. Az 1. t´etelben a v1 , v2 , v3 konstansok megegyeznek az (5)-ben tal´ alhat´ o konstansokkal. ´ ´ 1. TETEL BIZONY´IT ASA. Vizsg´ aljuk a
(6)
Gk (i) o¨sszeget. Bontsuk fel
i=1
k´et tagra az al´ abbi m´ odon. N X
N P
bn+1
Gk (i) =
i=1
X
Gk (i) +
i=1
N X
Gk (i)
i=bn+1 +1
Az els˝ o o¨sszeg [2] szerint bn+1
(7)
X
Gk (i) = r1 α2n + r2 αn αn3 + r3 αn αn3 + r4 α2n 2 +
i=1
n n n n n + r5 α2n 3 + r6 α2 α3 + O(α ) + O(α α4 )
alakban ´ırhat´ o fel, ahol ri b´ ol N X
(i = 1, 2, 3, 4, 5, 6)
k-t´ ol f¨ ugg˝ o konstansok. (3)-
Gk (i) = Tk (bn+1 ) + 1 + Tk (bn+1 + 1) + 1 + · · · + Tk (N − 1) + 1 =
i=bn+1 +1
= N − bn+1 +
N −1 X
bn+1 +t−1
Tk (i) = t +
i=bn+1
X
Tk (i)
i=bn+1
k¨ ovetkezik. El´eg nagy n eset´en teljes¨ ul, hogy t < bn−k+2 , ez´ert N < bn+2 . ´Igy Tk (i) definici´ oja miatt minden bn+1 ≤ i ≤ bn+1 + t − 1 eg´esz eset´en Tk (i) = bn + Tk (i − bn+1 ). Ebb˝ ol k¨ ovetkezik, hogy N X
i=bn+1 +1
Gk (i) = t + tbn +
t−1 X i=0
Tk (i).
34
T´ om´ acs Tibor
Ebben az o¨sszegben az n-t˝ ol f¨ uggetlen tagok o¨sszeg´et jel¨ olj¨ uk fk,t-vel. Teh´ at fk,t := t +
t−1 X
Tk (i).
i=0
ok Ismert, hogy a bn sorozat tagjai fel´ırhat´ bn = c1 αn + c2 αn2 + · · · + ck αnk
(8) alakban, ahol ci Dilcher [1]). Ez´ert
(i = 1, 2, . . . , k) csak k-t´ ol f¨ ugg˝ o komplex konstansok (K.
N X
Gk (i) = fk,t + t(c1 αn + c2 αn2 + · · · + ck αnk ).
i=bn+1 +1
Az α > 1 val´ os sz´ am, m´ asr´eszt (4) miatt fk,t + t(c1 αn + c2 αn2 + · · · + ck αnk ) ≤ fk,t αn + tc1 αn + tc2 αn2 + · · · + tck αnk ≤ ≤ (fk,t + tc1 + tc2 + · · · + tck )αn . Ebb˝ ol k¨ ovetkezik, hogy N X
(9)
Gk (i) = O(αn ).
i=bn+1 +1
(6), (7) ´es (9)-b˝ ol ad´ odik, hogy
(10)
N X
Gk (i) = r1 α2n + r2 αn αn2 + r3 αn αn3 + r4 α2n 2 +
i=1
n n n n n + r5 α2n 3 + r6 α2 α3 + O(α ) + O(α α4 ),
tov´ abb´ a (8)-b´ ol (11) N = bn+1 + t = s1 αn + s2 αn2 + · · · + sk αnk + t = s1 αn + O(αn2 ) + t, ahol si = ci αi
(i = 1, 2, . . . , k). Felhaszn´ alva (11)-et
N N N P P P Gk (i) Gk (i) Gk (i) N X 1 i=1 i=1 i=1 + Gk (i) = = O(αn )+t N i=1 s1 αn + O(αn2 ) + t s1 αn (1 + o(1)) s1 αn 1 + s1 2αn
Egy rekurz´ıv sorozat tagjainak a ´tlag´ ar´ ol
35
ad´ odik, amib˝ ol (10) alapj´ an kapjuk az N α n α n 1 X 2 3 Gk (i) = p1 αn + p2 αn2 + p3 αn3 + p4 αn2 + p5 αn3 + N i=1 α α
(12)
α α n 1 2 3 n + p6 + O (α4 ) + O(1) α 1 + o(1) becsl´est, ahol pi =
ri s1
(i = 1, 2, . . . , k). De
p1 αn = (s1 αn + s2 αn2 + · · · + sk αnk + t) −
p1 p1 p1 s3 αn3 − · · · − sk αnk − t. s1 s1 s1
p1 p1 − s2 αn2 − s1 s1
Mivel s1 αn + s2 αn2 + · · · + sk αnk + t = N , tov´ abb´ a (4) miatt −
p1 p1 p1 s4 αn4 − s5 αn5 − · · · − sk αnk = O(αn4 ), s1 s1 s1
´es − ´ıgy v1 :=
p1 s1 ,
p1 t = O(1), s1
d2 := − ps11 s2 , d3 := − ps11 s3 jel¨ ol´essel p1 αn = v1 N + d2 αn2 + d3 αn3 + O(αn4 ) + O(1)
(13)
ad´ odik.Tudjuk m´eg, hogy (14)
p4
α n 2
α
αn2 + p5
α n 3
α
αn3 + p6
α α n 2 3 + O (αn4 ) = o (αn2 ) . α
Ez´ert (12), (13) ´es (14) alapj´ an N 1 X 1 Gk (i) = v1 N + v2 αn2 + v3 αn3 + O(1) + o(αn2 ) , N i=1 1 + o(1)
ami a t´etel¨ unket bizony´ıtja. A bizony´ıt´ as sor´ an a konstansok ´ert´ek´et nem befoly´ asolta t, ´ıgy val´ oban igaz a megjegyz´es a´ll´ıt´ asa is.
36
T´ om´ acs Tibor ´ ´ 2. TETEL BIZONY´IT ASA. (1), (2), (3) ´es (7) alapj´ an N X
bn+1 −1
Gk (i) =
bn−t+1 −1
X
Tk (i) = i=1 i=1 2n = x1 α2n + x2 αn αn2 + x3 αn αn3 + x4 α2n 2 + x5 α3 + + x6 αn2 αn3 + O(αn ) + O(αn αn4 ) + N + bn bn−t+1 ,
i=1
ahol
X
Tk (i) + N + bn−t+1 bn +
xi = ri 1 +
1 1 (i = 1, 2, 3), x4 = r4 1 + 2t , αt αti α2 1 1 x5 = r5 1 + 2t ´es x6 = r6 1 + t t . α3 α2 α3
A tov´ abbiakban n
bn bn−t+1 = (c1 α +
c2 αn2
+ ··· +
ck αnk )
s1 n s2 n sk α + t α2 + · · · + t αnk αt α2 αk
=
2n n n n n = z1 α2n + z2 αn αn2 + z3 αn αn3 + z4 α2n 2 + z5 α3 + z6 α2 α3 + O (α α4 )
felhaszn´ al´ as´ aval, ahol z1 =
s21 , αt+1
z4 =
z2 =
s22 , αt+1 2
s1 s2 s1 s2 , t + t αα2 α α2
z5 =
s23 , αt+1 3
z3 =
z6 =
s1 s3 s1 s3 , t + t αα3 α α3
s2 s3 s2 s3 + t , t α2 α3 α2 α3
a t´etel hasonl´ oan bizony´ıthat´ o, mint az el˝ oz˝ o. Megjegyz´ es. Kisz´ amolva v1 ´es v1′ konstansokat v1′
=
tov´ abb´ a c1 α1−4k v1 = + α−4k α−1
r1 1 +
1 α2t
s21 1 +
s2
1 + αt+1 , 1 2
αt
k X cq α2q α2 − αq q=2
!
+ α−4k
α2k − 1 1 + 2 2 α −1 2α
ad´ odik. Bel´ athat´ o behelyettes´ıt´essel, hogy k = 2 ´es k = 3 eset´en v1 = v1′ . A sejt´es az, hogy ez minden k ≥ 2 eset´en teljes¨ ul, vagyis a 2. t´etelben defini´ alt N -re is igaz az (5) formula.
Egy rekurz´ıv sorozat tagjainak a ´tlag´ ar´ ol
37
r1 . c21 α2
Ez´ert v1 = v1′ akkor
Az 1. t´etel bizony´ıt´ as´ ab´ ol l´ athat´ o, hogy v1 =
´es csak akkor teljes¨ ul, ha c21 α = 2r1 . Vissza´ırva r1 -et v1 -be kapjuk, hogy a 1 a´ll´ıt´ assal. sejt´es ekvivalens a v1 = 2α
Irodalom [1] K. DILCHER , On a class of iterative recurrence relations, Fibonacci Quart., (to appear). [2] P. KISS, Avarage order of the terms of a recursive sequence, Proc. of the Austrian-Hungarian-Slovak. Number Theory Coll., Graz, (1992), (to appear). [3] D. S. MEEK and G. H. J. VAN REES, The solution of an iterated recurrence, Fibonacci Quart., 22 (1984), 101–104. [4] ZAY B.: Egy rekurz´ıv sorozatr´ ol. Acta Academiae Paedagogicae Agriensis, Sectio Mat., (megjelen´es alatt).
