Послідовність Фібоначчі

Розбиття на квадрати, в яких кожна довжина сторін підпорядковується послідовності чисел Фібоначчі

Послідо́вність Фібона́ччі, чи́сла Фібона́ччі — у математиці числова послідовність ${F_{n}},$ задана рекурентним співвідношенням другого порядку

F_{1}=1,F_{2}=1,F_{n+2}=F_{n}+F_{n+1},n=1,2,3,\ldots ,

F_{1}=1,F_{2}=1,F_{3}=2,F_{4}=3,F_{5}=5,F_{6}=8,F_{7}=13,F_{8}=21,\,

і т. д. Ця послідовність виникає у найрізноманітніших математичних ситуаціях — комбінаторних, числових, геометричних.

Простіше кажучи, перші два члени послідовності — одиниці, а кожний наступний — сума значень двох попередніх чисел:

1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;

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

0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;

.

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

В математичних термінах послідовність чисел Фібоначчі F_n визначається як рекурентне співвідношення

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

із початковими значеннями^[en] ^[2]^[3]

F_{1}=1,\;F_{2}=1

або^[4]

F_{0}=0,\;F_{1}=1.

У природі числа Фібоначчі часто трапляються в різних спіральних формах. Так, черешки листя примикають до стебла по спіралі, що проходить між двома сусідніми листками: 1/3 повного оберту в ліщини, 2/5 — у дуба, 3/8 — у тополі і груші, 5/13 — у верби; лусочки на ялиновій шишці, насіння соняшника розташовані спіралями, причому кількості спіралей кожного напрямку також, як правило, числа Фібоначчі.

Послідовність названа на честь математика XIII століття Леонардо Фібоначчі з Пізи. Його 1202 книга — Книга абака — представила цю послідовність спільноті західноєвропейських математиків^[5], хоча така послідовність вже була описана раніше як числа Вараханка^[en] в індійській математиці●. Послідовність, описана в «Книзі абака», починалася з F₁ = 1.

Формула Біне

Числа Фібоначчі тісно пов'язані з золотим перетином $\phi ={\frac {1+{\sqrt {5}}}{2}}.$ Формула Біне виражає за допомогою $\phi$ значення $F_{n}$ в явному вигляді як функцію від $n$ :

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).

При цьому $\phi =1,618\ldots \,\!$ і $(-\phi )^{-1}=1-\phi =-0,618\ldots \,\!$ є коренями квадратного рівняння $x^{2}-x-1=0\,\!$ .

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

Властивості чисел Фібоначчі

Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом, рівним найбільшому спільному дільнику індексів, тобто: $(F_{m},F_{n})=F_{(m,n)}\,\!$ $(F_{m},F_{n})=F_{(m,n)}\,\!$ . Внаслідок цього:
- $F_{m}$ ділиться на $F_{n}$ тоді й тільки тоді, коли $m$ ділиться на $n$ (за винятком $n=2$ );
- кожне третє число Фібоначчі парне ( $F_{3}=2,F_{6}=8,F_{9}=34$ );
- кожне четверте ділиться на три ( $F_{4}=3,F_{8}=21,F_{12}=144$ );
- кожне п'ятнадцяте закінчується нулем ( $F_{15}=610$ );
- два сусідніх числа Фібоначчі взаємно прості;
- $F_{m}$ може бути простим тільки для простих $m$ (за єдиним винятком $m=4,$ що пов'язано з $F_{2}=1$ ). Зворотне твердження неправильне: $F_{19}=4181=37\cdot 113,$ хоча $19$ — просте число. Тепер невідомо, чи існує нескінченно багато простих чисел Фібоначчі.
Використовуючи те саме рекурентне співвідношення, що і на початку, у вигляді $F_{n}=F_{n+2}-F_{n+1}$ , можливо поширити визначення чисел Фібоначчі і на від'ємні індекси: $F_{0}=0,F_{-1}=1,F_{-2}=-1,F_{-3}=2,F_{-4}=-3,F_{-5}=5,\ldots .$ Неважко переконатися, що $F_{-n}=(-1)^{n+1}F_{n},$ тобто одержуємо таку саму послідовність із знаками, що чергуються.
Послідовність чисел Фібоначчі є частковим випадком генерованої послідовності, її характеристичний многочлен рівний $x^{2}-x-1$ і має корені $\phi$ і $-1/\phi$ .
Генератрисою послідовності чисел Фібоначчі є:

0+x+x^{2}+2x^{3}+3x^{4}+5x^{5}+\dots =\sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}

Числа Фібоначчі можна представити значеннями континуант на наборі одиниць: $F_{n}=K_{n}(1,\dots ,1)$ , тобто

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

, а також

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

,

де матриці мають розмір

n\times n

,

i

— уявна одиниця.

Для будь-якого n,

{\begin{pmatrix}1&1\\1&0\end{pmatrix}}^{n}={\begin{pmatrix}F_{n+1}&F_{n}\\F_{n}&F_{n-1}\end{pmatrix}}.

