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

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

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

Послідо́вність Фібона́ччі, чи́сла Фібона́ччі - числова послідовність {Fn}, задана рекурентним співвідношенням другого порядку F0=0; F1=1; Fk=Fk-1+Fk, k=2,3,... (для кожного натурального k > 1). 0, 1, 1, 2, 3, 5, 8, 13, і т.п. Ця послідовність виникає у самих різних математичних ситуаціях - комбінаторних, числових, геометричних.

Іноді числа Фібоначчі розглядають і для від'ємних індексів:

F_{-1} = 1, F_{-2} = -1, F_{-3} = 2 \dots\;, F_{n-1} = F_{n+1}-F_n

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

Зміст

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

Формула Біне виражає в явному вигляді значення Fn як функцію від n:

F_n = \frac{\left(\frac{1 + \sqrt{5}}{2}\right)^n - \left(\frac{1 - \sqrt{5}}{2}\right)^n}{\sqrt{5}} = \frac{\phi^n - (-\phi )^{-n}}{\phi - (-\phi )^{-1}},

де \phi=\frac{1 + \sqrt{5}}{2}золотий перетин. При цьому \phi\,\! і (-\phi )^{-1}=1-\phi\,\! є коренями квадратного рівняння x^2-x-1=0\,\!.

З формули Біне випливає, що для всіх n\ge0, Fn є найближчим до \frac{\phi^n}{\sqrt{5}}\, цілим числом, тобто F_n = \left\lfloor\frac{\phi^n}{\sqrt{5}}\right\rceil. Зокрема, справедлива асимптотика F_n\sim \frac{\phi^n}{\sqrt{5}}.

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

  • кожне третє число Фібоначчі парне
  • кожне четверте ділиться на три
  • кожне п'ятнадцяте закінчується нулем
  • два сусідніх числа Фібоначчі взаємно прості
  • Fn ділиться на Fm тоді і тільки тоді, коли n ділиться на m.
  • Генератрисою послідовності чисел Фібоначчі є:
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}
  • Послідовність чисел Фібоначчі є частковим випадком генерованої послідовності, її характеристичний многочлен рівний x2x − 1 й має корені φ і − 1 / φ.
  • Найбільший спільний дільник двох чисел Фібоначчі дорівнює числу Фібоначчі з індексом рівним найбільшому спільному дільнику індексів, тобто: (F_m,F_n) = F_{(m,n)}\,\!. Наслідки:
    • Fm ділиться Fn тоді й тільки тоді, коли m ділиться на n (за виключенням n = 2).
    • Fm може бути простим тільки для простих m (за єдиним виключенням m = 4). Зворотнє невірно, наприклад F_{19}=4181=37\cdot 113. На даний момент невідомо, чи існує безкінечно багато простих чисел Фібоначчі.
  • Числа Фібоначчі можна представити значеннями континуант на наборі одиниць: 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 довів, що єдиними точними квадратами серед чисел Фібоначчі є 0, 1 і 122=144.
z = 2xy4 + x2y3 − 2x3y2y5x4y + 2y
в натуральних числах, см. P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, стор. 153

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

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

[ред.] Теорія чисел Фібоначчі як математична основа теорії хвиль


Зображення:wiki_letter_w.png Цю секцію необхідно дописати чи вдосконалити. Ви можете допомогти проекту, зробивши це!