Cím: Néhány érdekesség a Fibonacci- és a Fibonacci-típusú sorozatokról II. rész
Szerző(k):  Énekes Béla ,  Kós Géza 
Füzet: 2001/január, 3 - 9. oldal  PDF file
Témakör(ök): Szakmai cikkek

A szöveg csak Firefox böngészőben jelenik meg helyesen. Használja a fenti PDF file-ra mutató link-et a letöltésre.

Előző számunkban a ,,Fibonacci-típusú'' sorozatoknak, illetve magának a Fibonacci sorozatnak több érdekes tulajdonságát bebizonyítottuk. Most ezek felhasználásával különböző megoldásokat adunk az A. 244. feladatra. A definíciók, tételek és lemmák számozását nem kezdjük újra, mivel többször hivatkozni fogunk a cikk első részében leírtakra.

 
A. 244. Egy számsorozatot nevezzünk Fibonacci-típusúnak, ha a harmadiktól kezdve mindegyik eleme az előző kettő összege. Bizonyítsuk be, hogy a pozitív egész számok halmaza felbontható olyan Fibonacci-típusú végtelen sorozatok uniójára, amelyek közül semelyik kettőnek nincs közös eleme.
 
 
 
I. megoldás az A. 244. feladatra
 
 

Elsőként a feladatnak egy olyan megoldását vizsgáljuk meg, amely két, önmagában is érdekes segédsorozat felhasználásával konstruálja meg a kívánt felbontást.
 
2. definíció. Definiáljuk az A=(a0,a1,...) és a B=(b0,b1,...) sorozatokat a következőképpen:
*(1) Legyen a0=b0=1;
*(2) ha a0, ..., an-1-et és b0, ..., bn-1-et már definiáltuk, akkor legyen an az a legkisebb pozitív egész, amelyik nem szerepel az a0, a1, ..., an-1, b0, b1, ..., bn-1 értékek között;
*(3) legyen bn=an+n.

A következő táblázat tartalmazza az A és B első néhány elemét:
n012345678910an1245791012131517bn136811141619212427n1112131415161718192021an1820222325262830313334bn2932353740424548505355

A megoldás kulcsa a következő lemma.
 
5. lemma. Tetszőleges n nemnegatív egészre
abn=an+bn.

A lemma bizonyításához további lemmákra lesz szükségünk.
 
6. lemma. Az A és a B sorozat is szigorúan monoton nő, a0=b0=1-től eltekintve nincs közös elemük, továbbá minden egyes pozitív egészt tartalmazza valamelyik sorozat.
 
7. lemma. Az A és a B elemeire teljesülnek a következő egyenlőtlenségek:
an+1an+1an+2;(9a)bn+2bn+1bn+3;(9b)an+3an+2an+4;(9c)bn+5bn+2bn+6.(9d)

 
7. feladat. Igazoljuk a 6. és a 7. lemmát.
 
8. lemma. Tetszőleges n nemnegatív egészre
aan=bn+1.(11)

 
Bizonyítás. Teljes indukcióval bizonyítunk. Az n=0 esetben b0+1=1+1=2=a+1=aa0.
Tegyük fel, hogy az állítás teljesül n=m-re, azaz aam=bm+1; ebből bebizonyítjuk az n=m+1 esetre is. A bm+1+1 szám a (9b) alapján nem szerepelhet a B sorozatban, tehát az A sorozatban szerepel: bm+1+1=ak valamilyen k-ra. Azt kell igazolnunk, hogy k=am+1.
A (9a) egyenlőtlenség szerint am+1am+1am+2. Ha am+1=am+1, akkor bm+1=bm+2, és ak=bm+1+1=(bm+1)+2=aam+2. (Az utolsó lépésben az indukciós feltevést alkalmaztuk.) A (9a) és (9c) egyenlőtlenségek szerint ez csak úgy lehetséges, ha k=am+1=am+1.
Ha am+1=am+2, akkor bm+1=bm+3, és ak=bm+1+1=(bm+1)+3=aam+3. (Az utolsó lépésben ismét az indukciós feltevést alkalmaztuk.) A (9a) és (9c) egyenlőtlenségek szerint ez csak úgy lehetséges, ha k=am+2=am+1. Ezzel a lemmát igazoltuk.
 
