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

Матеріал з Вікіпедії — вільної енциклопедії.

Зображення, яке ілюструє послідовність Ф.

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

$F_1=1, F_2=1, F_{n+2}=F_{n}+F_{n+1}, k=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/3 повного оберту в ліщини, 2/5 - у дуба, 3/8 - у тополі і груші, 5/13 - у верби; лусочки на ялиновій шишці, насіння соняшника розташовані спіралями, причому кількості спіралей кожного напрямку також, як правило, числа Фібоначчі.

[ред.] Формула Біне

Числа Фібоначчі щільно пов'язані з золотим перетином $\phi=\frac{1 + \sqrt{5}}{2}.$ Формула Біне виражає за допомогою $φ$ значення $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\geq 1).$

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

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

[ред.] Властивості чисел Фібоначчі

Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом рівним найбільшому спільному дільнику індексів, тобто: . В наслідок цього:
- $F m$ ділиться $F n$ тоді й тільки тоді, коли $m$ ділиться на $n$ (за виключенням $n = 2$ );
- кожне третє число Фібоначчі парне ( $F 3 = 2, F 6 = 8, F 9 = 34$ );
- кожне четверте ділиться на три ( $F 4 = 3, F 8 = 21, F 1 2 = 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$ й має корені $φ$ і $- 1 / φ$ .
Генератрисою послідовності чисел Фібоначчі є:

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

Числа Фібоначчі можна представити значеннями континуант на наборі одиниць: $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}$ є підходящими дробами золотого перетину $φ$ і, зокрема, $\lim_{n\to\infty}\frac{F_{n+1}}{F_n}=\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) = 2 x y 4 + x 2 y 3 - 2 x 3 y 2 - y 5 - x 4 y + 2 y,

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

[ред.] Історія відкриття

У XIII столітті італійський математик Фібоначчі розв’язував таку задачу:

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

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

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

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

F_n = F_n-1 + F_n-2, F₁ = F₂ = 1

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, ... , У 1225 році государ Римської імперії Фрідріг II на турнірі в Пізі запропонував Леонардо Фібоначчі таку задачу: Знайти повний квадрат, який залишаеться повним квадратом як після збільшення, так і після зменшення його на 5. Фібоначчі після деяких розміркувань знайшов це число. Воно виявилося дробовим: 1681/144, або (41/12)². Справді, 1681/144-5=961/144, 1681/144+5=2401/144. інакше (41/12)²-5=(31/12)² і (41/12)²+5=(49/12)². Якими міркуваннями керувався Фібоначчі під час турніру, ми ніколи не з'ясуемо, але задачу він розв'язав блискуче.