Свойства

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

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

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

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

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

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

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

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

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 может быть построен путём добавления 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).

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

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

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

Пример

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

Свойства

Доказательство. Заметим, что треугольник на плоскости с вершинами , и не может содержать целых точек, отличных от вершин. Иначе, если целая точка содержится в , то дробь 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.

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