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

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

для всех

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

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

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

ПримерыПравить

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

Формула общего членаПравить

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

 

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

 

где   — корень характеристического многочлена и   — целое неотрицательное число меньшее, чем кратность  .

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

ПримерПравить

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

 .

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

 

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

  и  .

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

 

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

  и  .

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

 ;  ,  .

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

 .

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

 

ПриложенияПравить

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

ИсторияПравить

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

См. такжеПравить

ПримечанияПравить

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

ЛитератураПравить