Свойства

• Всякая последовательность является своей подпоследовательностью.

• Для всякой подпоследовательности верно, что .

• Подпоследовательность сходящейся последовательности сходится к тому же пределу, что и исходная последовательность.

• Если все подпоследовательности некоторой исходной последовательности сходятся, то их пределы равны.

• Любая подпоследовательность бесконечно большой последовательности также является бесконечно большой.

• Из любой неограниченной числовой последовательности можно выделить бесконечно большую подпоследовательность, все элементы которой имеют определённый знак.

• Из любой числовой последовательности можно выделить либо сходящуюся подпоследовательность, либо бесконечно большую подпоследовательность, все элементы которой имеют определённый знак.

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

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181, 6765, 10946, … (последовательность A000045 вOEIS)

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

Более формально, последовательность чисел Фибоначчи задается линейным рекуррентным соотношением:

Иногда числа Фибоначчи рассматривают и для отрицательных номеров n как двусторонне бесконечную последовательность, удовлетворяющую тому же рекуррентному соотношению. При этом члены с отрицательными индексами легко получить с помощью эквивалентной формулы «назад»: F_n = F_{n + 2} − F_{n + 1}:

n

−10

−9

−8

−7

−6

−5

−4

−3

−2

−1

Fn

−55

−21

−8

−3

−1

Легко заметить, что .

Происхождение

Последовательность Фибоначчи была хорошо известна в древней Индии, где она применялась в метрических науках (просодии, другими словами — стихосложении), намного раньше, чем она стала известна в Европе.

Образец длиной n может быть построен путём добавления S к образцу длиной n -1, либо L к образцу длиной n -2; и просодицисты показали, что число образцов длиною n является суммой двух предыдущих чисел в последовательности. Дональд Кнутрассматривает этот эффект в книге «Искусство программирования».

На Западе эта последовательность была исследована Леонардо Пизанским, известным как Фибоначчи, в его труде «Liber Abaci» (1202). Он рассматривает развитие идеализированной (биологически нереальной) популяции кроликов, предполагая что:

• В «нулевом» месяце имеется пара кроликов (1 новая пара).
• В первом месяце первая пара производит на свет другую пару (1 новая пара).
• Во втором месяце обе пары кроликов порождают другие пары и первая пара погибает (2 новые пары).
• В третьем месяце вторая пара и две новые пары порождают в общем три новые пары, а старая вторая пара погибает (3 новые пары).

Закономерным является тот факт, что каждая пара кроликов порождает ещё две пары на протяжении жизни, а затем погибает.

Пусть популяция за месяц n будет равна F (n). В это время только те кролики, которые жили в месяце n -2, являются способными к размножению и производят потомков, тогда F (n -2) пар прибавится к текущей популяции F (n -1). Таким образом общее количество пар будет равно F (n) = F (n -1) + F (n -2).

Формула Бине выражает в явном виде значение F_n как функцию от n:

,

где — золотое сечение. При этом и являются корнями характеристического уравнения .

Из формулы Бине следует, что для всех , F_n есть ближайшее к целое число, то есть . В частности, при справедлива асимптотика .

Формула Бине может быть аналитически продолжена следующим образом:

При этом соотношение F_{z + 2} = F_{z + 1} + F_z выполняется для любого комплексного числа z.

Тождества

• 

• 

• 

• 

• 

• 

• 

• 

• 

И более общие формулы:

• 

• 

• 

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

, а также ,

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

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

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

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

Свойства

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

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

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

.

• В 1964 году Дж. Кон (J. H. E. Cohn) доказал,^[2] что единственными точными квадратами среди чисел Фибоначчи являются числа Фибоначчи с индексами 0, 1, 2, 12:

F ₀ = 0² = 0, F ₁ = 1² = 1, F ₂ = 1² = 1, F ₁₂ = 12² = 144.

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

• Множество чисел Фибоначчи совпадает с множеством неотрицательных значений многочлена

z (x, y) = 2 xy ⁴ + x ² y ³ − 2 x ³ y ² − y ⁵ − x ⁴ y + 2 y,

на множестве неотрицательных целых чисел x и y. ^[3]

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

• Период чисел Фибоначчи по модулю натурального числа n называется периодом Пизано и обозначается π(n). Периоды Пизано π(n) образуют последовательность:

1, 3, 8, 6, 20, 24, 16, 12, 24, 60, 10, 24, 28, 48, 40, 24, 36, … (последовательность A001175 в OEIS)

• В частности, последние цифры чисел Фибоначчи образуют периодическую последовательность с периодом π(10)=60, последняя пара цифр чисел Фибоначчи образует последовательность с периодом π(100)=300, последние три цифры — с периодом π(1000)=1500, последние четыре — с периодом π(10000)=15000, последние пять — с периодом π(100000)=150000 и т. д.

• Натуральное число N является числом Фибоначчи тогда и только тогда, когда 5 N ² + 4 или 5 N ² − 4 является квадратом.^[4]

• Не существует арифметической прогрессии длиной больше 3, состоящей из чисел Фибоначчи.^[5]

Последовательность Фарея n -ного порядка представляет собой возрастающий ряд всех несократимых дробей, знаменатель которых меньше или равен n:

Последовательность Фарея порядка n + 1 можно построить из последовательности порядка n по следующему правилу:

1. Копируем все элементы последовательности порядка n.
2. Если сумма знаменателей в двух соседних дробях последовательности порядка n дает число не большее, чем n + 1, вставляем между этими дробями их медианту, равную отношению суммы их числителей к сумме знаменателей.

Пример

Последовательности Фарея для n от 1 до 8:

Свойства

Если p 1 / q 1 < p 2 / q 2 — две соседние дроби в ряде Фарея, тогда q 1 p 2 − q 2 p 1 = 1.

Доказательство. Заметим, что треугольник на плоскости с вершинами , и не может содержать целых точек, отличных от вершин. Иначе, если целая точка содержится в , то дробь r / s лежит между p ₁ / q ₁ и p ₂ / q ₂, а знаменатель s не превосходит . Значит, по формуле Пика, его площадь равна 1 / 2. С другой стороны, площадь равна (q ₁ p ₂ − q ₂ p ₁) / 2. Ч. т. д.

Справедливо и обратное утверждение: если дроби p ₁ / q ₁ < p ₂ / q ₂ таковы, что q ₁ p ₂ − q ₂ p ₁ = 1, то они представляют собой соседние члены ряда Фарея .

Дели́мость — одно из основных понятий арифметики и теории чисел, связанное с операцией деления. С точки зрения теории множеств, делимость целых чисел является отношением, определённым на множестве целых чисел.

Если для некоторого целого числа a и целого числа b существует такое целое число q, что bq = a, то говорят, что число a делится нацело на b или, что b делит a.

При этом число b называется делителем числа a, делимое a будет кратным числа b, а число q называется частным от деления a на b.

Хотя свойство делимости определено на всём множестве целых чисел, обычно рассматривается лишь делимость натуральных чисел. В частности, функция количества делителей натурального числа подсчитывает лишь его положительные делители.