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

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

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

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

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

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

Սահմանում

Ֆիբոնաչիի թվերը կարելի է սահմանել հետևյալ ռեկուրենտ հարաբերությամբ^[6]. $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$ թվերի համար^[7]^[8]։

Առաջին 20 $F n$ Ֆիբոնաչիի թվերն են^[1].

$F 0$	$F 1$	$F 2$	$F 3$	$F 4$	$F 5$	$F 6$	$F 7$	$F 8$	$F 9$	$F 10$	$F 11$	$F 12$	$F 13$	$F 14$	$F 15$	$F 16$	$F 17$	$F 18$	$F 19$
0	1	1	2	3	5	8	13	21	34	55	89	144	233	377	610	987	1597	2584	4181

Պատմություն

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

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

Բինեի բանաձև

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

$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$

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

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

Այս հարաբերության և Ֆիբոնաչիի թվերի կապը տեսնելու համար^[11] անհաժեշտ է նկատել, որ $φ$ և $ψ$ թվերը ${\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 = 0$ և $U 1 = 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 0$ և $U 1$ հաստատուններ վերցնելու դեպքում ստացվում է հետևյալ ընդհանուր լուծումը.

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

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

Ընդ որում, մոտարկման սխալը շատ փոքր է. $n \geq 4$ արժեքների դեպքուն այն փոքր է 0.1-ից, իսկ $n \geq 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$ ^[12], և $\log _{10}(\varphi )=0.208987\ldots$ ^[13]։

Մեծություն

Քանի որ 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$ -ին^[14]^[15]. $\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}$ կանոնով։

Տես նաև

Ծանոթագրություններ

↑ ^1,0 ^1,1 Sloane, N. J. A. (ed.), «Sequence A000045 (Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1)», The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
↑ Goonatilake, Susantha (1998), Toward a Global Science, Indiana University Press, էջ 126, ISBN 978-0-253-33388-9
↑ Singh, Parmanand (1985), «The So-called Fibonacci numbers in ancient and medieval India», Historia Mathematica, 12 (3): 229–44, doi:10.1016/0315-0860(85)90021-7
↑ Knuth, Donald (2006), The Art of Computer Programming, vol. 4. Generating All Trees – History of Combinatorial Generation, Addison–Wesley, էջ 50, ISBN 978-0-321-33570-8, «it was natural to consider the set of all sequences of [L] and [S] that have exactly m beats. ... there are exactly Fm+1 of them. For example the 21 sequences when $m = 7$ are: [gives list]. In this way Indian prosodists were led to discover the Fibonacci sequence, as we have observed in Section 1.2.8 (from v.1)»
↑ Sigler, 2002, էջեր 404–05
↑ Lucas, 1891, էջ 3
↑ Beck, Geoghegan
↑ Bóna, 2011, էջ 180
↑ Beutelspacher, Albrecht; Petri, Bernhard (1996), «Fibonacci-Zahlen», Der Goldene Schnitt, Einblick in die Wissenschaft, Vieweg+Teubner Verlag, էջեր 87–98, doi:10.1007/978-3-322-85165-9_6, ISBN 978-3-8154-2511-4
↑ Ball, 2003, էջ 156
↑ Ball, 2003, էջեր 155–156
↑ Sloane, N. J. A. (ed.), «Sequence A002390 (Decimal expansion of natural logarithm of golden ratio)», The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
↑ Sloane, N. J. A. (ed.), «Sequence A097348 (Decimal expansion of arccsch(2)/log(10))», The On-Line Encyclopedia of Integer Sequences, OEIS Foundation
↑ Kepler, Johannes (1966), A New Year Gift: On Hexagonal Snow, Oxford University Press, էջ 92, ISBN 978-0-19-858120-8
↑ Strena seu de Nive Sexangula, 1611

[oeis-1] 1,0 ^1,1 Sloane, N. J. A. (ed.), «Sequence A000045 (Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1)», The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

[GlobalScience-2] Goonatilake, Susantha (1998), Toward a Global Science, Indiana University Press, էջ 126, ISBN 978-0-253-33388-9

[HistoriaMathematica-3] Singh, Parmanand (1985), «The So-called Fibonacci numbers in ancient and medieval India», Historia Mathematica, 12 (3): 229–44, doi:10.1016/0315-0860(85)90021-7

[Donald_Knuth_2006_50-4] Knuth, Donald (2006), The Art of Computer Programming, vol. 4. Generating All Trees – History of Combinatorial Generation, Addison–Wesley, էջ 50, ISBN 978-0-321-33570-8, «it was natural to consider the set of all sequences of [L] and [S] that have exactly m beats. ... there are exactly Fm+1 of them. For example the 21 sequences when $m = 7$ are: [gives list]. In this way Indian prosodists were led to discover the Fibonacci sequence, as we have observed in Section 1.2.8 (from v.1)»

[Sigler—2002——404–05-5] Sigler, 2002, էջեր 404–05

[Lucas_—_1891_——3-6] Lucas, 1891, էջ 3

[Beck_—_Geoghegan_——-7] Beck, Geoghegan

[Bóna_—_2011_——180-8] Bóna, 2011, էջ 180

[9] Beutelspacher, Albrecht; Petri, Bernhard (1996), «Fibonacci-Zahlen», Der Goldene Schnitt, Einblick in die Wissenschaft, Vieweg+Teubner Verlag, էջեր 87–98, doi:10.1007/978-3-322-85165-9_6, ISBN 978-3-8154-2511-4

[Ball_—_2003_——156-10] Ball, 2003, էջ 156

[Ball_—_2003_——155–156-11] Ball, 2003, էջեր 155–156

[12] Sloane, N. J. A. (ed.), «Sequence A002390 (Decimal expansion of natural logarithm of golden ratio)», The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

[13] Sloane, N. J. A. (ed.), «Sequence A097348 (Decimal expansion of arccsch(2)/log(10))», The On-Line Encyclopedia of Integer Sequences, OEIS Foundation

[14] Kepler, Johannes (1966), A New Year Gift: On Hexagonal Snow, Oxford University Press, էջ 92, ISBN 978-0-19-858120-8

[15] Strena seu de Nive Sexangula, 1611

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]