Ֆիբոնաչիի Հաջորդականություն

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....

Ֆիբոնաչիի թվերը առաջին անգամ նկարագրվել են Հնդկաստանում մ.թ.ա. 200 թվականին՝ Պինգալայի աշխատություններում։ Հաջորդականությունը կոչվել է ի պատիվ իտալացի մաթեմատիկոս Լեոնարդո Պիզանոյի (հայտնի է նաև որպես Ֆիբոնաչի), որը 1202 թվականին իր «Հաշվարկի գիքրը» (Liber Abaci) գրքում հաջորդականությունը ներկայացրել է Արևելյան Եվրոպայի մաթեմատիկոսներին։

Ֆիբոնաչիի թվերը հաճախ անսպասելիորեն հայտնվում են մաթեմատիկայի տարբեր խնդիրներում, այնքան, որ գոյություն ունի հենց այս երևույթը ուսումնասիրող ամսագիր՝ «Fibonacci Quarterly»-ն։ Ֆիբոնաչիի թվերը կիրառվում են համակարգչային ալգորիթմներում, ինչպես օրինակ Ֆիբոնաչիի որոնման մեթոդը և «Ֆիբոնաչիի կույտ» տվյալների կառուցվածքը, «Ֆիբոնաչիի խորանարդ» կոչվող գրաֆները օգտագործվում են զուգահեռ և բաշխված համակարգերը միացնելու համար։ Թվերը նաև հանդիպում են կենսաբանությունում, ինչպես օրինակ՝ ծառերի ճյուղավորումը, ցողունի վրա տերևների դասավորությունը կամ փշավոր արքայախնձորի պտղատուփերը։

Ֆիբոնաչիի թվերը կապված են ոսկե հատման հետ. Բինեի բանաձևը ցույց է տալիս, որ n-րդ Ֆիբոնաչիի թիվը կարելի է արտահայտել n թվի և ոսկե հարաբերությամբ, որից հետևում է, որ երկու երկու հաջորդական Ֆիբոնաչիի թվերի հարաբերությունը ձգտում է ոսկե հարաբերությանը, երբ n-ը ձգտում է անվերջության։ Ֆիբոնաչիի թվերը նաև կապված են Լուկասի թվերի հետ, որոնք կառուցվում են նույն ռեկուրենտ կանոնով, որով կառուցվում են Ֆիբոնաչիի թվերը։

 

Ֆիբոնաչիի թվերը կարելի է սահմանել հետևյալ ռեկուրենտ հարաբերությամբ.

$${\displaystyle F_{0}=0,\quad F_{1}=1,}$$

 

