Числа Фибоначчи

Числа Фибоначчи — последовательность целых чисел \left\{F_n\right\}, заданная с помощью рекуррентного соотношения

F_0 = 0,\quad F_1 = 1,\quad F_{n+1} = F_n + F_{n-1}.

Последовательность чисел Фибоначчи начинается так:

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

Содержание

Формула Бине

Формула Бине выражает в явном виде значение 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}}.

Свойства

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}
  • Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен x2 - x - 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.
  • Множество чисел Фибоначчи совпадает с множеством решений уравнения в натуральных числах относительно x
z = 2xy4 + x2y3 − 2x3y2y5x4y + 2y
в натуральных числах, см. P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, стр. 153

См. также

Литература

Ссылки

 
Начальная страница  » 
А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Щ Ы Э Ю Я
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
0 1 2 3 4 5 6 7 8 9 Home