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

Մաթեմատիկայում Ֆիբոնաչիի հաջորդականությունը թվային հաջորդականություն է, որի յուրաքանչյուր անդամ հավասար է նախորդ երկու անդամների գումարին։ Այս հաջորդականության անդամները կոչվում են Ֆիբոնաչիի թվեր և հաճախ նշանակվում են F_n-ով։ Սովորաբար հաջորդականությունը սկսվում է 0 և 1 թվերով, սակայն որոշ հեղինակներ այն սկսում են 1 և 1 կամ 1 և 2 թվերով՝ ինչպես Ֆիբոնաչին։ 0 և 1 թվերով սկսվելու դեպքում հաջորդականությունը ունի հետևյալ տեսքը.

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

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

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

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

Սահմանում

Ֆիբոնաչի պարույր. ոսկե պարույրի մոտարկում։

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

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

և

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

կամայական n > 1 թվի համար։

Որոշ սահմանումներում $F_{0}=0$ բացակայում է և հաջորդկանությունը սկսվում է $F_{1}=F_{2}=1,$ թվերով, իսկ $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 թվականին։

Ոսկե հատման հետ կապ

Հիմնական հոդված՝ Ոսկե հատում

Բինեի բանաձև

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

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

որտեղ

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

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

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

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

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

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

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

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

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

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

$${\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 թվերի համարժեք պահանջ է դրանց հետևյալ հավասարումների համակարգին բավարարելը.

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

որի

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

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

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

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

որտեղ

$${\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-ը ${\frac {\varphi ^{n}}{\sqrt {5}}}$-ին ամենամոտ ամբողջ թիվն է։ Հետևաբար, այն կարելի է գտնել կլորացնելով՝ օգվելով ամենամոտ ամբողջ թվի ֆունկցիայից․

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

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

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

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

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

որտեղ $\log _{\varphi }(x)=\ln(x)/\ln(\varphi )=\log _{10}(x)/\log _{10}(\varphi )$, $\ln(\varphi )=0.481211\ldots$, և $\log _{10}(\varphi )=0.208987\ldots$։

Մեծություն

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

Առհասարակ, b հաշվարկման համակարգում F_n-ի թվանշանների քանակը ասիմպտոտիկ է $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) և եզրակացրել, որ հարաբերությունը ձգտում է ոսկե հատմանը՝ $\varphi \colon$-ին.

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

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

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

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

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

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

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

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

Այս հավասարումը կարելի է ապացուցել մաթեմատիկական ինդուկցիայով.

$$\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}:$$

$\psi =-1/\varphi$ դեպքում ճիշտ է նաև $\psi ^{2}=\psi +1$ պնդումը, ինչպես նաև՝

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

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

Տես նաև

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