$${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$$

 

Որոշ սահմանումներում ${\displaystyle F_{0}=0}$  բացակայում է և հաջորդկանությունը սկսվում է ${\displaystyle F_{1}=F_{2}=1,}$  թվերով, իսկ ${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$  հարաբերությունը այս դեպքում ճիշտ է n > 2 թվերի համար։

Առաջին 20 F_n Ֆիբոնաչիի թվերն են.

F0	F1	F2	F3	F4	F5	F6	F7	F8	F9	F10	F11	F12	F13	F14	F15	F16	F17	F18	F19
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

Այս թվերը ներկայացրեց 1202 թվականին Լեոնարդո Ֆիբոնաչչին, ով հայտնի է նաև որպես «Լեոնարդո Պիզացի»։ Սակայն հենց 19-րդ դարի մաթեմատիկոս Լուկասի «Ֆիբոնաչչիի թվերը» դարձավ համընդհանուր օգտագործելի։ Այնուամենայնիվ այդ թվերը հիշատակվել են ավելի վաղ՝ 1135 թվականին Գոպալան և Խեմաչանդրան `1150 թվականին։

Բինեի բանաձև

Ինչպես հաստատուն գործակցով գծային ռեկուրենտ շատ հաջորդականություններ, Ֆիբոնաչիի թվերը նույնպես ունեն անալիտիկ ներկայացում։ Ֆրանսիացի մաթեմատիկոս Ժակ Ֆիլիպ Մարի Բինեի պատվին այն կոչվում է Բինեի բանաձև, չնայած բանաձևը հայտնի էր Աբրահամ դը Մուավրին և Դանիել Բեռնուլիին.

$${\displaystyle F_{n}={\frac {\varphi ^{n}-\psi ^{n}}{\varphi -\psi }}={\frac {\varphi ^{n}-\psi ^{n}}{\sqrt {5}}},}$$

 

որտեղ

$${\displaystyle \varphi ={\frac {1+{\sqrt {5}}}{2}}\approx 1.61803\,39887\ldots }$$

 

Ոսկե հատումն է, իսկ ψ-ը՝ դրա համալուծն է.

$${\displaystyle \psi ={\frac {1-{\sqrt {5}}}{2}}=1-\varphi =-{1 \over \varphi }\approx -0.61803\,39887\ldots .}$$

 

Քանի որ ${\displaystyle \psi =-\varphi ^{-1}}$ , հետևաբար բանաձևը կարելի է գրել հետևյալ կերպ.

$${\displaystyle F_{n}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{\sqrt {5}}}={\frac {\varphi ^{n}-(-\varphi )^{-n}}{2\varphi -1}}.}$$

 

Այս հարաբերության և Ֆիբոնաչիի թվերի կապը տեսնելու համար անհաժեշտ է նկատել, որ φ և ψ թվերը ${\textstyle x^{2}=x+1}$ , հետևաբար նաև ${\displaystyle x^{n}=x^{n-1}+x^{n-2}}$  հավասարման լուծումներ են։ Այսպիսով φ և ψ թվերը բավարարում են Ֆիբոնաչիի ռեկուրենտ կանոնին։ Այլ կերպ ասած,

$${\displaystyle {\begin{aligned}\varphi ^{n}&=\varphi ^{n-1}+\varphi ^{n-2},\\[3mu]\psi ^{n}&=\psi ^{n-1}+\psi ^{n-2}:\end{aligned}}}$$

 

Որից հետևում է, որ կամայական a և b թվերով սահմանված

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

 

հաջորդականությունը բավարարում է նույն ռեկուրսիային,

$${\displaystyle {\begin{aligned}U_{n}&=a\varphi ^{n}+b\psi ^{n}\\[3mu]&=a(\varphi ^{n-1}+\varphi ^{n-2})+b(\psi ^{n-1}+\psi ^{n-2})\\[3mu]&=a\varphi ^{n-1}+b\psi ^{n-1}+a\varphi ^{n-2}+b\psi ^{n-2}\\[3mu]&=U_{n-1}+U_{n-2}:\end{aligned}}}$$

 

Եթե a և b թվերը ընտրվեն այնպես, որ U₀ = 0 և U₁ = 1, ապա ստացված U_n հաջորդականությունը Ֆիբոնաչիի հաջորդականությունն է։ a և b թվերի համարժեք պահանջ է դրանց հետևյալ հավասարումների համակարգին բավարարելը.

$${\displaystyle \left\{{\begin{aligned}a+b&=0\\\varphi a+\psi b&=1\end{aligned}}\right.}$$

 

որի

$${\displaystyle a={\frac {1}{\varphi -\psi }}={\frac {1}{\sqrt {5}}},\quad b=-a,}$$

 

լուծումը բավարարում է անհրաժեշտ բանաձևին։

Կամայական U₀ և U₁ հաստատուններ վերցնելու դեպքում ստացվում է հետևյալ ընդհանուր լուծումը.

$${\displaystyle U_{n}=a\varphi ^{n}+b\psi ^{n}}$$

 

որտեղ

$${\displaystyle {\begin{aligned}a&={\frac {U_{1}-U_{0}\psi }{\sqrt {5}}},\\[3mu]b&={\frac {U_{0}\varphi -U_{1}}{\sqrt {5}}}.\end{aligned}}}$$

 

Կլորացմամբ հաշվում

Քանի որ ${\textstyle \left|{\frac {\psi ^{n}}{\sqrt {5}}}\right|<{\frac {1}{2}}}$  կամայական n ≥ 0 թվի համար, F_n-ը ${\displaystyle {\frac {\varphi ^{n}}{\sqrt {5}}}}$ -ին ամենամոտ ամբողջ թիվն է։ Հետևաբար, այն կարելի է գտնել կլորացնելով՝ օգվելով ամենամոտ ամբողջ թվի ֆունկցիայից․

$${\displaystyle F_{n}=\left\lfloor {\frac {\varphi ^{n}}{\sqrt {5}}}\right\rceil ,\ n\geq 0.}$$

 

Ընդ որում, մոտարկման սխալը շատ փոքր է. n ≥ 4 արժեքների դեպքուն այն փոքր է 0.1-ից, իսկ n ≥ 8 արժեքների դեպքում՝ 0.01-ից։ Այս բանաձևը կարելի է հեշտորեն շրջել՝ F Ֆիբոնաչիի թվի համարը ստանալու համար.

$${\displaystyle n(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}F\right\rceil ,\ F\geq 1.}$$

 

Ամենամոտ ամբողջ թվի փոխարեն ամբողջ մասը օգտագործելու դեպքում կստանքն F-ը չգերազանցող ամենամեծ Ֆիբոնաչիի թվի համարը.

$${\displaystyle n_{\mathrm {largest} }(F)=\left\lfloor \log _{\varphi }{\sqrt {5}}(F+1/2)\right\rfloor ,\ F\geq 0,}$$

 

${\displaystyle \log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )}$ 

${\displaystyle \ln(\varphi )=0.481211\ldots }$ 

${\displaystyle \log _{10}(\varphi )=0.208987\ldots }$ 

Մեծություն

Քանի որ F_n-ը ասիմպտոտիկ է ${\displaystyle \varphi ^{n}/{\sqrt {5}}}$ -ին, ապա F_n թվի թվանշանների քանակը ասիմպտոտիկ է ${\displaystyle n\log _{10}\varphi \approx 0.2090\,n}$ -ին։ Հանգունորեն, յուրաքանչյուր d > 1 ամբողջ թվի համար գոյություն ունեն 4 կամ 5 Ֆիբոնաչիի թվեր, որոնք ունեն d թվանշան։

Առհասարակ, b հաշվարկման համակարգում F_n-ի թվանշանների քանակը ասիմպտոտիկ է ${\displaystyle n\log _{b}\varphi ={\frac {n\log \varphi }{\log b}}}$ -ին։

Հաջորդական անդամների հարաբերության սահման

Յոհան Կեպլերը նկատել է, որ Ֆիբոնաչիի թվերի հաջորդկան անդամների հարաբերության սահմանը զուգամետ է։ Նա գրել է, որ «ինչպես 5-ն է 8-ի համար, գործնականում, այնպես 8-ն է 13-ի համար, և ինչպես 8-ն է 13-ի համար, այնպես 13-ն է 21-ի համար» (անգլ.՝ as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost) և եզրակացրել, որ հարաբերությունը ձգտում է ոսկե հատմանը՝ ${\displaystyle \varphi \colon }$ -ին.

$${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\varphi }$$

 

Այս զուգամիտությունը ճիշտ է անկախ ${\displaystyle U_{0}}$  և ${\displaystyle U_{1}}$  սկզբնական թվերի ընտրությունից (բացառությամբ երբ ${\displaystyle U_{1}=-U_{0}/\varphi }$ )։ Այս պնդումը կարելի է ապացուցել Բինեի բանաձևով։ Օրինակ, 3 և 2 սկզբնական թվերի դեպքում ստացվում է 3, 2, 5, 7, 12, 19, 31, 50, 81, 131, 212, 343, 555, ...  հաջորդականությունը, որի հաջորդկան անդամների հարաբերությունը նույնպես ձգտում է ոսկե հատմանը։

Ընդհանուր առմամբ ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+m}}{F_{n}}}=\varphi ^{m}}$ , քանի որ Ֆիբոնաչիի թվերի հաջորդկան անդամների հարաբերությունը ձգտում է ${\displaystyle \varphi }$ -ի։

Աստիճանների վերլուծում

Քանի որ ոսկե հատումը բավարարում է հետևյալ հավասարմանը

$${\displaystyle \varphi ^{2}=\varphi +1,}$$

 

ուրեմն այս արտահայտությունը կարելի է օգտագործել ${\displaystyle \varphi ^{n}}$ -ի բարձր աստիճանները ավելի փոքր աստիճանի գծային ֆունկցիայով վերլուծելու համար։ Այս սկզբունքի շարունակական կիառությամբ կստանանք ռեկուրենտ հարաբերություն.

$${\displaystyle \varphi ^{n}=F_{n}\varphi +F_{n-1}.}$$

 

$${\displaystyle \varphi ^{n+1}=(F_{n}\varphi +F_{n-1})\varphi =F_{n}\varphi ^{2}+F_{n-1}\varphi =F_{n}(\varphi +1)+F_{n-1}\varphi =(F_{n}+F_{n-1})\varphi +F_{n}=F_{n+1}\varphi +F_{n}:}$$

 

${\displaystyle \psi =-1/\varphi }$ 

${\displaystyle \psi ^{2}=\psi +1}$ 

$${\displaystyle \psi ^{n}=F_{n}\psi +F_{n-1}:}$$

 

Այս արտահայտությունները ճիշտ են նաև n < 1 դեպքում, եթե Ֆիբոնաչիի թվերը ընդլայնվեն բացասական թվերի համար ${\displaystyle F_{n}=F_{n+2}-F_{n+1}}$  կանոնով։

• Ոսկե հատում
• Ռեկուրսիա