9. lemma. Tetszőleges n pozitív egészre
abn-2=abn-3;(12a)abn-1=abn-1;(12b)abn+1=abn+2.(12c)

 
Bizonyítás. Először a (12b) egyenlőséget igazoljuk. Tegyük fel, hogy az állítás hamis; ekkor abn=abn-1+2, és az abn-1+1=abn-1 szám a B sorozatban van: abn-1=bk valamilyen k-ra. A 8. lemma szerint bk+1=aak, tehát abn=bk+1=aak. Az A sorozat monotonitása miatt ebből következik, hogy ak=bn, ami ellentmond annak, hogy az A és a B sorozatnak az a0=b0=1-en kívül nincs közös eleme. A (12b) tehát teljesül.
A (9a) és (9c) egyenlőtlenségek alapján abn-2abn-3 és abn-2abn-1-2=abn-3; ezekből (12a) következik.
Szintén a (9a) és (9c) egyenlőtlenségek alapján abn+1abn+2 és abn+1abn-1+3=abn+2; tehát (12c) is igaz.
Most már rátérhetünk az 5. lemma bizonyítására.
 
Az 5. lemma bizonyítása. A bizonyításhoz ismét a teljes indukciót használjuk. Az állítás igaz n=0-ra: ab0=a1=2=1+1=a0+b0.
Tegyük fel, hogy az állítás igaz nm esetén, ebből bebizonyítjuk n=(m+1)-re is. Ismét két esetet vizsgálunk aszerint, hogy am+1=am+1 vagy am+1=am+2.
Ha am+1=am+1, akkor bm+1=bm+2 és am+1+bm+1=am+bm+3=abn+3. Másrészt a 8. lemma alapján
abm+1=abm+1-1+1=abm+1+1=(abm+2)+1=abm+3.
Ebben az esetben tehát am+1+bm+1=abm+1.
Ha am+1=am+2, akkor bm+1=bm+3 és am+1+bm+1=am+bm+3=abn+5. A 8. lemma alapján
abm+1=abm+1-2+3=abm+1+3=(abm+2)+3=abm+5.
Az állítás ebben az esetben is teljesül. A lemmát ezzel bebizonyítottuk.
Az 5. lemma segítségével könnyen megkonstruálható az A. 244. feladatban kívánt felbontás, erről szól a következő tétel.
 
6. tétel. Tekintsük az összes olyan (am,bm) paraméterű Fibonacci-típusú sorozatot, amelyre az m nemnegatív egész szám nem szerepel a B sorozatban. Az összes pozitív egész szám pontosan egy ilyen sorozatban szerepel.
 
Bizonyítás. Ha valamely m-re am és bm egy Fibonacci-típusú sorozat két egymás utáni eleme, akkor az 5. lemma és a B sorozat definíciója alapján a következő két elem am+bm=abm, illetve abm+bm=bbm. Ezt a gondolatmenetet megismételve láthatjuk, hogy az (am,bm) paraméterű sorozat elemei
am1,bm1,am2,bm2,am3,bm3,...
alakban írhatók, ahol m1=m és mi+1=bmi.
Tetszőleges (am,bm) számpárhoz egyértelműen meghatározható, hogy melyik számpár áll előtte a megfelelő sorozatban. Ha m a B sorozatban szerepel, azaz m=bk valamely k-ra, akkor ez az (ak,bk) számpár. Ha m nem szerepel a B sorozatban, akkor az (am,bm) számpár a megfelelő paraméterű sorozat első két eleme. Ezen a módon visszafelé lépkedve, mindegyik pozitív egész számról egyértelműen eldönthető, hogy melyik sorozatban szerepel. Ezzel a tételt bebizonyítottuk.
A következő táblázatban felsoroltuk az első néhány sorozatot.
mam1bm1am2bm2am3bm3am4bm401123581321...2461016264268110...471118294776123199...591423376097157254...71219315081131212343...915243963102165267432...

 
 

 
II. megoldás az A. 244. feladatra
 
 

