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

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

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

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

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

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

Սահմանում

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

Ֆիբոնաչիի թվերը կարելի է սահմանել հետևյալ ռեկուրենտ հարաբերությամբԿաղապար:Sfn. $$F_0=0,F_1=1,$$ և $$F_n=F_{n-1}+F_{n-2}$$ կամայական Կաղապար:Math թվի համար։

Որոշ սահմանումներում $F_0=0$ բացակայում է և հաջորդկանությունը սկսվում է $F_1=F_2=1,$ թվերով, իսկ $F_n=F_{n-1}+F_{n-2}$ հարաբերությունը այս դեպքում ճիշտ է Կաղապար:Math թվերի համարԿաղապար:SfnԿաղապար:Sfn։

Առաջին 20 Կաղապար:Math Ֆիբոնաչիի թվերն են.

Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math	Կաղապար:Math
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{{\phi }^n-{\psi }^n}{\phi -\psi }=\frac{{\phi }^n-{\psi }^n}{\sqrt{5}},$$

որտեղ

$$\phi =\frac{1+\sqrt{5}}{2}\approx 1.6180339887\dots$$

Ոսկե հատումն է, իսկ Կաղապար:Mvar-ը՝ դրա համալուծն էԿաղապար:Sfn.

$$\psi =\frac{1-\sqrt{5}}{2}=1-\phi =-\frac{1}{\phi }\approx -0.6180339887\dots .$$

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

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

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

$$\begin{array}{cc}{\phi }^n& ={\phi }^{n-1}+{\phi }^{n-2},\\ {\psi }^n& ={\psi }^{n-1}+{\psi }^{n-2}:\end{array}$$

Որից հետևում է, որ կամայական Կաղապար:Mvar և Կաղապար:Mvar թվերով սահմանված

$$U_n=a{\phi }^n+b{\psi }^n$$

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

$$\begin{array}{cc}{U}_n& =a{\phi }^n+b{\psi }^n\\ & =a({\phi }^{n-1}+{\phi }^{n-2})+b({\psi }^{n-1}+{\psi }^{n-2})\\ & =a{\phi }^{n-1}+b{\psi }^{n-1}+a{\phi }^{n-2}+b{\psi }^{n-2}\\ & =U_{n-1}+U_{n-2}:\end{array}$$

Եթե Կաղապար:Mvar և Կաղապար:Mvar թվերը ընտրվեն այնպես, որ Կաղապար:Math և Կաղապար:Math, ապա ստացված Կաղապար:Math հաջորդականությունը Ֆիբոնաչիի հաջորդականությունն է։ Կաղապար:Mvar և Կաղապար:Mvar թվերի համարժեք պահանջ է դրանց հետևյալ հավասարումների համակարգին բավարարելը.

$$\{\begin{array}{cc}a+b& =0\\ \phi a+\psi b& =1\end{array}$$

որի

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

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

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

$$U_n=a{\phi }^n+b{\psi }^n$$

որտեղ

$$\begin{array}{cc}a& =\frac{U_1-U_0\psi }{\sqrt{5}},\\ b& =\frac{U_0\phi -U_1}{\sqrt{5}}.\end{array}$$

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

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

$$F_n=\lfloor \frac{{\phi }^n}{\sqrt{5}}\rceil ,n\ge 0.$$

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

$$n(F)=\lfloor {\log }_{\phi }\sqrt{5}F\rceil ,F\ge 1.$$

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

$$n_{\mathrm{l}\mathrm{a}\mathrm{r}\mathrm{g}\mathrm{e}\mathrm{s}\mathrm{t}}(F)=\lfloor {\log }_{\phi }\sqrt{5}(F+1/2)\rfloor ,F\ge 0,$$ որտեղ ${\log }_{\phi }(x)=\ln (x)/\ln (\phi )={\log }_{10}(x)/{\log }_{10}(\phi )$, $\ln (\phi )=0.481211\dots$, և ${\log }_{10}(\phi )=0.208987\dots$։

Մեծություն

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

Առհասարակ, Կաղապար:Mvar հաշվարկման համակարգում Կաղապար:Math-ի թվանշանների քանակը ասիմպտոտիկ է $n{\log }_b\phi =\frac{n\log \phi }{\log b}$-ին։

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

Յոհան Կեպլերը նկատել է, որ Ֆիբոնաչիի թվերի հաջորդկան անդամների հարաբերության սահմանը զուգամետ է։ Նա գրել է, որ «ինչպես 5-ն է 8-ի համար, գործնականում, այնպես 8-ն է 13-ի համար, և ինչպես 8-ն է 13-ի համար, այնպես 13-ն է 21-ի համար» (Կաղապար:Lang-en) և եզրակացրել, որ հարաբերությունը ձգտում է ոսկե հատմանը՝ $\phi :$-ին. $$\underset{n\to \mathrm{\infty }}{\lim }\frac{F_{n+1}}{F_n}=\phi$$

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

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

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

Քանի որ ոսկե հատումը բավարարում է հետևյալ հավասարմանը $${\phi }^2=\phi +1,$$

ուրեմն այս արտահայտությունը կարելի է օգտագործել ${\phi }^n$-ի բարձր աստիճանները ավելի փոքր աստիճանի գծային ֆունկցիայով վերլուծելու համար։ Այս սկզբունքի շարունակական կիառությամբ կստանանք ռեկուրենտ հարաբերություն. $${\phi }^n=F_n\phi +F_{n-1}.$$ Այս հավասարումը կարելի է ապացուցել մաթեմատիկական ինդուկցիայով. $${\phi }^{n+1}=(F_n\phi +F_{n-1})\phi =F_n{\phi }^2+F_{n-1}\phi =F_n(\phi +1)+F_{n-1}\phi =(F_n+F_{n-1})\phi +F_n=F_{n+1}\phi +F_n:$$ $\psi =-1/\phi$ դեպքում ճիշտ է նաև ${\psi }^2=\psi +1$ պնդումը, ինչպես նաև՝ $${\psi }^n=F_n\psi +F_{n-1}:$$

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

Տես նաև

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