Ця формула надає швидкий алгоритм обчислення чисел Фібоначчі за допомогою матричного варіанта алгоритму швидкого піднесення до степеня. Обчислення визначників дає:

(-1)^{n}=F_{n+1}F_{n-1}-F_{n}^{2}

Відношення ${\frac {F_{n+1}}{F_{n}}}$ є підходящими дробами золотого перетину $\phi$ і, зокрема, $\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=\phi$ .

Доведення. Позначимо

\lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=x.

Враховуючи, що

F_{n+1}=F_{n}+F_{n-1},

і вважаючи, що шукана границя існує і не дорівнює нулю, запишемо:

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

Отримуємо просте рівняння

x=1+{\frac {1}{x}},

яке зводиться до квадратного рівняння

x^{2}-x-1=0.

Розв'язками є числа

x_{1}={\frac {1+{\sqrt {5}}}{2}}

і

x_{2}={\frac {1-{\sqrt {5}}}{2}}.

Очевидно, що розв'язок

x_{2}<0

не підходить, тому остаточно:

\lim \limits _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}={\frac {1+{\sqrt {5}}}{2}}=\phi .

Суми біноміальних коефіцієнтів на діагоналях трикутника Паскаля є числами Фібоначчі з огляду на формулу

F_{n+1}=\sum _{k=0}^{\lfloor n/2\rfloor }{n-k \choose k}

.

У 1964 р. J. H. E. Cohn довів, що єдиними точними квадратами серед чисел Фібоначчі є $F_{0}=0,F_{1}=F_{2}=1$ і $F_{12}=144=12^{2}.$

Множина чисел Фібоначчі збігається з множиною натуральних значень наступного полінома двох змінних

P(x,y)=2xy^{4}+x^{2}y^{3}-2x^{3}y^{2}-y^{5}-x^{4}y+2y,

де $x,y\in \mathbb {Z}$ — цілі числа. (див. P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, с. 153). Цей факт, виявлений Дж. Джоунзом, відіграє ключову роль у теоремі Матіясевича (негативному розв'язанні десятої проблеми Гільберта), тому що він надає спосіб задати експоненціально зростаючу послідовність чисел Фібоначчі у вигляді діофантової множини^[en].

Числа Фібоначчі за O(ln n)

Ідея полягає в наступному:

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

$F_{n+1}=F_{n}+F_{n-1}=2\cdot F_{n-1}+F_{n-2}.$

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

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

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

$A={\begin{pmatrix}1&1\\1&2\end{pmatrix}},$

то отримаємо

${\begin{pmatrix}F_{2n}\\F_{2n+1}\end{pmatrix}}=A^{n}\cdot {\begin{pmatrix}1\\1\end{pmatrix}}.$

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

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

Історія відкриття

У XIII столітті італійський математик Фібоначчі розв'язував таку задачу: Фермер годує кроликів. Кожна пара кроликів народжує одну пару кроликів, коли парі стає 2 місяці, а потім дає потомство в 1 пару щомісяця. Скільки пар кроликів буде у фермера через n місяців, якщо спочатку у нього була лише одна пара кроликів (вважаємо, що кролики не гинуть і кожен народжений дає потомство за вище описаною схемою)?

Очевидно, що першого та другого місяця у фермера залишається одна пара, оскільки потомства ще немає. На третій місяць буде дві, оскільки перші через два місяці народять другу пару кроликів. На четвертий місяць перші кролики дадуть ще одну, а другі кролики потомства не дадуть, оскільки їм ще тільки один місяць. Отож на четвертий місяць буде три пари кроликів.

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

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

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

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

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

Див. також

Посилання

CodeCodex: Fibonacci sequence [Архівовано 4 березня 2007 у Wayback Machine.](англ.)— приклади програм обчислення чисел Фібоначчі.
Послідовність Фібоначчі — послідовність A000045 з Онлайн енциклопедії послідовностей цілих чисел, OEIS

Примітки

↑ John Hudson Tiner (200). Exploring the World of Mathematics: From Ancient Record Keeping to the Latest Advances in Computers. New Leaf Publishing Group. ISBN 978-1-61458-155-0. Архів оригіналу за 12 січня 2017. Процитовано 24 січня 2017.
↑ Beck та Geoghegan, 2010.
↑ Bóna, 2011, с. 180.
↑ Lucas, 1891, с. 3.
↑ Pisano, 2002, с. 404—5.

Література

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

Портал «Математика»

[1] John Hudson Tiner (200). Exploring the World of Mathematics: From Ancient Record Keeping to the Latest Advances in Computers. New Leaf Publishing Group. ISBN 978-1-61458-155-0. Архів оригіналу за 12 січня 2017. Процитовано 24 січня 2017.

[FOOTNOTEBeckGeoghegan2010-2] Beck та Geoghegan, 2010.

[FOOTNOTEBóna2011180-3] Bóna, 2011, с. 180.

[FOOTNOTELucas18913-4] Lucas, 1891, с. 3.

[FOOTNOTEPisano2002404—5-5] Pisano, 2002, с. 404—5.

[1]

[2]

[3]

[4]

[5]