Másodszor egy olyan megoldást mutatunk, amely egy többé-kevésbé természetes konstrukciót ad a keresett felbontásra.
Képzeljük el, hogy a pozitív egész számok halmazát már felbontottuk páronként diszjunkt Fibonacci-típusú sorozatok uniójára. Legyen f az a függvény, ami minden egyes pozitív egészhez hozzárendeli az őt tartalmazó egyetlen sorozat következő elemét. Tehát tetszőleges n pozitív egészre az n-et tartalmazó sorozatban az n után az f(n), azután pedig az f(f(n)) következik. Mivel a sorozat Fibonacci-típusú, szükséges, hogy f(f(n))=f(n)+n teljesüljön. Az f függvény tehát pozitív egész számokhoz pozitív egész számokat rendel, és teljesül rá az f(f(n))=f(n)+n függvényegyenlet.
Megoldásunk az iménti gondolatmenet megfordításával működik. Először megadunk egy f függvényt, amire teljesül a talált függvényegyenlet. Ezután definiáljuk a megfelelő Fibonacci-típusú sorozatokat.
 
3. definíció. Definiáljuk az f függvényt a következőképpen:
1. Legyen f(1)=2;
2. Ha f(1), ..., f(n-1)-et már definiáltuk, és az n nem szerepel ezek között, akkor legyen f(n)=f(n-1)+1;
3. Ha f(1), ..., f(n-1)-et már definiáltuk, és az n szerepel ezek között, akkor legyen k a legkisebb pozitív egész, amelyre f(k)=n, és legyen f(n)=n+k.

