Դիտել Ֆիբոնաչիի հաջորդականություն էջի վիքիկոդը

[[Մաթեմատիկա]]յում '''Ֆիբոնաչիի հաջորդականությունը''' թվային հաջորդականություն է, որի յուրաքանչյուր անդամ հավասար է նախորդ երկու անդամների գումարին։ Այս հաջորդականության անդամները կոչվում են '''Ֆիբոնաչիի թվեր''' և հաճախ նշանակվում են {{nowrap|{{math|''F<sub>n</sub>''}}}}-ով։ Սովորաբար հաջորդականությունը սկսվում է 0 և 1 թվերով, սակայն որոշ հեղինակներ այն սկսում են 1 և 1 կամ 1 և 2 թվերով՝ ինչպես Ֆիբոնաչին։ 0 և 1 թվերով սկսվելու դեպքում հաջորդականությունը ունի հետևյալ տեսքը.

: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ....<ref name=oeis>{{Cite OEIS|1=A000045|2=Fibonacci numbers: F(n) = F(n-1) + F(n-2) with F(0) = 0 and F(1) = 1|mode=cs2}}</ref>

Ֆիբոնաչիի թվերը առաջին անգամ նկարագրվել են [[Մաթեմատիկայի պատմությունը Հնդկաստանում|Հնդկաստանում]] մ.թ.ա. 200 թվականին՝ [[Պինգալա]]յի աշխատություններում<ref name=GlobalScience>{{Citation |last=Goonatilake |first=Susantha |title=Toward a Global Science |page=126 |year=1998 |url=https://books.google.com/books?id=SI5ip95BbgEC&pg=PA126 |publisher=Indiana University Press |isbn=978-0-253-33388-9}}</ref><ref name="HistoriaMathematica">{{Citation |last=Singh |first=Parmanand |title=The So-called Fibonacci numbers in ancient and medieval India |journal=Historia Mathematica |volume=12 |issue=3 |pages=229–44 |year=1985 |doi=10.1016/0315-0860(85)90021-7 |doi-access=free}}</ref><ref name="Donald Knuth 2006 50">{{Citation |last=Knuth |first=Donald |title=The Art of Computer Programming |volume=4. Generating All Trees – History of Combinatorial Generation |page=50 |year=2006 |url=https://books.google.com/books?id=56LNfE2QGtYC&q=rhythms&pg=PA50 |publisher=Addison–Wesley |isbn=978-0-321-33570-8 |quote=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 {{math|1=''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) |author-link=Donald Knuth}}</ref>։ Հաջորդականությունը կոչվել է ի պատիվ իտալացի մաթեմատիկոս [[Լեոնարդո Պիզանո]]յի (հայտնի է նաև որպես [[Ֆիբոնաչի]]), որը 1202 թվականին իր «Հաշվարկի գիքրը» ({{lang|la|[[Liber Abaci]]}}) գրքում հաջորդականությունը ներկայացրել է Արևելյան Եվրոպայի մաթեմատիկոսներին{{Sfn|Sigler|2002|pp=404–05}}։

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

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

== Սահմանում ==
[[File:Fibonacci Spiral.svg|thumb|Ֆիբոնաչի պարույր. [[ոսկե պարույր]]ի մոտարկում։]]
Ֆիբոնաչիի թվերը կարելի է սահմանել հետևյալ ռեկուրենտ հարաբերությամբ{{Sfn | Lucas | 1891 | p=3}}.
<math display=block>F_0=0,\quad F_1= 1,</math>
և
<math display=block>F_n=F_{n-1} + F_{n-2}</math>
կամայական {{math|''n'' > 1}} թվի համար։

Որոշ սահմանումներում <math>F_0 = 0</math> բացակայում է և հաջորդկանությունը սկսվում է <math>F_1=F_2=1,</math> թվերով, իսկ <math>F_n=F_{n-1} + F_{n-2}</math> հարաբերությունը այս դեպքում ճիշտ է {{math|''n'' > 2}} թվերի համար{{Sfn | Beck | Geoghegan | 2010}}{{Sfn | Bóna | 2011 | p=180}}։

Առաջին 20 {{math|''F<sub>n</sub>''}} Ֆիբոնաչիի թվերն են<ref name=oeis/>.
:{| class="wikitable" style="text-align:right"
! {{math|''F''<sub>0</sub>}}
! {{math|''F''<sub>1</sub>}}
! {{math|''F''<sub>2</sub>}}
! {{math|''F''<sub>3</sub>}}
! {{math|''F''<sub>4</sub>}}
! {{math|''F''<sub>5</sub>}}
! {{math|''F''<sub>6</sub>}}
! {{math|''F''<sub>7</sub>}}
! {{math|''F''<sub>8</sub>}}
! {{math|''F''<sub>9</sub>}}
! {{math|''F''<sub>10</sub>}}
! {{math|''F''<sub>11</sub>}}
! {{math|''F''<sub>12</sub>}}
! {{math|''F''<sub>13</sub>}}
! {{math|''F''<sub>14</sub>}}
! {{math|''F''<sub>15</sub>}}
! {{math|''F''<sub>16</sub>}}
! {{math|''F''<sub>17</sub>}}
! {{math|''F''<sub>18</sub>}}
! {{math|''F''<sub>19</sub>}}
|-
| 0
| 1
| 1
| 2
| 3
| 5
| 8
| 13
| 21
| 34
| 55
| 89
| 144
| 233
| 377
| 610
| 987
| 1597
| 2584
| 4181
|}

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

== Ոսկե հատման հետ կապ ==
{{Հիմնական|Ոսկե հատում}}

=== Բինեի բանաձև ===
Ինչպես հաստատուն գործակցով գծային ռեկուրենտ շատ [[Հաջորդականություն (մաթեմատիկա)|հաջորդականություններ]], Ֆիբոնաչիի թվերը նույնպես ունեն անալիտիկ ներկայացում։ Ֆրանսիացի մաթեմատիկոս Ժակ Ֆիլիպ Մարի Բինեի պատվին այն կոչվում է '''Բինեի բանաձև''', չնայած բանաձևը հայտնի էր [[Աբրահամ դը Մուավր]]ին և [[Դանիել Բեռնուլի]]ին<ref>{{Citation |last1=Beutelspacher |first1=Albrecht |title=Der Goldene Schnitt |pages=87–98 |year=1996 |series=Einblick in die Wissenschaft |contribution=Fibonacci-Zahlen |publisher=Vieweg+Teubner Verlag |doi=10.1007/978-3-322-85165-9_6 |isbn=978-3-8154-2511-4 |last2=Petri |first2=Bernhard}}</ref>.

<math display=block>
F_n = \frac{\varphi^n-\psi^n}{\varphi-\psi} = \frac{\varphi^n-\psi^n}{\sqrt 5},
</math>

որտեղ

<math display=block>
\varphi = \frac{1 + \sqrt{5}}{2} \approx 1.61803\,39887\ldots
</math>

[[Ոսկե հատում]]ն է, իսկ {{mvar|ψ}}-ը՝ դրա համալուծն է{{Sfn | Ball | 2003 | p = 156}}.

<math display=block>
\psi = \frac{1 - \sqrt{5}}{2} = 1 - \varphi = - {1 \over \varphi} \approx -0.61803\,39887\ldots.
</math>

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

<math display=block>
F_n = \frac{\varphi^n - (-\varphi)^{-n}}{\sqrt 5} = \frac{\varphi^n - (-\varphi)^{-n}}{2\varphi - 1}.
</math>

Այս հարաբերության և Ֆիբոնաչիի թվերի կապը տեսնելու համար{{Sfn | Ball | 2003 | pp = 155–156}} անհաժեշտ է նկատել, որ {{mvar|φ}} և {{mvar|ψ}} թվերը <math display=inline>x^2 = x + 1</math>, հետևաբար նաև <math>x^n = x^{n-1} + x^{n-2}</math> հավասարման լուծումներ են։ Այսպիսով {{mvar|φ}} և {{mvar|ψ}} թվերը բավարարում են Ֆիբոնաչիի ռեկուրենտ կանոնին։ Այլ կերպ ասած,

<math display=block>\begin{align}
\varphi^n &= \varphi^{n-1} + \varphi^{n-2}, \\[3mu]
\psi^n &= \psi^{n-1} + \psi^{n-2}:
\end{align}</math>

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

<math display=block>U_n=a \varphi^n + b \psi^n</math>

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

<math display=block>\begin{align}
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{align}</math>

Եթե {{mvar|a}} և {{mvar|b}} թվերը ընտրվեն այնպես, որ {{math|1=''U''<sub>0</sub> = 0}} և {{math|1=''U''<sub>1</sub> = 1}}, ապա ստացված {{math|''U''<sub>''n''</sub>}} հաջորդականությունը Ֆիբոնաչիի հաջորդականությունն է։ {{mvar|a}} և {{mvar|b}} թվերի համարժեք պահանջ է դրանց հետևյալ հավասարումների համակարգին բավարարելը.

<math display=block>
\left\{\begin{align} a + b &= 0 \\ \varphi a + \psi b &= 1\end{align}\right.
</math>

որի

<math display=block>
a = \frac{1}{\varphi-\psi} = \frac{1}{\sqrt 5},\quad  b = -a,
</math>

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

Կամայական {{math|''U''<sub>0</sub>}} և {{math|''U''<sub>1</sub>}} հաստատուններ վերցնելու դեպքում ստացվում է հետևյալ ընդհանուր լուծումը.

<math display=block> U_n = a\varphi^n + b\psi^n </math>

որտեղ

<math display=block>\begin{align}
a&=\frac{U_1-U_0\psi}{\sqrt 5}, \\[3mu]
b&=\frac{U_0\varphi-U_1}{\sqrt 5}.
\end{align}</math>

=== Կլորացմամբ հաշվում ===
Քանի որ 
<math display=inline>\left|\frac{\psi^{n}}{\sqrt 5}\right| < \frac{1}{2}</math> կամայական {{math|''n'' ≥ 0}} թվի համար, {{math|''F''<sub>''n''</sub>}}-ը <math>\frac{\varphi^n}{\sqrt 5}</math>-ին ամենամոտ [[ամբողջ թիվ]]ն է։ Հետևաբար, այն կարելի է գտնել կլորացնելով՝ օգվելով ամենամոտ ամբողջ թվի ֆունկցիայից․

<math display=block>F_n=\left\lfloor\frac{\varphi^n}{\sqrt 5}\right\rceil,\ n \geq 0.</math>

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

<math display=block>n(F) = \left\lfloor  \log_\varphi \sqrt{5}F\right\rceil,\ F \geq 1.</math>

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

<math display=block>n_{\mathrm{largest}}(F) = \left\lfloor  \log_\varphi \sqrt{5}(F+1/2)\right\rfloor,\ F \geq 0,</math>
որտեղ <math>\log_\varphi(x) = \ln(x)/\ln(\varphi) = \log_{10}(x)/\log_{10}(\varphi)</math>, <math>\ln(\varphi) = 0.481211\ldots</math><ref>{{Cite OEIS|1=A002390|2=Decimal expansion of natural logarithm of golden ratio|mode=cs2}}</ref>, և <math>\log_{10}(\varphi) = 0.208987\ldots</math><ref>{{Cite OEIS|1=A097348|2=Decimal expansion of arccsch(2)/log(10)|mode=cs2}}</ref>։

=== Մեծություն ===
Քանի որ ''F<sub>n</sub>''-ը ասիմպտոտիկ է <math>\varphi^n/\sqrt5</math>-ին, ապա {{math|''F''<sub>''n''</sub>}} թվի թվանշանների քանակը ասիմպտոտիկ է <math>n\log_{10}\varphi\approx 0.2090\, n</math>-ին։ Հանգունորեն, յուրաքանչյուր {{math|''d'' > 1}} ամբողջ թվի համար գոյություն ունեն 4 կամ 5 Ֆիբոնաչիի թվեր, որոնք ունեն {{mvar|d}} թվանշան։

Առհասարակ, {{mvar|b}} հաշվարկման համակարգում {{math|''F''<sub>''n''</sub>}}-ի թվանշանների քանակը ասիմպտոտիկ է <math>n\log_b\varphi = \frac{n \log \varphi}{\log b}</math>-ին։

=== Հաջորդական անդամների հարաբերության սահման ===
[[Յոհան Կեպլեր]]ը նկատել է, որ Ֆիբոնաչիի թվերի հաջորդկան անդամների հարաբերության սահմանը զուգամետ է։ Նա գրել է, որ «ինչպես 5-ն է 8-ի համար, գործնականում, այնպես 8-ն է 13-ի համար, և ինչպես 8-ն է 13-ի համար, այնպես 13-ն է 21-ի համար» ({{lang-en|as 5 is to 8 so is 8 to 13, practically, and as 8 is to 13, so is 13 to 21 almost}}) և եզրակացրել, որ հարաբերությունը ձգտում է ոսկե հատմանը՝ <math>\varphi\colon </math>-ին<ref>{{Citation |last=Kepler |first=Johannes |title=A New Year Gift: On Hexagonal Snow |page=92 |year=1966 |publisher=Oxford University Press |isbn=978-0-19-858120-8}}</ref><ref>{{Citation |title=Strena seu de Nive Sexangula |year=1611}}</ref>.
<math display=block>\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\varphi</math>

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

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

=== Աստիճանների վերլուծում ===
Քանի որ ոսկե հատումը բավարարում է հետևյալ հավասարմանը
<math display=block>\varphi^2 = \varphi + 1,</math>

ուրեմն այս արտահայտությունը կարելի է օգտագործել <math>\varphi^n</math>-ի բարձր աստիճանները ավելի փոքր աստիճանի գծային ֆունկցիայով վերլուծելու համար։ Այս սկզբունքի շարունակական կիառությամբ կստանանք ռեկուրենտ հարաբերություն.
<math display=block>\varphi^n = F_n\varphi + F_{n-1}.</math>
Այս հավասարումը կարելի է [[Մաթեմատիկական ապացույց|ապացուցել]] [[մաթեմատիկական ինդուկցիա]]յով.
<math display=block>\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:</math>
<math>\psi = -1/\varphi</math> դեպքում ճիշտ է նաև <math>\psi^2 = \psi + 1</math> պնդումը, ինչպես նաև՝
<math display=block>\psi^n = F_n\psi + F_{n-1}:</math>

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

== Տես նաև ==
* [[Ոսկե հատում]]
* [[Ռեկուրսիա]]

== Ծանոթագրություններ ==
{{ծանցանկ}}

[[Կատեգորիա:Ամբողջ թվեր]]
[[Կատեգորիա:Թվային համակարգեր]]
[[Կատեգորիա:Թվեր]]