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

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

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

для всех

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

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

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

Примеры[править | править код]

Частными случаями линейных рекуррентных последовательностей являются последовательности:

Формула общего члена[править | править код]

Для линейных рекуррентных последовательностей существует формула, выражающая общий член последовательности через корни её характеристического многочлена

А именно, общий член выражается в виде линейной комбинации последовательностей вида

где — корень характеристического многочлена и — целое неотрицательное число не превосходящее кратность .

Для чисел Фибоначчи такой формулой является формула Бине.

Пример[править | править код]

Для нахождения формулы общего члена последовательности , удовлетворяющей линейному рекуррентному уравнению второго порядка с начальными значениями , , следует решить характеристическое уравнение

.

Если уравнение имеет два различных корня и , отличных от нуля, то для произвольных постоянных и , последовательность

удовлетворяет рекурентному соотношению; остаётся найти числа и , что

и .

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

удовлетворяет рекурентному соотношению; остаётся найти числа и , что

и .

В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка

; , .

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

.

Окончательно:

Приложения[править | править код]

Линейные рекуррентные последовательности над кольцами вычетов традиционно используются для генерации псевдослучайных чисел.

История[править | править код]

Основы теории линейных рекуррентных последовательностей были даны в двадцатых годах восемнадцатого века Абрахамом де Муавром и Даниилом Бернулли. Леонард Эйлер изложил её в тринадцатой главе своего «Введения в анализ бесконечно-малых» (1748).[1] Позднее Пафнутий Львович Чебышёв и ещё позже Александр Александрович Марков изложили эту теорию в своих курсах исчисления конечных разностей.[2][3]

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

Примечания[править | править код]

  1. Л. Эйлер, Введение в анализ бесконечно-малых, т. I, M. — Л., 1936, стр. 197–218
  2. П. Л.Чебышев, Теория вероятностей, лекции 1879–1880 гг., М. — Л., 1936, стр. 139–147
  3. А. А. Марков, Исчисление конечных разностей, 2-е изд., Одесса, 1910, стр. 209–239

Литература[править | править код]