Перегляд вихідного коду сторінки Послідовність Фібоначчі

[[Файл:FibonacciBlocks.svg|thumb|right|Розбиття на квадрати, в яких кожна довжина сторін підпорядковується послідовності чисел Фібоначчі]]
[[Файл:Fibonacci spiral 34.svg|right|thumb|180px|Спіраль Фібоначчі: апроксимація [[Золота спіраль|золотої спіралі]] утворена круглими дугами, що проведені через протилежні кути квадратів Фібоначчі;<ref>{{cite book | url=https://books.google.com/books?id=CDEEAwAAQBAJ&pg=PA81 | title=Exploring the World of Mathematics: From Ancient Record Keeping to the Latest Advances in Computers | author=John Hudson Tiner | publisher=New Leaf Publishing Group | year=200 | isbn=978-1-61458-155-0 | accessdate=24 січня 2017 | archive-date=12 січня 2017 | archive-url=https://web.archive.org/web/20170112093352/https://books.google.com/books?id=CDEEAwAAQBAJ&pg=PA81 }}</ref> в цьому прикладі сторони квадратів були такими: 1, 1, 2, 3, 5, 8, 13, 21, і 34.]]

'''Послідо́вність Фібона́ччі, чи́сла Фібона́ччі'''&nbsp;— у [[математика|математиці]] числова послідовність <math>{F_n},</math> задана [[рекурентне співвідношення|рекурентним співвідношенням]] другого порядку
: <math> F_1=1, F_2=1, F_{n+2}=F_{n}+F_{n+1}, n=1,2,3,\ldots, </math>
: <math> F_1=1, F_2=1, F_3=2, F_4=3, F_5=5, F_6=8, F_7=13, F_8=21, \, </math>
і&nbsp;т.&nbsp;д. Ця послідовність виникає у найрізноманітніших математичних ситуаціях&nbsp;— комбінаторних, числових, геометричних.

Простіше кажучи, перші два члени послідовності&nbsp;— одиниці, а кожний наступний&nbsp;— сума значень двох попередніх чисел:
: <math>1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;</math>

Часто, особливо в сучасному вигляді, послідовність доповнюється ще одним початковим членом:

: <math>0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\; \ldots\;</math>.

За визначенням, перші два числа в послідовності Фібоначчі є або 1 і 1, або 0 і 1, залежно від обраного початку послідовностей, а кожне наступне число є сумою двох попередніх.

В математичних термінах послідовність чисел Фібоначчі ''F<sub>n</sub>'' визначається як [[рекурентне співвідношення]]
: <math>F_n=F_{n-1} + F_{n-2},</math>

із {{Нп|Початкові значеннями|початковими значеннями||Initial condition}} {{Sfn | Beck | Geoghegan | 2010}}{{Sfn | Bóna | 2011 | p=180}}
: <math>F_1=1,\; F_2=1</math>
або{{Sfn | Lucas | 1891 | p=3}}
: <math>F_0=0,\; F_1=1.</math>

[[Файл:Helianthus whorl.jpg|thumb|right|Суцвіття [[Соняшник|соняшника]] з 34 спіралями в один бік і 55 в інший]]
У природі числа Фібоначчі часто трапляються в різних спіральних формах. Так, [[Черешок|черешки листя]] примикають до стебла по спіралі, що проходить між двома сусідніми листками: 1/3 повного оберту в [[Ліщина звичайна|ліщини]], 2/5&nbsp;— у [[Дуб|дуба]], 3/8&nbsp;— у [[Тополя|тополі]] і [[Груша звичайна|груші]], 5/13&nbsp;— у [[Верба|верби]]; лусочки на ялиновій шишці, насіння соняшника розташовані спіралями, причому кількості спіралей кожного напрямку також, як правило, числа Фібоначчі.

Послідовність названа на честь математика XIII століття Леонардо [[Фібоначчі]] з [[Піза|Пізи]]. Його 1202 книга&nbsp;— ''[[Книга абака]]''&nbsp;— представила цю послідовність спільноті західноєвропейських математиків{{Sfn | Pisano | 2002 | pp=404–5}}, хоча така послідовність вже була описана раніше як числа {{Нп|Вараханк|Вараханка||Virahanka}} в [[Індійська математика|індійській математиці]]. Послідовність, описана в «Книзі абака», починалася з ''F''<sub>1</sub>&nbsp;=&nbsp;1.

== Формула Біне ==
Числа Фібоначчі тісно пов'язані з [[золотий перетин|золотим перетином]] <math>\phi=\frac{1 + \sqrt{5}}{2}.</math> '''Формула Біне''' виражає за допомогою <math>\phi</math> значення <math>F_n</math> в явному вигляді як функцію від <math>n</math>:
: <math>F_n = \frac{\phi^n - (-\phi )^{-n}}{\phi - (-\phi )^{-1}} = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}}\approx\frac{\phi^n}{\sqrt{5}}\quad (n\geqslant 1).</math>
При цьому <math>\phi=1,618\ldots\,\!</math> і <math>(-\phi)^{-1}=1-\phi=-0,618\ldots\,\!</math> є коренями квадратного рівняння <math>x^2-x-1=0\,\!</math>.

Оскільки <math>-1<1-\phi<0,</math> знаходимо, що при <math>n\geqslant 1,\ -1<(1-\phi)^n<1.</math> Тому з формули Біне випливає, що для всіх натуральних <math>n,\, F_n</math> є найближчим до
<math>\frac{\phi^n}{\sqrt{5}}\,</math> цілим числом, тому <math>F_n = \left[\frac{\phi^n}{\sqrt{5}}\right]</math> або <math>F_n = \left\lfloor\frac{\phi^n}{\sqrt{5}}+\frac12\right\rfloor</math>. Зокрема, справедлива [[асимптотика]] <math>F_n\sim \frac{\phi^n}{\sqrt{5}},\ n\to\infty.</math>

== Властивості чисел Фібоначчі ==
* [[Найбільший спільний дільник]] двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом, рівним найбільшому спільному дільнику індексів, тобто: <math>(F_m,F_n) = F_{(m,n)}\,\!</math>. Внаслідок цього:
** <math>F_m</math> ділиться на <math>F_n</math> тоді й тільки тоді, коли <math>m</math> ділиться на <math>n</math> (за винятком <math>n=2</math>);
** кожне третє число Фібоначчі парне (<math>F_3=2, F_6=8, F_9=34</math>);
** кожне четверте ділиться на три (<math>F_4=3, F_8=21, F_{12}=144</math>);
** кожне п'ятнадцяте закінчується нулем (<math>F_{15}=610</math>);
** два сусідніх числа Фібоначчі [[взаємно прості числа|взаємно прості]];
** <math>F_m</math> може бути [[просте число|простим]] тільки для простих <math>m</math> (за єдиним винятком <math>m=4,</math> що пов'язано з <math>F_2=1</math>). Зворотне твердження '''неправильне''': <math>F_{19}=4181=37\cdot 113,</math> хоча <math>19</math>&nbsp;— просте число. Тепер невідомо, чи існує нескінченно багато простих чисел Фібоначчі.
* Використовуючи те саме рекурентне співвідношення, що і на початку, у вигляді <math>F_n=F_{n+2}-F_{n+1}</math>, можливо поширити визначення чисел Фібоначчі і на від'ємні індекси: <math>F_0=0, F_{-1} = 1, F_{-2} = -1, F_{-3} = 2, F_{-4} = -3, F_{-5}=5, \ldots.</math> Неважко переконатися, що <math>F_{-n}=(-1)^{n+1}F_{n},</math> тобто одержуємо таку саму послідовність із знаками, що чергуються.
* Послідовність чисел Фібоначчі є частковим випадком генерованої послідовності, її [[характеристичний многочлен]] рівний <math>x^2 - x - 1</math> і має корені <math>\phi</math> і <math>-1/\phi</math>.
* [[Генератриса|Генератрисою]] послідовності чисел Фібоначчі є:
:: <math>0 + x + x^2 + 2 x^3 + 3 x^4 + 5 x^5 + \dots = \sum_{n=0}^{\infty} F_n x^n = \frac{x}{1-x-x^2}</math>
* Числа Фібоначчі можна представити значеннями [[континуанта|континуант]] на наборі одиниць: <math>F_n = K_n(1,\dots,1)</math>, тобто
:: <math>F_n =
\det \begin{pmatrix} 
1 & 1    & 0 &\cdots & 0 \\ 
-1  & 1  & 1 &  \ddots    & \vdots\\
0   & -1   & \ddots &\ddots & 0 \\
\vdots & \ddots  & \ddots   &\ddots & 1 \\ 
0 & \cdots & 0 & -1 & 1
\end{pmatrix}</math>, а також <math>\ F_{n+1} =
\det \begin{pmatrix} 
1 & i    & 0 &\cdots & 0 \\ 
i  & 1  & i &  \ddots    & \vdots\\
0   & i   & \ddots &\ddots & 0 \\
\vdots & \ddots  & \ddots   &\ddots & i \\ 
0 & \cdots & 0 & i & 1\end{pmatrix}</math>,
: де матриці мають розмір <math>n\times n</math>, <math>i</math>&nbsp;— [[уявна одиниця]].
* Для будь-якого ''n'',
:: <math>\begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n =
       \begin{pmatrix} F_{n+1} & F_n \\
                       F_n   & F_{n-1} \end{pmatrix}.</math>
: Ця формула надає швидкий алгоритм обчислення чисел Фібоначчі за допомогою матричного варіанта алгоритму [[Швидке піднесення до степеня|швидкого піднесення до степеня]]. Обчислення [[визначник]]ів дає:
::: <math>(-1)^n = F_{n+1} F_{n-1} - F_n^2</math>
* Відношення <math>\frac{F_{n+1}}{F_n}</math> є [[ланцюговий дріб|підходящими дробами]] [[Золотий перетин|золотого перетину]] <math>\phi</math> і, зокрема, <math>\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\phi</math>.
: Доведення. Позначимо <math>\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=x.</math> Враховуючи, що <math>F_{n+1} = F_n + F_{n-1},</math> і вважаючи, що шукана границя існує і не дорівнює нулю, запишемо:
: <math>\lim_{n\to\infty}\frac{F_{n+1}}{F_n}= \lim\limits_{n\to\infty}\frac{F_n + F_{n-1}}{F_n}= 1+\lim\limits_{n\to\infty}\frac{F_{n-1}}{F_n}= 
1+\frac{1}{\lim\limits_{n\to\infty}\frac{F_{n}}{F_{n-1}}}= 
1+\frac{1}{\lim\limits_{n\to\infty}\frac{F_{n+1}}{F_{n}}}.</math>
: Отримуємо просте рівняння <math>x = 1 + \frac{1}{x},</math> яке зводиться до квадратного рівняння <math>x^2 - x - 1 = 0.</math>
: Розв'язками є числа <math>x_1 = \frac{1+\sqrt{5}}{2}</math> і <math>x_2 = \frac{1-\sqrt{5}}{2}.</math>
: Очевидно, що розв'язок <math>x_2<0</math> не підходить, тому остаточно:
: <math>\lim\limits_{n\to\infty}\frac{F_{n+1}}{F_n}=
\frac{1+\sqrt{5}}{2}=\phi. </math>
* Суми [[біноміальний коефіцієнт|біноміальних коефіцієнтів]] на діагоналях [[трикутник Паскаля|трикутника Паскаля]] є числами Фібоначчі з огляду на формулу
: <math>F_{n+1} = \sum_{k=0}^{\lfloor n/2\rfloor} {n-k\choose k}</math>.
* У 1964&nbsp;р. ''J. H. E. Cohn'' довів, що єдиними точними квадратами серед чисел Фібоначчі є <math>F_0=0, F_1=F_2=1</math> і <math>F_{12}=144=12^2.</math>

* Множина чисел Фібоначчі збігається з множиною натуральних значень наступного [[многочлен|полінома]] двох змінних
:: <math>P(x,y)= 2xy^4 + x^2 y^3 - 2 x^3 y^2 - y^5 -  x^4 y + 2y,</math>
де <math>x,y\in\mathbb{Z}</math>&nbsp;— цілі числа. (див. ''P. Ribenboim, The New Book of Prime Number Records, Springer'', 1996, с. 153). Цей факт, виявлений Дж. Джоунзом, відіграє ключову роль у [[теорема Матіясевича|теоремі Матіясевича]] (негативному розв'язанні [[Десята проблема Гільберта|десятої проблеми Гільберта]]), тому що він надає спосіб задати експоненціально зростаючу послідовність чисел Фібоначчі у вигляді {{нп|діофантова множина|діофантової множини|en|diophantine set}}.

== Числа Фібоначчі за ''O(ln n)'' ==
Ідея полягає в наступному:

<math>F_n = F_{n-1} + F_{n-2};</math>

<math>F_{n+1} = F_n + F_{n-1} = 2\cdot F_{n-1} + F_{n-2}.</math>

Можна користуватися цими формулами в початковому вигляді, проте більш ефективним буде таке матричне рівняння:

<math> \begin{pmatrix} F_n\\ F_{n+1}\end{pmatrix}=\begin{pmatrix}1&1\\1&2\end{pmatrix}\cdot\begin{pmatrix}F_{n-2}\\F_{n-1}\end{pmatrix}.</math>

Якщо через ''A'' позначити матрицю

<math>A=\begin{pmatrix}1&1\\1&2\end{pmatrix},</math>

то отримаємо

<math> \begin{pmatrix} F_{2n}\\F_{2n+1}\end{pmatrix}=A^n\cdot\begin{pmatrix}1\\1\end{pmatrix}.</math>

Отже, щоб вирахувати ''2n-е/2n+1''-ше число Фібоначчі, треба матрицю ''A'' піднести до ''n''-го степеня, а це можна зробити за ''O(ln n)'' операцій.

Зауважимо, що аналогічним способом можна знаходити ''n''-ий член довільної послідовності, заданої лінійним рекурентним рівнянням, за ''O(ln n)'' операцій.

== Історія відкриття ==
[[Файл:Liber abbaci magliab f124r.jpg|thumb|Сторінка з ''[[Liber abaci]]'' Фібоначчі, книга зберігається в [[Національна центральна бібліотека Флоренції|Національній центральній бібліотеці Флоренції]]. В прямокутній рамці справа послідовність Фібоначчі; порядкові номери вказані шрифтом чорного кольору словами латиною, з десятого номера&nbsp;— [[Римська система числення|римськими цифрами]], сама послідовність подана червоним кольором [[Індо-арабська система числення|арабськими цифрами]].]]
У XIII столітті італійський математик [[Фібоначчі]] розв'язував таку задачу: Фермер годує кроликів. Кожна пара кроликів народжує одну пару кроликів, коли парі стає 2 місяці, а потім дає потомство в 1 пару щомісяця. Скільки пар кроликів буде у фермера через ''n'' місяців, якщо спочатку у нього була лише одна пара кроликів (вважаємо, що кролики не гинуть і кожен народжений дає потомство за вище описаною схемою)?

Очевидно, що першого та другого місяця у фермера залишається одна пара, оскільки потомства ще немає. На третій місяць буде дві, оскільки перші через два місяці народять другу пару кроликів. На четвертий місяць перші кролики дадуть ще одну, а другі кролики потомства не дадуть, оскільки їм ще тільки один місяць. Отож на четвертий місяць буде три пари кроликів.
 
Можна помітити, що кількість кроликів після ''n''-го місяця дорівнює кількості кроликів, які були у ''n-1'' місяці, плюс кількість народжених кроликів. Останніх буде стільки, скільки є кроликів, що дають потомство, або дорівнює кількості кроликів, яким уже виповнилося 2 місяці (тобто кількості кроликів після ''n-2'' місяця).

Якщо через ''F<sub>n</sub>'' позначити кількість кроликів після ''n''-го місяця, то маємо таке рекурентне співвідношення:

<math>F_n = F_{n-1} + F_{n-2}, F_1 = F_2 = 1</math>

Покладемо ''F<sub>0</sub> = 0'', при цьому співвідношення при ''n = 2'' залишиться істинним. Таким чином утворюється послідовність

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, …
[[File:Fibonacci Rabbits.svg|left|thumb|upright=1.5|У зростаючій ідеалізованій популяції кількість пар кроликів утворює послідовність Фібоначчі. Наприкінці ''n''-го місяця кількість пар дорівнює ''F<sub>n.</sub>'']]
{{clear|left}}

== Див. також ==
* [[Куб Фібоначчі]]
* [[Період Пізано]]
* [[Послідовність Гофстедтера]]
* [[Послідовність Люка]]
* [[Теорема Цекендорфа]]
* [[Числа трибоначчі]]
* [[Числа Якобсталя]]

== Посилання ==
* [http://www.codecodex.com/wiki/index.php?title=Fibonacci_sequence CodeCodex: Fibonacci sequence] {{Webarchive|url=https://web.archive.org/web/20070304181804/http://www.codecodex.com/wiki/index.php?title=Fibonacci_sequence |date=4 березня 2007 }}{{ref-en|}}— приклади програм обчислення чисел Фібоначчі.
* Послідовність Фібоначчі — {{OEIS|A000045}}

== Примітки ==
{{reflist}}

== Література ==
* Воробьев, Числа Фибоначчи (Популярные лекции по математике, вып. 5). М., Наука.
* Грант Аракелян''.'' ''Математика и история золотого сечения''. Логос, 2014, 404 с. ISBN 978-5-98704-663-0.

{{Класи натуральних чисел}}
{{Послідовності й ряди}}
{{ВП-портали|Математика|}}

[[Категорія:Цілочисельні послідовності]]
[[Категорія:Золотий перетин]]
[[Категорія:Числа з власними іменами]]