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

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

1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 … (последовательность 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
Fn	-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 есть ближайшее к целое число, то есть . В частности, справедлива асимптотика.

Тождества

• 

• 

• 

• 

• 

• 

• 

• Числа Фибоначчи представляются значениями континуант на наборе единиц: , то есть

, а также ,

где матрицы имеют размер , i — мнимая единица.

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

• Для любого n,

·         Следствие. Подсчёт определителей даёт

Свойства

• Наибольший общий делитель двух чисел Фибоначчи равен числу Фибоначчи с индексом, равным наибольшему общему делителю индексов, т. е. (F_m,F_n) = F_(m,n). Следствия:
  • F_m делится на F_n тогда и только тогда, когда m делится на n (за исключением n = 2). В частности, F_m делится на F₃ = 2 (то есть является чётным) только для m = 3k; F_m делится на F₄ = 3 только для m = 4k; F_m делится на F₅ = 5 только для m = 5k и т. д.
  • F_m может быть простым только для простых m (с единственным исключением m = 4) (например, число 233 простое, и индекс его, равный 13, также прост). Обратное не верно, первый контрпример — . Неизвестно, бесконечно ли множество чисел Фибоначчи, являющихся простыми.

• Последовательность чисел Фибоначчи является частным случаем возвратной последовательности, её характеристический многочлен x² - x - 1имеет корни и .

• Отношения являются подходящими дробями золотого сечения φ и, в частности, .
• Суммы биномиальных коэффициентов на диагоналях треугольника Паскаля являются числами Фибоначчи ввиду формулы

.

• В 1964 Дж. Кон (J. H. E. Cohn) доказал, что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12: F₀ = 0² = 0, F₁ = 1² = 1, F₂ = 1² = 1, F₁₂ = 12² = 144. При этом для n=0,1,12 верно утверждение F_n = n².

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

• Множество чисел Фибоначчи совпадает с множеством положительных значений многочлена
  z(x,y) = 2xy⁴ + x²y³ − 2x³y² − y⁵ − x⁴y + 2y,
  на множестве неотрицательных целых чисел x и y.

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

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

Вариации и обобщения

• Числа трибоначчи
• Числа Фибоначчи являются частным случаем последовательностей Люка , при этом их дополнением являются числа Люка .