❶

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 α₀,α₁,… valós számsorozatokat, amelyek kielégítik az α_j+1=α_j+α_j–1, j=1,2,… feltételt (és az α₀, α₁kezdő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=(ϕ₀, ϕ₁,…) 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 (α,αρ,αρ²,…) mértani sorozat (α≠0) pontosan akkor Φ-sorozat, ha ρ²=ρ+1, ahonnan ${}_1=\left(1+\sqrt{5}\right)/2, {}_2=\left(1-\sqrt{5}\right)/2.$

Legyen $S_m=\left(1,{}_m,{}_m^2,\dots \right), m=\mathrm{1,2}$ és keressük az F Fibonacci-sorozat előállítását F=γ₁S₁+γ₂S₂ 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=γ₁+γ₂, ϕ₁=1=γ₁ρ₁+γ₂ρ₂ összefüggéseket jelenti. Ezt a lineáris egyenletrendszert megoldva ${\gamma }_1=1/\sqrt{5}, {\gamma }_2=-1/\sqrt{5}$ adódik. Innen ${}_n={\gamma }_1{}_1^n+{\gamma }_2{}_2^n$ 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 S₁ és S₂ 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 $\mathcal{F}:\mathcal{ }{\mathbf{R}}^2\to {\mathbf{R}}^2$ az $\mathcal{F}\left(\begin{array}{c}a\\ b\end{array}\right)=\left(\begin{array}{c}b\\ a+b\end{array}\right)$ lineáris transzformáció. Ekkor $\mathcal{F}\left(\begin{array}{c}{\phi }_{j-1}\\ {\phi }_j\end{array}\right)=\left(\begin{array}{c}{\phi }_j\\ {\phi }_{j-1}+{\phi }_j\end{array}\right)=\left(\begin{array}{c}{\phi }_j\\ {\phi }_{j+1}\end{array}\right)$ és így ${\mathcal{F}}^n\left(\begin{array}{c}0\\ 1\end{array}\right)=\left(\begin{array}{c}{\phi }_n\\ {\phi }_{n+1}\end{array}\right)$

Tegyük fel, hogy ${\underset{\_}{b}}_1,{\underset{\_}{b}}_2$ olyan bázis R²-ben, ahol mindkét ${\underset{\_}{b}}_m$ sajátvektora $\mathcal{F}$-nek. Legyenek a megfelelő sajátértékek λ₁, λ₂, ekkor ${\mathcal{F}}^n{\underset{\_}{b}}_m={\lambda }_m^n{\underset{\_}{b}}_m, m=\mathrm{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 $\mathcal{F}$ mátrixát pl. az $\left(\begin{array}{c}1\\ 0\end{array}\right),\left(\begin{array}{c}0\\ 1\end{array}\right)$ bázisban: $\left[\mathcal{F}\right]=\left(\begin{array}{cc}0& 1\\ 1& 1\end{array}\right)$ Innen a karakterisztikus polinom $k_{\mathcal{F}}=x^2-x-1$ a sajátértékek ennek a gyökei ${\lambda }_{\mathrm{1,2}}=(1\pm \sqrt{5})/2$ és a(z egyik) megfelelő sajátbázis ${\underset{\_}{b}}_{\mathrm{1,2}}=\left(\begin{array}{c}1\\ (1\pm \sqrt{5})/2\end{array}\right)$ Ezt (i)-be beírva ${\delta }_1=-{\delta }_2=1/\sqrt{5}$ adódik, és innen (ii) alapján kapjuk a tétel állítását.❷

Harmadik bizonyítás: Tekintsük az $F\left(z\right)={}_{n=0}^{}{\phi }_n{z}^n$ hatványsort. Mivel a Fibonacci-számok definíciójából teljes indukcióval könnyen adódik ϕ_n<2ⁿ, 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 z²F(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–z²)F(z)=z, azaz F(z)=z/(1–z–z²).

Az F(z)-re kapott racionális törtfüggvényt parciális törtekre bontjuk és hatványsorba fejtjük. Legyenek a z²+z–1 polinom gyökei μ₁ és ${\mu }_{\mathrm{1,2}}=(-1\pm \sqrt{5})/2$ Ekkor alkalmas β₁, β₂-vel

(1)

alakban írható fel. A beszorzások elvégzése után az ezzel (z≠μ₁, μ₂-re) ekvivalens –z=μ₁β₁(μ₂–z)+μ₂β₂(μ₁–z)feltételhez jutunk, azaz 0=μ₁μ₂(β₁+β₂) és μ₁β₁+μ₂β₂=1, ahonnan ${\beta }_1=-{\beta }_2=1/\sqrt{5}$ 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 zⁿ 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 α₁₀₀₀-et, ha α₁=α₂=1 és

a) α_k=α_k–1+2α_k–2;

b) α_k=2α_k–1+α_k–2.

9.2.2 Számítsuk ki α₁₁₁₁-et, ha α₁=3, α₂=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=μ₁α_k–1+…+μ_tα_k–t feltételnek eleget tevő α₀, α₁,… komplex számsorozatokat, ahol t rögzített pozitív egész és μ₁,…, μ_t rögzített komplex számok, μ_t≠0. Legyenek az f=x^t–μ₁x^t–1–…–μ_t polinom különböző (komplex) gyökei λ₁,…, λ_r, a multiplicitásuk rendre s₁,…, s_r. Mutassuk meg, hogy ekkor ${\alpha }_n={}_{j=1}^r{g}_j\left(n\right){\lambda }_j^n$ ahol g_j egy legfeljebb s_j–1-edfokú polinom, j=1,2,…,r, és g_j együtthatói csak az α₀,…, α_t–1 kezdőértékektől függnek.

9.2.4 Használjuk az előző feladat jelöléseit. Mutassuk meg, hogy az α₀, α₁,… komplex számsorozat akkor és csak akkor lesz periodikus bármilyen α₀,…, α_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, β₁=1.

9.2.6 Mutassuk meg, hogy az n-edik Fibonacci-szám, ϕ_n éppen a ${\tau }_n=({1/\sqrt{5})\left(\left(1+\sqrt{5}\right)/2\right)}^n$ 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,46ⁿ<ψ_n<1,47ⁿ.

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) ${\phi }_{2n-1}={\phi }_{n-1}^2+{\phi }_n^2$

c) ϕ₁+ϕ₂+…+ϕ_n=ϕ_n+2–1;

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

e) ${\phi }_1^2+{\phi }_2^2+\dots +{\phi }_n^2={\phi }_n{\phi }_{n+1}$

f) ${\phi }_n^2={\phi }_{n-1}{\phi }_{n+1}+(-1{)}^{n+1}$

g) ${\phi }_{3n}=5{\phi }_n^3+3(-1{)}^n{\phi }_n$

h) ${\phi }_n={}_{j=0}^{⌊\left(n-1\right)/2⌋}\left(\begin{array}{c}n-j-1\\ j\end{array}\right)$

i) ${\phi }_{2n}={}_{j=1}^n\left(\begin{array}{c}n\\ j\end{array}\right){\phi }_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 $k\left|n\iff {\phi }_k\right|{\phi }_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?