Freud Róbert (2014)
ELTE Eötvös Kiadó
Ebben a pontban a Fibonacci-számok képletét határozzuk meg, amelyet már a 4.6.8 feladatban is kitűztünk. Emlékeztetünk arra, hogy a Fibonacci-számok sorozatát a ϕ0=0, ϕ1=1, ϕj+1=ϕj+ϕj–1, j=1,2,… rekurzióval definiáljuk. A sorozat első néhány tagja: 0,1,1,2,3,5,8,13,21,34,…
❶
Megjegyzés: Ha már valahonnan tudjuk, hogy mi a bizonyítandó formula, akkor ezt egyszerűen igazolhatjuk teljes indukcióval. Így azonban nem kapunk magyarázatot arra, hogyan lehet a képletre rájönni (nem valószínű, hogy akár az első ezer tag felírása után sikerül ezt „megsejtenünk”). Az alábbi bizonyításokból a képlethez vezető út is kiderül.
A bizonyítások közül kettő lineáris algebrai, a harmadik pedig az analízis területéről a hatványsorokat veszi igénybe (bár céljainknak az ún. formális hatványsorok algebrai elmélete is megfelelne). Hasonló módszerekkel kezelhetők általában is a rekurzív sorozatok, amelyek a matematika számos ágában fontos szerepet játszanak.
Első bizonyítás: Nevezzük a Fibonacci-sorozat általánosításaként Φ-sorozatnak az olyan α0,α1,… valós számsorozatokat, amelyek kielégítik az αj+1=αj+αj–1, j=1,2,… feltételt (és az α0, α1kezdőtagok tetszőleges valós számok). Egy Φ-sorozat (valós) számszorosa és két Φ-sorozat összege nyilván ismét Φ-sorozat (két sorozat összegét, illetve egy sorozat számszorosát a szokásos módon elemenként képezzük).
Most megpróbáljuk magát az F=(ϕ0, ϕ1,…) Fibonacci-sorozatot olyan Φ-sorozatokból előállítani, amelyek tagjaira ismerünk egyszerű képletet. Könnyen adódik, hogy a számtani sorozatok közül csak az azonosan nulla lesz Φ-sorozat, ami nem segít a probléma megoldásában. A mértani sorozatoknál azonban már több szerencsével járunk: az (α,αρ,αρ2,…) mértani sorozat (α≠0) pontosan akkor Φ-sorozat, ha ρ2=ρ+1, ahonnan
Legyen és keressük az F Fibonacci-sorozat előállítását F=γ1S1+γ2S2 alakban. Mivel mindkét oldalon Φ-sorozat áll, ezért az egyenlőség pontosan akkor teljesül, ha a két kezdőtagra igaz, mert utána a rekurzió miatt öröklődik. A két kezdőtagra felírva ez a ϕ0=0=γ1+γ2, ϕ1=1=γ1ρ1+γ2ρ2 összefüggéseket jelenti. Ezt a lineáris egyenletrendszert megoldva adódik. Innen ami (a ρm, γm konkrét értékek figyelembe vételével) éppen a tétel állítása.❷
Megjegyzés: Felmerül a kérdés, hol használtunk a megoldásban lineáris algebrát. A bizonyítás a fenti formájában természetesen középiskolai eszközökkel dolgozik, a lineáris algebra inkább a szemléletet, a hátteret adja. Itt tulajdonképpen arról van szó, hogy a Φ-sorozatok vektorterében keresünk alkalmas generátorrendszert, amelynek segítségével az F Fibonacci-sorozatot fel tudjuk írni. Ez a vektortér 2-dimenziós, hiszen a két kezdőtag választható szabadon, azaz a szabadsági fokok száma kettő. (Precízen: „természetes” bázis az 1,0-val és a 0,1-gyel kezdődő két Φ-sorozat; (1,0,1,1,2,3,5,…) és (0,1,1,2,3,5,8,…), ami mellesleg a Fibonacci-sorozat egy eltoltja és maga a Fibonacci-sorozat.) Ebben a 2-dimenziós vektortérben keresünk „szebb alakú” generátorrendszert. A mértani sorozatok közül a fent talált S1 és S2 megfelel, hiszen két lineárisan független elem biztosan bázist alkot.
Mindezek alapján nem kell kivételes szerencsének éreznünk, hogy az előállítás sikerült. A mértani sorozatok hányadosait ugyanis egy másodfokú egyenlet gyökeiként kaptuk és csak akkor lettünk volna gondban, ha az egyenletnek többszörös gyöke van. Azonban ez az eset (még a több tagból álló rekurziónál) is kezelhető, lásd a 9.2.3 feladatot.
Második bizonyítás: Legyen az lineáris transzformáció. Ekkor és így
Tegyük fel, hogy olyan bázis R2-ben, ahol mindkét sajátvektora -nek. Legyenek a megfelelő sajátértékek λ1, λ2, ekkor Ha
(i)
akkor
(ii)
és innen az első koordinátaként megkapjuk ϕn-et.
A sajátértékek meghatározásához írjuk fel mátrixát pl. az bázisban: Innen a karakterisztikus polinom a sajátértékek ennek a gyökei és a(z egyik) megfelelő sajátbázis Ezt (i)-be beírva adódik, és innen (ii) alapján kapjuk a tétel állítását.❷
Harmadik bizonyítás: Tekintsük az hatványsort. Mivel a Fibonacci-számok definíciójából teljes indukcióval könnyen adódik ϕn<2n, emiatt az F(z) hatványsor |z|<1/2-re abszolút konvergens. Ez azért hasznos, mert abszolút konvergens végtelen sorokkal „ugyanúgy számolhatunk”, mint ahogyan a véges összegek körében megszoktuk.
Írjuk le egymás alá az F(z), zF(z) és z2F(z)hatványsorokat:
Az első sorból kivonva a másik kettő összegét, a jobb oldalon majdnem minden tag kiesik, és azt kapjuk, hogy (1–z–z2)F(z)=z, azaz F(z)=z/(1–z–z2).
Az F(z)-re kapott racionális törtfüggvényt parciális törtekre bontjuk és hatványsorba fejtjük. Legyenek a z2+z–1 polinom gyökei μ1 és Ekkor alkalmas β1, β2-vel
(1)
alakban írható fel. A beszorzások elvégzése után az ezzel (z≠μ1, μ2-re) ekvivalens –z=μ1β1(μ2–z)+μ2β2(μ1–z)feltételhez jutunk, azaz 0=μ1μ2(β1+β2) és μ1β1+μ2β2=1, ahonnan Ezt az (1) jobb oldalára beírva és az (1–z/μm)–1 függvényeket végtelen mértani sorba fejtve kapjuk, hogy
Itt zn együtthatójára — ami nem más mint ϕn — a tételben megadott értéket nyerjük. (A második bizonyítással összevetve könnyen adódik, hogy μm=1/λm és βm=δm, m=1,2.)❷
Feladatok
9.2.1 Számítsuk ki α1000-et, ha α1=α2=1 és
a) αk=αk–1+2αk–2;
b) αk=2αk–1+αk–2.
9.2.2 Számítsuk ki α1111-et, ha α1=3, α2=7 és
a) αk=2αk–1–αk–2;
b) αk=αk–1–αk–2;
c) αk=αk–1–αk–2+αk–3–αk–4.
*9.2.3 Tekintsük az αk=μ1αk–1+…+μtαk–t feltételnek eleget tevő α0, α1,… komplex számsorozatokat, ahol t rögzített pozitív egész és μ1,…, μt rögzített komplex számok, μt≠0. Legyenek az f=xt–μ1xt–1–…–μt polinom különböző (komplex) gyökei λ1,…, λr, a multiplicitásuk rendre s1,…, sr. Mutassuk meg, hogy ekkor ahol gj egy legfeljebb sj–1-edfokú polinom, j=1,2,…,r, és gj együtthatói csak az α0,…, αt–1 kezdőértékektől függnek.
9.2.4 Használjuk az előző feladat jelöléseit. Mutassuk meg, hogy az α0, α1,… komplex számsorozat akkor és csak akkor lesz periodikus bármilyen α0,…, αt–1 kezdőértékek mellett, ha f-nek nincs többszörös gyöke és minden gyöke egységgyök.
9.2.5 Határozzuk meg βn-et, ha βk=βk–1+βk–2+2, β0=0, β1=1.
9.2.6 Mutassuk meg, hogy az n-edik Fibonacci-szám, ϕn éppen a számhoz legközelebbi egész. Lássuk be azt is, hogy ϕn és τn eltérése 0-hoz tart, ha n→∞ (azaz ϕn „majdnem” mértani sorozat).
9.2.7
a) Hányféleképpen lehet egy 2×n-es téglalapot 2×1-es dominókkal kirakni?
*b) Hányféleképpen lehet egy 3×n-es téglalapot 2×1-es dominókkal kirakni?
*c) Jelöljük ψn-nel, ahányféleképpen egy 3×n-es téglalapot 3×1-es dominókkal ki lehet rakni. Bizonyítsuk be, hogy minden elég nagy n-re 1,46n<ψn<1,47n.
9.2.8 Hány olyan részhalmaza van az {1,2,…,n} számoknak, amelyben nem fordulnak elő szomszédos elemek?
9.2.9 Mutassuk meg, hogy minden pozitív egész felírható különböző Fibonacci-számok összegeként.
9.2.10 Igazoljuk a Fibonacci-számokra vonatkozó alábbi azonosságokat:
a) ϕm+n=ϕm–1ϕn+ϕmϕn+1;
b)
c) ϕ1+ϕ2+…+ϕn=ϕn+2–1;
d) ϕ1+2ϕ2+…+nϕn=(n+1)ϕn+2–ϕn+4+2;
e)
f)
g)
h)
i)
9.2.11 Bizonyítsuk be, hogy a szomszédos Fibonacci-számok relatív prímek. Mi a helyzet a másodszomszédokkal? És a harmadszomszédokkal?
9.2.12 Lássuk be, hogy minden m-re van végtelen sok m-mel osztható Fibonacci-szám.
*9.2.13 Igazoljuk, hogy sőt ϕ(k,n)=(ϕk, ϕn).
9.2.14
a) Legyenek a>b olyan pozitív egészek, amelyekre az euklideszi algoritmus pontosan n lépésből áll, és ezen belül b a lehető legkisebb. Határozzuk meg b-t.
*b) Oldjuk meg a feladatot arra az esetre is, amikor az euklideszi algoritmust (a legkisebb nemnegatív maradékok helyett) a legkisebb abszolút értékű maradékokkal végezzük.
*9.2.15 Számítsuk ki a kettőhatvány indexű Fibonacci-számok reciprokaiból képezett végtelen sor összegét.
M**9.2.16 A többtényezős szorzatokat az asszociativitás miatt nem kell zárójelezni. Tekintsünk most egy nemasszociatív műveletet. Hányféle értékű lehet (azaz hányféleképpen zárójelezhető) ekkor egy n-tényezős szorzat?
**9.2.17 Hányféleképpen lehet egy konvex n-szöget a sokszög belsejében egymást nem metsző átlókkal háromszögekre bontani?