Линейная рекуррентная последовательность

Линейной рекуррентной последовательностью (возвратной последовательностью, линейной рекуррентой) называется всякая числовая последовательность , задаваемая линейным рекуррентным соотношением:

для всех

с заданными начальными членами , где — фиксированное натуральное число, называемое порядком последовательности, — заданные числовые коэффициенты, .

Примеры известных линейных рекуррентных последовательностей можно посмотреть под калькулятором.

Линейная рекуррентная последовательность

Числовые коэффициенты

Размер последовательности для расчета

Начальные члены

x₀

x₁

x₂

x₃

x₄

Рассчитать

Формула

 

Файл очень большой, при загрузке и создании может наблюдаться торможение браузера.

Загрузить 

Точность вычисления

Знаков после запятой: 2

 Ссылка  Сохранить  Виджет

Примеры линейных рекуррентных последовательностей

Начнем с того, что такие известные понятия, как арифметическая прогрессия и геометрическая прогрессия, можно описать как линейные рекуррентные последовательности.

Арифметическую прогрессию с первым членом a₁ и разностью прогрессии d можно представить как линейное рекуррентное соотношение второго порядка следующего вида:

с x₁ = a₁ и x₂ = a₁+d соответственно. Вот так это выглядит для a₁ = 1 и d = 2.

Геометрическую прогрессию с первым членом a₁ и знаменателем прогрессии q можно представить как линейное рекуррентное соотношение первого порядка вида:

c x₁ = a₁. Вот как это выглядит для геометрической прогрессии со знаменателем 2.

Одной из самых известных линейных рекуррентных последовательностей являются числа Фибоначчи - это последовательность, в которой первые два числа равны 0 и 1, а каждое последующее число равно сумме двух предыдущих чисел. Соотношение двух последовательных чисел Фибоначчи дает, между прочим, приближение золотого сечения.

Числа Фибоначчи относятся к последовательностям Люка - семейству пар линейных рекуррентных последовательностей второго порядка, впервые рассмотренных Эдуардом Люка. К ним же относятся и числа Люка - последовательность, в которой, как и в числах Фибоначчи, каждое последующее число равно сумме двух предыдущих чисел, но с первыми членами 2 и 1 соответственно. Числа Люка могут использоваться для проверки на простоту.

Еще две примечательные последовательности Люка это числа Пелля, с формулой

и начальными членами 0 и 1, и числа Пелля-Люка или сопутствующие числа Пелля, с той же формулой и начальными членами 2 и 2. Примечательны эти числа тем, что с их помощью можно построить бесконечную последовательность подходящих дробей для квадратного корня из двух:

Здесь в числителе половина числа Пелля-Люка (2, 6, 14, 34, ...), а в знаменателе - число Пелля (1, 2, 5, 12, ...), начиная со второго числа в последовательности (n=1). Помимо этого соотношение двух последовательных чисел Пелля дает приближение так называемого серебрянного сечения.

И наконец числа трибоначчи, параметры калькулятора по умолчанию, это последовательность целых чисел, где каждое последующее число является суммой трех предыдущих, с начальными членами 0, 0, и 1. Название образовано по аналогии с "Фибоначчи" с заменой на приставку "три", от латинского tri.