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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук
Зображення, яке ілюструє послідовність Ф.

Послідо́вність Фібона́ччі, чи́сла Фібона́ччі — числова послідовність {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, \,

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

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

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

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

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

Числа Фібоначчі за logN[ред.ред. код]

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

F_n = F_(n-1) + F_(n-2)
F_(n+1) = F_n + F_(n-1) = 2*F_(n-1) + F_(n-2)

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

| F_n    |        | 1   1 |   | F_(n-2)|
|        |   =    |       |   |        |
| F_(n+1)|        | 1   2 |   | F_(n-1)|.

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

    | 1   1 |
A = |       |
    | 1   2 |,

то отримаєм

| F_(2n)  |             | 1 |
|         |   =  A^n *  |   |
| F_(2n+1)|             | 1 |.

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

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

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

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

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

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

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

Fn = Fn-1 + Fn-2, F1 = F2 = 1

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

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

Див. також[ред.ред. код]

Посилання[ред.ред. код]

Література[ред.ред. код]

  • Воробьев, Числа Фибоначчи (Популярные лекции по математике, вып. 5). М., Наука.