Az alábbi táblázat tartalmazza f első néhány értékét.
n123456789101112131415f(n)2356810111314161819212324n161718192021222324252627282930f(n)262729313234353739404244454748

 
10. lemma. Az f függvényre a következők teljesülnek:
a) tetszőleges pozitív egész n-re f(n)>n;
b) az f függvény szigorúan monoton nő;
c) tetszőleges n pozitív egészre f(f(n))=f(n)+n.

 
Bizonyítás. Az a) tulajdonságot teljes indukcióval igazoljuk. Az n=1 esetben igaz, mert f(1)=2>1. Tegyük fel, hogy igaz n<m-re; ebből bebizonyítjuk n=m-re is. Ha m nem szerepel az f(1), ..., f(m-1) számok között, akkor f(m)=f(m-1)+1>(m-1)+1=m. Ha n szerepel az f(1), ..., f(m-1) számok között és k a legkisebb pozitív egész, amelyre n=f(k), akkor f(n)=n+k>n. Ezzel az a) állítást igazoltuk.
A b) állításhoz teljes indukcióval igazoljuk, hogy tetszőleges n pozitív egészre f(n+1)>f(n). Ez n=1-re igaz, mert f(1)=2 és f(2)=3. Tegyük fel, hogy
f(1)<f(2)<...<f(n);
ebből bebizonyítjuk, hogy f(n)<f(n+1).
Ha n+1 nem szerepel az f(1), ..., f(n) számok között, akkor
f(n+1)=f(n)+1>f(n).
Tegyük tehát fel, hogy n+1 szerepel az f(1),...,f(n) számok között, és legyen k a legkisebb pozitív egész, amelyre n+1=f(k); ekkor persze f(n+1)=n+k+1. Legyen ezután m=f(k-1); ekkor f(m)=m+k-1. Az indukciós feltevés szerint az f(1), ..., f(k-2) számok kisebbek f(k-1)-nél, ezért az m+1, ..., n számok egyike sem szerepel f(1), ..., f(k-1) között. Az f(k), ..., f(n-1) számok pedig az indukciós feltevés szerint nagyobbak n=f(k-1)-nél, ezért az f definíciója szerint
f(m+1)=f(m)+1=m+k,f(m+2)=f(m+1)+1=m+k+1,f(n)=f(n-1)+1=n+k-1.
Mivel f(n+1)=n+k+1, most is f(n)<f(n+1). Ezzel a b) állítást is igazoltuk.
Legyen most n tetszőleges pozitív egész. Az a) állítás szerint f(n)>n. A b) állítás szerint pedig az n-en kívül nincs még egy k szám, amelyre f(n)=f(k) teljesülne. Ezért az f függvény a definíció szerint f(n)-hez az f(n)+n számot rendeli: f(f(n))=f(n)+n. Ezzel a c) állítást is igazoltuk.
Ezután megkonstruálhatjuk az A. 244. feladatban megkívánt felbontást. Tekintsük az összes olyan n, f(n), f(f(n)), f(f(f(n))), ... sorozatot, amelyben n nem eleme f értékkészletének. A függvényegyenlet szerint ezek mind Fibonacci-típusú sorozatok:
12358132134...461016264268110...71118294776123199...91423376097157254...1219315081131212343...
Azt is könnyű végiggondolni, hogy minden pozitív egész pontosan egy sorozatban szerepel: ez a szigorúan monoton növekedő tulajdonságból következik.
 
 
III. megoldás az A. 244. feladatra*
 
 
* * Versenyzőink közül Horváth Illés, a Fazekas Mihály Főv. Gyak. Gimn. 11. osztályos tanulója oldotta meg így a feladatot.
Ebben a megoldásban az f helyett egy másik függvény segítségével adjuk meg a keresett felbontást.
Mint már láttuk, a Fibonacci-típusú sorozatok bizonyos értelemben hasonlítanak a q=1+52 hányadosú mértani sorozatokhoz. Ez adja a konstrukció alapötletét.
 
4. definíció. Legyen tetszőleges n pozitív egészre g(n) az az egész szám, amelyik a legközelebb van a qn számhoz, azaz |g(n)-qn|<12.
 
11. lemma. Tetszőleges n pozitív egészre g(g(n))=g(n)+n.
 
Bizonyítás. Legyen m=g(n) és k=g(g(n))=g(m). Azt kell igazolnunk, hogy k=m+n. A g definíciója szerint
|m-qn|<12és|k-qm|<12.
Felhasználva, hogy q(q-1)=q2-q=1,
|k-m-n|=|k-qm+(q-1)m-q(q-1)n|<<|k-qm|+(q-1)|m-qn|<12+(q-1)12=q2<1.

Mivel k, m és n egész számok, ez csak úgy lehet, ha k-m-n=0.
Innen a II. megoldás szerint haladhatunk az f függvény helyett a g függvénnyel.
 
 
IV. megoldás az A. 244. feladatra
 
 

Ez a megoldás Csikvári Péter és Zsbán Ambrus (mindketten a Fazekas M. Főv. Gyak. Gimn. 11. osztályos tanulói) dolgozatából származik.
 
