Ugrás a tartalomhoz

Lineáris algebra

Freud Róbert (2014)

ELTE Eötvös Kiadó

9.2. Fibonacci-számok

9.2. Fibonacci-számok

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+1jj–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,…

9.2.1 Tétel

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 α01,… valós számsorozatokat, amelyek kielégítik az αj+1jj–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 1=1+5/2,  2=1-5/2.

Legyen Sm=1,m,m2,,  m=1,2 és keressük az F Fibonacci-sorozat előállítását F1S12S2 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=γ12, ϕ1=1=γ1ρ12ρ2 összefüggéseket jelenti. Ezt a lineáris egyenletrendszert megoldva γ1=1/5, γ2=-1/5 adódik. Innen n=γ11n+γ22n 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 F: R2R2 az Fab=ba+b lineáris transzformáció. Ekkor Fφj-1φj=φjφj-1+φj=φjφj+1 és így Fn01=φnφn+1

Tegyük fel, hogy b_1,b_2 olyan bázis R2-ben, ahol mindkét b_m sajátvektora F-nek. Legyenek a megfelelő sajátértékek λ1, λ2, ekkor Fnb_m=λmnb_m,  m=1,2 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 F mátrixát pl. az 10,01 bázisban: F=0111 Innen a karakterisztikus polinom kF=x2-x-1 a sajátértékek ennek a gyökei λ1,2=(1±5)/2 és a(z egyik) megfelelő sajátbázis b_1,2=1(1±5)/2 Ezt (i)-be beírva δ1=-δ2=1/5 adódik, és innen (ii) alapján kapjuk a tétel állítását.❷

Harmadik bizonyítás: Tekintsük az Fz=n=0φnzn 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–zz2)F(z)=z, azaz F(z)=z/(1–zz2).

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 μ1,2=(-1±5)/2 Ekkor alkalmas β1, β2-vel

(1)

alakban írható fel. A beszorzások elvégzése után az ezzel (z≠μ1, μ2-re) ekvivalens –z1β12z)+μ2β21z)feltételhez jutunk, azaz 0=μ1μ212) és μ1β12β2=1, ahonnan β1=-β2=1/5 Ezt az (1) jobb oldalára beírva és az (1–zm)–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 βmm, m=1,2.)❷

Feladatok

9.2.1 Számítsuk ki α1000-et, ha α12=1 és

a) αkk–1+2αk–2;

b) αk=2αk–1k–2.

9.2.2 Számítsuk ki α1111-et, ha α1=3, α2=7 és

a) αk=2αk–1–αk–2;

b) αkk–1–αk–2;

c) αkk–1–αk–2k–3–αk–4.

*9.2.3 Tekintsük az αk1α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 αn=j=1rgjnλjn 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 βkk–1k–2+2, β0=0, β1=1.

9.2.6 Mutassuk meg, hogy az n-edik Fibonacci-szám, ϕn éppen a τn=(1/5)1+5/2n 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,46nn<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+nm–1ϕnmϕn+1;

b) φ2n-1=φn-12+φn2

c) ϕ12+…+ϕnn+2–1;

d) ϕ1+2ϕ2+…+nϕn=(n+1)ϕn+2–ϕn+4+2;

e) φ12+φ22++φn2=φnφn+1

f) φn2=φn-1φn+1+(-1)n+1

g) φ3n=5φn3+3(-1)nφn

h) φn=j=0n-1/2n-j-1j

i) φ2n=j=1nnjφj

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 knφkφn 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?