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

Материал из Википедии — свободной энциклопедии

Текущая версия (не проверялась)

Чи́сла Фибона́ччи — элементы числовой последовательности

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 …

в которой каждое последующее число равно сумме двух предыдущих чисел. Название по имени средневекового математика Леонардо Пизанского (или Фибоначчи) ^[1].

Более формально, последовательность чисел Фибоначчи $\left\{F_n\right\}$ задается рекуррентным соотношением:

$F_1 = 1,\quad F_2 = 1,\quad F_{n+1} = F_n + F_{n-1}, \quad n\in\mathbb{N}$ (последовательность A000045 в OEIS).

Иногда числа Фибоначчи рассматривают и для неположительных номеров $n$ как двусторонне бесконечную последовательность, удовлетворяющую основному соотношению. Члены с такими номерами легко получить с помощью эквивалентной формулы «назад»: $F n = F n + 2 - F n + 1$ :

n	-10	-9	-8	-7	-6	-5	-4	-3	-2	-1	0	1	2	3	4	5	6	7	8	9	10
$F n$	-55	34	-21	13	-8	5	-3	2	-1	1	0	1	1	2	3	5	8	13	21	34	55

Легко видеть, что $F - n = ( - 1) n + 1 F n$ . Для чисел Фибоначчи с отрицательными индексами остаются верными большинство нижеприведённых свойств (но не все!).

[править] Формула Бине

Формула Бине выражает в явном виде значение $F n$ как функцию от $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$ , $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}}$ .

[править] Тождества

$F_1+F_2+F_3+\dots+F_n=F_{n+2}-1$

$F_1+F_3+F_5+\dots+F_{2n-1}=F_{2n}$

$F_2+F_4+F_6+\dots+F_{2n}=F_{2n+1}-1$

$F_{n+m}^{}=F_{n-1}F_{m}+F_{n}F_{m+1}$

$F_{n+1}F_{n+2}^{}-F_nF_{n+3}=(-1)^{n+1}$

$F_1^2+F_2^2+F_3^2+\dots+F_{n}^2=F_nF_{n+1}$

$F_n^2+F_{n+1}^2=F_{2n+1}$

Числа Фибоначчи представляются значениями континуант на наборе единиц: $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

— мнимая единица.

Числа Фибоначчи можно выразить через многочлены Чебышёва:

$F_{n+1} = (-i)^n U_n\left(\frac{-i}{2}\right) = (-i)^n T_n(-i)$

$F_{2n+2} = U_n\left(\frac{3}{2}\right) = T_n(3)$

Для любого 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_m,F_n) = F_(m,n). Следствия:
- $F m$ делится на $F n$ тогда и только тогда, когда $m$ делится на $n$ (за исключением $n = 2$ ). В частности, $F m$ делится на $F 3 = 2$ (то есть является чётным) только для $m = 3 k$ ; $F m$ делится на $F 4 = 3$ только для $m = 4 k$ ; $F m$ делится на $F 5 = 5$ только для $m = 5 k$ и т. д.
- $F m$ может быть простым только для простых $m$ (с единственным исключением $m = 4$ ) (например, число 233 простое, и индекс его, равный 13, также прост). Обратное не верно, первый контрпример — $F_{19}=4181=37\cdot 113$ . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.

Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен $x 2 - x - 1$ имеет корни $~\phi$ и $-\frac{1}{\phi}$ .

Отношения $\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 доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12: $F 0 = 0 2 = 0$ , $F 1 = 1 2 = 1$ , $F 2 = 1 2 = 1$ , $F 12 = 12 2 = 144$ . При этом для n=0,1,12 верно утверждение $F n = n 2$ .

Производящей функцией последовательности чисел Фибоначчи является:

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

Множество чисел Фибоначчи совпадает с множеством положительных значений многочлена
$z (x, y) = 2 x y 4 + x 2 y 3 - 2 x 3 y 2 - y 5 - x 4 y + 2 y$ ,
на множестве неотрицательных целых чисел $x$ и $y$ ^[2].

Произведение и частное двух любых различных чисел Фибоначчи, отличных от единицы, никогда не является числом Фибоначчи.

Последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом 60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом 300, последние три цифры — с периодом 1500, последние четыре — с периодом 15000, последние пять — с периодом 150000 и т.д.

[править] См. также

[править] Литература

Н. Н. Воробьёв Числа Фибоначчи. — Наука, 1978. — Т. 39. — (Популярные лекции по математике).
А. И. Маркушевич Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
А. Н. Рудаков Числа Фибоначчи и простота числа 2¹²⁷-1 // Математическое Просвещение, третья серия. — 2000. — Т. 4.
Дональд Кнут Искусство программирования, том 1. Основные алгоритмы = The Art of Computer Programming, vol.1. Fundamental Algorithms. — 3-е изд. — М.: «Вильямс», 2006. — С. 720. — ISBN 0-201-89683-4
Дональд Кнут, Роналд Грэхем, Орен Паташник Конкретная математика. Основание информатики = Concrete Mathematics. A Foundation for Computer Science. — М.: Мир; Бином. Лаборатория знаний, 2006. — С. 703. — ISBN 5-94774-560-7

[править] Ссылки

[править] Примечания

↑ БСЭ
↑ P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 193.

[0] БСЭ

[1] P. Ribenboim, The New Book of Prime Number Records, Springer, 1996, p. 193.

[1]

[2]

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

Материал из Википедии — свободной энциклопедии

Содержание

[править] Формула Бине

[править] Тождества

[править] Свойства

[править] См. также

[править] Литература

[править] Ссылки

[править] Примечания

Просмотры

Личные инструменты

Навигация

Поиск

Участие

Инструменты

На других языках