12. lemma. Minden pozitív egész számot egyértelműen felírhatunk különböző Fibonacci-számok összegeként úgy, hogy nem használunk fel szomszédos Fibonacci-számokat, például 17=1+3+13, 49=2+13+34.
Ennek a lemmának a felhasználásával egy szép konstrukció adható a szükséges Fibonacci-típusú sorozatokra.
Tekintsünk egy olyan számot, amelynek a 12. lemma szerinti felírásában a tagok között szerepel az 1:
Fi1+Fi2+...+Fik,
ahol ij+1ij+2 és i1=2. (F1=F2=1 miatt nem engedjük meg a 0 és 1 indexeket.) Ha ebben az összegben az összes tagot a rákövetkező Fibonacci-számra cseréljük ki, akkor egy másik számot kapunk. Ezt a műveletet ismételve pedig egy sorozatot:
Fi1+...+Fik,Fi1+1+...+Fik+1,Fi1+2+...+Fik+2,...
Ez a sorozat a Fibonacci-sorozat k darab eltoltjának összege, tehát maga is Fibonacci-típusú.
Minden pozitív egész n pontosan egy ilyen sorozatban szerepel. Ha ugyanis n-et felírjuk a 12. lemmának megfelelően, akkor a tagokat a megfelelő kisebb Fibonacci-számokra cserélve egyértelműen meghatározható annak a sorozatnak az első eleme, amelyik az n-et tartalmazza.

Az így kapott Fibonacci-típusú sorozatok:
1, 2, 3, 5, 8, ...
4=1+3, 7=2+5, 11=3+8, 18=5+13, ...
6=1+5, 10=2+8, 16=3+13, 26=5+21, ...
9=1+8, 15=2+13, 24=3+21, 39=5+34, ...
12=1+3+8, 20=2+5+13, 32=3+8+21, 52=5+13+34, ...


 
8. feladat. Bizonyítsuk be a 12. lemmát!
 
 
 
További feladatok
 
 

 
9. feladat. Bizonyítsuk be, hogy az I. és a II. megoldás ugyanazt a felbontást állítja elő.
 
10. feladat. Mutassuk meg, hogy az I., a III. és a IV. megoldás három különböző konstrukciót ad a feladatra.
 
11. feladat. Két játékos a következő játékot játssza: Két kupac kavicsból felváltva vesznek el. Egy lépésben vagy az egyik kupacból vehetnek el legalább egy kavicsot, vagy pedig mindkét kupacból ugyanannyit. Az veszít, aki nem tud lépni. Mutassuk meg, hogy a második játékosnak pontosan akkor van nyerő stratégiája, ha a kiinduló állásban az egyik kupacban an-1, a másik kupacban bn-1 darab kavics van, ahol n alkalmas természetes szám, an és bn pedig a 2. definícióban szereplő sorozatok megfelelő elemei.
 
12. feladat. Legyen (an), illetve (bn) a 2. definícióban szereplő sorozat. Igazoljuk, hogy tetszőleges n nemnegatív egészre an=[qn]+1 és bn=[q2n]+1. ([x] az x egész része.)
 
13. feladat. Jelöljük h-val azt a függvényt, amely minden pozitív egészhez a IV. megoldásban látott felírása eltoltját rendeli; más szóval, ha az 1<i1<...<ik egész számok között nincsenek szomszédosak, akkor legyen h(Fi1+...+Fik)=Fi1+1+...+Fik+1. Bizonyítsuk be, hogy tetszőleges n pozitív egészre
qn-1q2<h(n)<qn+1q.

 
14. feladat. Azt mondjuk, hogy a (cn) sorozat a (dn) sorozat bővítése, ha létezik olyan k nemnegatív egész szám, amelyre cn+k=dn, azaz a (cn) sorozatot úgy kapjuk, hogy a (dn) sorozat elé további elemeket írunk. Bizonyítsuk be, hogy ha (cn) és (dn) pozitív számokból álló, monoton növő Fibonacci-típusú sorozatok és egyik sem a másik bővítése, akkor
a) legfeljebb két közös elemük van;
b) ha két közös elemük van, akkor az első elemeik megegyeznek.

 
15. feladat. Bizonyítsuk be a következő azonosságokat teljes indukcióval és a 2. lemma segítségével is.
Fn2-Fn-1Fn+1=(-1)n+1F2n-1=Fn2+Fn-12F3n-1=Fn3+3Fn2Fn-1+Fn-13


Énekes Béla, Kós Géza

*