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

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

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

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

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

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

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

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

${\displaystyle 1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;}$

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

${\displaystyle 0,\;1,\;1,\;2,\;3,\;5,\;8,\;13,\;21,\;34,\;55,\;89,\;144,\;\ldots \;}$.

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

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

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

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

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

або^[4]

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

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

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

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

Формула Біне

Числа Фібоначчі тісно пов'язані з золотим перетином ${\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). Цей факт, виявлений Дж. Джоунзом, відіграє ключову роль у теоремі Матіясевича (негативному розв'язанні десятої проблеми Гільберта), тому що він надає спосіб задати експоненціально зростаючу послідовність чисел Фібоначчі у вигляді діофантової множини^[en].

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

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

${\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, …

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

Див. також

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

Посилання

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

Примітки

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.
2. Beck та Geoghegan, 2010.
3. Bóna, 2011, с. 180.
4. Lucas, 1891, с. 3.
5. Pisano, 2002, с. 404—5.

Література

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

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