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

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

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

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

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

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

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

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

${\displaystyle 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}}}$, а також ${\displaystyle \ 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}}}$,

де матриці мають розмір ${\displaystyle n\times n}$, ${\displaystyle i}$ — уявна одиниця.

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

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

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

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

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

Доведення. Позначимо ${\displaystyle \lim _{n\to \infty }{\frac {F_{n+1}}{F_{n}}}=x.}$ Враховуючи, що ${\displaystyle F_{n+1}=F_{n}+F_{n-1},}$ і вважаючи, що шукана границя існує і не дорівнює нулю, запишемо:

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

Отримуємо просте рівняння ${\displaystyle x=1+{\frac {1}{x}},}$ яке зводиться до квадратного рівняння ${\displaystyle x^{2}-x-1=0.}$

Розв'язками є числа ${\displaystyle x_{1}={\frac {1+{\sqrt {5}}}{2}}}$ і ${\displaystyle x_{2}={\frac {1-{\sqrt {5}}}{2}}.}$

Очевидно, що розв'язок ${\displaystyle x_{2}<0}$ не підходить, тому остаточно:

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

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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 позначити матрицю

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

то отримаємо

${\displaystyle {\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-го місяця, то має місце таке рекурентне співвідношення:

${\displaystyle 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(англ.)— приклади програм обчислення чисел Фібоначчі.

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