Cím:	Néhány érdekesség a Fibonacci- és a Fibonacci-típusú sorozatokról
Szerző(k):	Énekes Béla ,  Kós Géza
Füzet:	2000/december, 517 - 523. oldal	PDF  |  MathML
Témakör(ök):	Szakmai cikkek
Hivatkozás(ok):	Feladatok: 2000/szeptember: A.244

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. I. rész   A KöMaL 2000. szeptemberi számában tűztük ki a következő feladatot:     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.   A cikk első részében közelebbről meg fogjuk vizsgálni a ,,Fibonacci-típusú'' sorozatokat. Eközben a Fibonacci-sorozat néhány érdekes tulajdonságára is fény derül. A második részben, amely a KöMaL következő számában fog megjelenni, több különböző megoldást mutatunk a feladatra. Terjedelmi okokból nem bizonyítunk precízen minden egyes állítást; lesznek olyanok, amelyek igazolását feladat formájában az Olvasóra hagyjuk. Ez azonban nem fog meggátolni minket abban, hogy a feladatként kimondott állításokat is felhasználjuk más állítások igazolásához.     A Fibonacci-sorozat     A természetes számokból álló sorozatok között az egyik legismertebb és legérdekesebb a Fibonacci sorozat. A sorozat elemei, a Fibonacci számok a legváltozatosabb és legmeglepőbb helyeken fordulnak elő, bukkannak fel nem csak a matematikában, de a természetben is. Bár a Fibonacci-sorozatot szinte minden középiskolás ismeri, nem árt újra felírni a definícióját. Különösen azért, hogy a továbbiakban az elemeket egységesen jelöljük és számozzuk. A sorozatot a következő rekurzióval definiáljuk: $\begin{array}{c}{\displaystyle F_0=0;F_1=1;F_{n+1}=F_n+F_{n-1}\left(n\ge 2\right)\mathrm{.}}\end{array}$ (1) A rekurzióból könnyen kiszámolhatjuk az első néhány Fibonacci-számot: $F_2=1$, $F_3=2$, $F_4=3$, $F_5=5$, $F_6=8$, $F_7=13$, $F_8=21$, $F_9=34$, $F_{10}=\mathrm{55,}$ $\text{...}$     Fibonacci-típusú sorozatok     Egyelőre egyetlen Fibonacci-típusú sorozatot láttunk: magát a Fibonacci-sorozatot. Először tehát nézzük meg, hogyan készíthetünk további ilyen sorozatokat. Egy lehetséges módszer, hogy a már ismert Fibonacci-típusú sorozatokból próbálunk újabbakat készíteni.   1. lemma. Fibonacci-típusú sorozatot kapunk minden esetben, ha * a) Egy Fibonacci-típusú sorozatnak elhagyjuk az első néhány elemét, vagy pedig olyan elemeket írunk elé, hogy a képzési szabály érvényes maradjon; * b)Egy Fibonacci-típusú sorozat összes elemét megszorozzuk ugyanazzal a számmal; * c)Néhány Fibonacci-típusú sorozat megfelelő elemeit összeadjuk.     1. feladat. Bizonyítsuk be az $1$. lemmát.   Egy másik lehetőség, hogy az (1) rekurzióban más számokat választunk a sorozat első két elemének. A leghíresebb ilyen sorozat az úgynevezett Lucas-sorozat: $\begin{array}{c}{\displaystyle L_0=\mathrm{2,}{L}_1=\mathrm{1,}{L}_2=\mathrm{3,}{L}_{n+1}=L_n+L_{n-1}\mathrm{,}}\end{array}$ de az első két elem helyére nyilván tetszőleges valós számokat írhatunk.   1. definíció. Tetszőleges $a$, $b$ valós számokra ,,az $\left(a\mathrm{,}b\right)$ paraméterű Fibonacci-típusú sorozatnak'' nevezzük azt a számsorozatot, amelyet a következő rekurzív képzési szabály definiál: $\begin{array}{c}{\displaystyle F_0^{\left(a\mathrm{,}b\right)}=a;F_1^{\left(a\mathrm{,}b\right)}=b;F_{n+1}^{\left(a\mathrm{,}b\right)}=F_n^{\left(a\mathrm{,}b\right)}+F_{n-1}^{\left(a\mathrm{,}b\right)}\left(n\ge 1\right)\mathrm{.}}\end{array}$   Ezzel a jelöléssel Fibonacci eredeti sorozata $F_n^{\left(\mathrm{0,}1\right)}$, a Lucas-sorozat pedig $F_n^{\left(\mathrm{2,}1\right)}$. Világos, hogy az 1. definícióban felírt sorozatok az összes Fibonacci-típusú sorozatot tartalmazzák, hiszen az első két elem egyértelműen meghatározza a többit. Ennek egy másik fontos következménye, hogy ha két Fibonacci-típusú sorozatról be akarjuk bizonyítani, hogy ugyanazok, akkor elég az első két elemről ellenőrizni, hogy megegyeznek. Ha elkezdjük formálisan felírni az $\left(F_n^{\left(a\mathrm{,}b\right)}\right)$ sorozat elemeit, érdekes dolgot vehetünk észre: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle F_2^{\left(a\mathrm{,}b\right)}}& {\displaystyle =F_1^{\left(a\mathrm{,}b\right)}+F_0^{\left(a\mathrm{,}b\right)}=1a+1b}\hfill \\ \hfill {\displaystyle F_3^{\left(a\mathrm{,}b\right)}}& {\displaystyle =F_2^{\left(a\mathrm{,}b\right)}+F_1^{\left(a\mathrm{,}b\right)}=1a+2b}\hfill \\ \hfill {\displaystyle F_4^{\left(a\mathrm{,}b\right)}}& {\displaystyle =F_3^{\left(a\mathrm{,}b\right)}+F_2^{\left(a\mathrm{,}b\right)}=2a+3b}\hfill \\ \hfill {\displaystyle F_5^{\left(a\mathrm{,}b\right)}}& {\displaystyle =F_4^{\left(a\mathrm{,}b\right)}+F_3^{\left(a\mathrm{,}b\right)}=3a+5b}\hfill \\ \hfill {\displaystyle F_6^{\left(a\mathrm{,}b\right)}}& {\displaystyle =F_5^{\left(a\mathrm{,}b\right)}+F_4^{\left(a\mathrm{,}b\right)}=5a+8b}\hfill \end{array}}}\end{array}$ Ezekből már megsejthetjük a következő tételt:   1. tétel. a) A Fibonacci-sorozatból kiindulva, az 1. lemmában felsorolt lépésekkel bármelyik Fibonacci-típusú sorozatot előállíthatjuk. b) Tetszőleges $a$, $b$ valós számokra az $\left(a\mathrm{,}b\right)$ paraméterű Fibonacci-típusú sorozat elemei felírhatók a következő alakban: $\begin{array}{c}{\displaystyle F_n^{\left(a\mathrm{,}b\right)}=F_{n-1}\cdot a+F_n\cdot b\left(n\ge 1\right)\mathrm{.}}\end{array}$ (2)   Bizonyítás. Legyenek $a$ és $b$ tetszőleges valós számok. Ha a Fibonacci-sorozat elejére odaírjuk az $1$-et, akkor az 1, 0, 1, 1, 2, 3, 5, 8, $\text{...}$ Fibonacci-típusú sorozatot kapjuk. Ha ennek $a$-szorosához hozzáadjuk a Fibonacci-sorozat $b$-szeresét, akkor a kapott sorozat az $a\cdot F_{n-1}+b\cdot F_n$ sorozat lesz. Ennek 0. eleme $a\cdot 1+b\cdot 0=a$, 1. eleme $a\cdot 0+b\cdot 1=b$, vagyis a sorozat nem más, mint az $\left(a\mathrm{,}b\right)$ paraméterű Fibonacci-típusú sorozat. Az $\left(F_n^{\left(a\mathrm{,}b\right)}\right)$ sorozatot tehát elő tudtuk állítani az 1. lemmában leírt lépésekkel, az előállítást formálisan a (2) képlet írja le.     Fibonacci-típusú mértani sorozatok     A Fibonacci-sorozat nem mértani sorozat. Ha kiszámítjuk a szomszédos Fibonacci-számok hányadosát, láthatjuk, hogy a hányadosok különbözők: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle \frac{1}{1}=1;\frac{2}{1}=2;\frac{3}{2}=\mathrm{1,5};\frac{5}{3}\approx \mathrm{1,667};\frac{8}{5}=\mathrm{1,6};}\\ \hfill {\displaystyle \frac{13}{8}=\mathrm{1,625};\frac{21}{13}\approx \mathrm{1,615};\frac{34}{21}\approx \mathrm{1,6190};\frac{55}{34}\approx \mathrm{1,6176};\text{...}}\end{array}}}\end{array}$ Azt is láthatjuk azonban, hogy a hányadosok egyre közelebb vannak egy számhoz, amelynek tizedestört alakja $\mathrm{1,618}$-del kezdődik. Ugyanezt az eredményt kapjuk sok más Fibonacci-típusú sorozat esetében. Például a Lucas-sorozatra $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle \frac{3}{1}=3;\frac{4}{3}\approx \mathrm{1,333};\frac{7}{4}=\mathrm{1,75};\frac{11}{7}\approx \mathrm{1,571};\frac{18}{11}\approx \mathrm{1,636};}\\ \hfill {\displaystyle \frac{29}{18}\approx \mathrm{1,611};\frac{47}{29}\approx \mathrm{1,621};\frac{76}{47}\approx \mathrm{1,617};\frac{123}{76}\approx \mathrm{1,6184};\text{...}}\end{array}}}\end{array}$ A Fibonacci-típusú sorozatok tehát bizonyos értelemben hasonlítanak egy olyan mértani sorozatra, amelynek hányadosa ez a titokzatos $q=\mathrm{1,618}\text{...}$ szám. A $q$ szám pontos kiszámításához keressünk olyan mértani sorozatot, amelyik Fibonacci-típusú is. Legyen a sorozat első eleme $a_1$, hányadosa $q$. Ekkor tetszőleges $n$-re $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle a_{n+2}=a_{n+1}+a_n\mathrm{,}}\\ \hfill {\displaystyle a_1{q}^{n+1}=a_1{q}^n+a_1{q}^{n-1}\mathrm{,}}\end{array}}}\end{array}$ azaz $\begin{array}{c}{\displaystyle q^2=q+1.}\end{array}$ (3) Ennek az egyenletnek két irracionális valós gyöke van: $q_1=\frac{1+\sqrt[]{5}}{2}\approx \mathrm{1,618034}$ és $q_2=\frac{1-\sqrt[]{5}}{2}\approx -\mathrm{0,618034}$. Tehát a keresett szám: $q=\frac{1+\sqrt[]{5}}{2}$. Érdekesség, hogy egy másik Fibonacci-típusú mértani sorozatot is találtunk; ennek hányadosa a negatív $\frac{1-\sqrt[]{5}}{2}$. A $q_2$ hányadosú sorozatban egyre kisebb abszolút értékű számok szerepelnek, váltakozó előjellel. Ezzel bebizonyítottuk a következő tételt:   2. tétel. Kétféle Fibonacci-típusú mértani sorozat létezik; ezeknek a hányadosa $q=\frac{1+\sqrt[]{5}}{2}$, illetve $q_2=\frac{1-\sqrt[]{5}}{2}$.   Azt még nem tisztáztuk, hogy a Fibonacci-sorozat milyen értelemben hasonlít erre a $q$ hányadosú mértani sorozatra; erre később, a 3. tételben térünk majd vissza.     A Fibonacci-sorozat és a $q=\frac{1+\sqrt[]{5}}{2}$ szám hatványai     Játsszunk most el egy kicsit a $q$ számmal úgy, hogy csak a $q^2=q+1$ azonosságot használjuk fel. A $q$ magasabb hatványait felírhatjuk $aq+b$ alakban: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle q^3}& {\displaystyle =q^2\cdot q=\left(q+1\right)q=q^2+q=\left(q+1\right)+q=2q+1;}\hfill \\ \hfill {\displaystyle q^4}& {\displaystyle =q^3\cdot q=\left(2q+1\right)q=2q^2+q=2\left(q+1\right)+q=3q+2;}\hfill \\ \hfill {\displaystyle q^5}& {\displaystyle =q^4\cdot q=\left(3q+2\right)q=3q^2+2q=3\left(q+1\right)+2q=5q+3;}\hfill \\ \hfill {\displaystyle q^6}& {\displaystyle =q^5\cdot q=\left(5q+3\right)q=5q^2+3q=5\left(q+1\right)+3q=8q+5;}\hfill \end{array}}}\end{array}$   2. lemma. Tetszőleges $n$ pozitív egészre $\begin{array}{c}{\displaystyle q^n=F_{n}q+F_{n-1}\mathrm{.}}\end{array}$ (4)   1. bizonyítás. Mivel (4) mindkét oldalán Fibonacci-típusú sorozat áll, ezért elég az első két elemre ellenőrizni. $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle n}& {\displaystyle =1:q=F_{1}q+F_0=q\mathrm{,}}\hfill \\ \hfill {\displaystyle n}& {\displaystyle =2:q^2=F_{2}q+F_1=q+1.}\hfill \end{array}}}\end{array}$   2. bizonyítás. Az $1$, $q$, $q^2$, $\text{...}$ sorozat nem más, mint az $\left(\mathrm{1,}q\right)$ paraméterű Fibonacci-típusú sorozat, ezért a 1. tétel szerint $n\ge 1$ esetén $\begin{array}{c}{\displaystyle q^n=F_n^{\left(\mathrm{1,}q\right)}=F_{n-1}\cdot 1+F_n\cdot q\mathrm{.}}\end{array}$   2. feladat. Bizonyítsuk be a $2$. lemmát teljes indukcióval is.   Most már bebizonyíthatjuk, hogy a szomszédos Fibonacci-számok hányadosa $q$-hoz tart, sőt ennél kicsit többet.   3. feladat. Bizonyítsuk be teljes indukcióval, hogy $n\ge 1$ esetén $\begin{array}{c}{\displaystyle \frac{1}{3}{q}^n<F_n<\frac{1}{2}{q}^n\mathrm{.}}\end{array}$   3. tétel. Tetszőleges $n$ pozitív egészre $\begin{array}{c}{\displaystyle \left|\frac{F_{n+1}}{F_n}-q\right|<\frac{1}{2F_n^2}\mathrm{.}}\end{array}$   Bizonyítás. A 2. lemma akkor is igaz marad, ha a $q$ helyére a $q_2$ számot írjuk, tehát $\begin{array}{c}{\displaystyle F_{n+1}{q}_2+F_n=q_2^{n+1}\mathrm{.}}\end{array}$ (5) Akár a ViŠte-képletekből, akár közvetlenül könnyen ellenőrizhető, hogy $q_2=\frac{-1}{q}$. Ezt beírva (5)-be és rendezve, $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{c}\hfill {\displaystyle -\frac{F_{n+1}}{q}+F_n=\frac{{\left(-1\right)}^{n+1}}{q^{n+1}}\mathrm{,}}\\ \hfill {\displaystyle \left|\frac{F_{n+1}}{F_n}-q\right|=\left|\frac{{\left(-1\right)}^n}{q^n{F}_n}\right|=\frac{1}{q^n\cdot F_n}<\frac{1}{2F_n^2}\mathrm{.}}\end{array}}}\end{array}$ (Az utolsó lépésben a 3. feladat felső becslését használtuk fel.)   A 3. tétel nem csak annyit mond, hogy az $\frac{F_{n+1}}{F_n}$ értéke ,,körülbelül'' $q$; azt is állítja, hogy ez a becslés nagyon pontos: a hiba $\frac{1}{2F_n^2}$-nél kisebb.${}^{*}$       Hogyan készítsünk végtelen sok azonosságot a Fibonacci-számokkal?     A 2. lemma állítását felhasználhatjuk arra, hogy olyan azonosságokat gyártsunk, amelyekben a Fibonacci-számok szerepelnek. Ehhez először is szükség van a következő lemmára:   3. lemma. Ha egy valós számot fel lehet írni $aq+b$ alakban alkalmas $a$, $b$ egész számokkal, akkor ez a felírás egyértelmű. Más szóval, ha valamely $a$, $b$, $c$, $d$ egész számokra $aq+b=cq+d$, akkor $a=c$ és $b=d$.   Bizonyítás. Az egyenletet átrendezve $\left(a-c\right)q=d-b$. Mivel $q$ irracionális, ez csak úgy lehetséges, ha $d-b=0$ és $a-c=0$.   Írjunk most fel egy tetszőleges azonosságot $q$ hatványaival, például azt, hogy $q^{n+k}=q^n\cdot q^k$, és helyettesítsük be a 2. lemmában látott kifejezéseket a hatványok helyére: $\begin{array}{c}{\displaystyle {\displaystyle \begin{array}{cc}\hfill {\displaystyle q^{n+k}}& {\displaystyle =q^n\cdot q^k\mathrm{,}}\hfill \\ \hfill {\displaystyle F_{n+k}\cdot q+F_{n+k-1}}& {\displaystyle =\left(F_n\cdot q+F_{n-1}\right)\cdot \left(F_k\cdot q-F_{k-1}\right)\mathrm{,}}\hfill \\ \hfill {\displaystyle F_{n+k}\cdot q+F_{n+k-1}}& {\displaystyle =F_n{F}_k\cdot q^2+\left(F_n{F}_{k-1}+F_{n-1}{F}_k\right)q+F_{n-1}{F}_{k-1}\mathrm{,}}\hfill \\ \hfill {\displaystyle F_{n+k}\cdot q+F_{n+k-1}}& {\displaystyle =F_n{F}_k\cdot \left(q+1\right)+\left(F_n{F}_{k-1}+F_{n-1}{F}_k\right)q+F_{n-1}{F}_{k-1}\mathrm{,}}\hfill \\ \hfill {\displaystyle F_{n+k}\cdot q+F_{n+k-1}}& {\displaystyle =\left(F_n{F}_k+F_n{F}_{k-1}+F_{n-1}{F}_k\right)q+\left(F_n{F}_k+F_{n-1}{F}_{k-1}\right)\mathrm{,}}\hfill \end{array}}}\end{array}$ amiből az egyértelműség miatt például $\begin{array}{c}{\displaystyle F_{n+k-1}=F_n{F}_k+F_{n-1}{F}_{k-1}\mathrm{.}}\end{array}$ (6)   4. feladat. Bizonyítsuk be teljes indukcióval a $\left(6\right)$ azonosságot.     A Fibonacci-típusú sorozatok explicit alakja     Most a Fibonacci-típusú sorozatokat egy explicit, rekurzió nélküli formában fogjuk felírni. Ehhez az 1. lemma lépéseit fogjuk alkalmazni, de nem a Fibonacci-sorozatra, hanem az $1$, $q$, $q^2$, $\text{...}$ és a $1$, $q_2$, $q_2^2$, $\text{...}$sorozatokra.   4. lemma. Tetszőleges $a$, $b$ valós számokhoz léteznek olyan $c$, $d$ valós számok, amelyekre $a=c+d$ és $b=cq+d{q}_2$.   Bizonyítás. A $c$ és $d$ kiszámításához csupán meg kell oldanunk a lineáris egyenletrendszert. Mint könnyen ellenőrizhető, $\begin{array}{c}{\displaystyle c=\frac{b-q_{2}a}{q-q_2}\text{és}d=\frac{qa-b}{q-q_2}\mathrm{.}}\end{array}$ (7)   4. tétel. Tetszőleges $a$, $b$ valós számokra az $\left(a\mathrm{,}b\right)$ paraméterű Fibonacci-típusú sorozat $n$-edik eleme felírható a következő alakban: $\begin{array}{c}{\displaystyle F_n^{\left(a\mathrm{,}b\right)}=c{q}^n+d{q}_2^n\mathrm{,}}\end{array}$ (8) ahol $c=\frac{b-q_{2}a}{q-q_2}$ és $d=\frac{qa-b}{q-q_2}$.   Bizonyítás. A (8) mindkét oldalán Fibonacci-típusú sorozat áll. Az egyenlőség az $n=0$ és $n=1$ esetekben a 4. lemma szerint teljesül.   A Fibonacci-sorozat paraméterei $\left(\mathrm{0,}1\right)$. Egy kis számolással kapjuk, hogy ezekre a számokra $c=\frac{1}{\sqrt[]{5}}$ és $d=\frac{-1}{\sqrt[]{5}}$. Ezzel máris bebizonyítottuk a Fibonacci-sorozat explicit felírását:   5. tétel. Tetszőleges $n$ nem-negatív egész számra $\begin{array}{c}{\displaystyle F_n=\frac{q^n-q_2^n}{\sqrt[]{5}}=\frac{{\left(\frac{1+\sqrt[]{5}}{2}\right)}^n-{\left(\frac{1-\sqrt[]{5}}{2}\right)}^n}{\sqrt[]{5}}\mathrm{.}}\end{array}$   5. feladat. Írjuk fel explicit alakban az $n$-edik Lucas-számot.   6. feladat. Az 1. tétel szerint, ha a Fibonacci-sorozatból indulunk ki, akkor az 1. lemma lépéseivel az összes Fibonacci-típusú sorozatot előállíthatjuk, nincs szükség több sorozatra. A 4. tételben miért nem volt elég csak az egyik sorozat? Magyarázzuk meg!   A Fibonacci-számok és Fibonacci-típusú sorozatok explicit felírásának ismeretében nagyon sok azonosság bizonyítása egyszerűvé válik: csupán be kell helyettesítenünk az explicit képletet a bizonyítandó azonosságba. A számelméleti és kombinatorikus tulajdonságok bizonyításában, így az A. 244. feladat megoldásában azonban további ötletekre van szükség. Énekes Béla, Kós Géza ${}^{*}$Ismeretes, hogy tetszőleges $\alpha$ irracionális számhoz végtelen sok olyan pozitív egész $P$, $Q$ számpár létezik, amelyre $\left|\frac{P}{Q}-\alpha \right|<\frac{1}{2Q^2}$. Akik erről a témáról többet szeretnének tudni, azoknak ajánljuk, hogy olvassák el Gyarmati Edit‐Turán Pál: Számelmélet c. jegyzetének Diofantikus approximáció c. fejezetét vagy Erdős Pál‐Surányi János: Válogatott fejezetek a számelméletből c. könyvének Racionális és irracionális számok. Számok megközelítése racionális számmal. (diofantoszi approcimáció) c. fejezetét.