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

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

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

Спіраль Фібоначчі: апроксимація золотої спіралі утворена круглими дугами, що проведені через протилежні кути квадратів Фібоначчі; в цьому прикладі сторони квадратів були такими: 1, 1, 2, 3, 5, 8, 13, 21, і 34.

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

із початковими значеннями

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

або

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

Суцвіття соняшника з 34 спіралями в один бік і 55 в інший

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

Послідовність названа на честь математика XIII століття Леонардо Фібоначчі з Пізи. Його 1202 книга — Книга абака — представила цю послідовність спільноті західноєвропейських математиків, хоча така послідовність вже була описана раніше як числа Вараханка в індійській математиці. Послідовність, описана в «Книзі абака», починалася з 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}$ тоді й тільки тоді, коли $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). Цей факт, виявлений Дж. Джоунзом, відіграє ключову роль у теоремі Матіясевича (негативному розв'язанні десятої проблеми Гільберта), тому що він надає спосіб задати експоненціально зростаючу послідовність чисел Фібоначчі у вигляді діофантової множини.

Числа Фібоначчі за 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) операцій.

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

Сторінка з Liber abaci Фібоначчі, книга зберігається в Національній центральній бібліотеці Флоренції. В прямокутній рамці справа послідовність Фібоначчі; порядкові номери вказані шрифтом чорного кольору словами латиною, з десятого номера — римськими цифрами, сама послідовність подана червоним кольором арабськими цифрами.

У 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, …

У зростаючій ідеалізованій популяції кількість пар кроликів утворює послідовність Фібоначчі. Наприкінці n-го місяця кількість пар дорівнює F_n.

Див. також

• Куб Фібоначчі
• Період Пізано
• Послідовність Гофстедтера
• Послідовність Люка
• Теорема Цекендорфа
• Числа трибоначчі
• Числа Якобсталя

Посилання

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

Література

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