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

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

xn=a1xn1++adxnd для всех nd
  с заданными начальными членами x0,,xd1, где d — фиксированное натуральное число, a1,,ad — заданные числовые коэффициенты, ad0. При этом число d называется порядком последовательности.
 Линейные рекуррентные последовательности иногда называют также возвратными последовательностями.
 Теория линейных рекуррентных последовательностей является точным аналогом теории линейных дифференциальных уравнений с постоянными коэффициентами.

Примеры


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

  • арифметическая прогрессия
  • геометрическая прогрессия
  • числа Фибоначчи
  • числа Люка
  • числа трибоначчи
  • последовательности Люка

Формула общего члена


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

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

xn=λknnm,
  где λk — корень характеристического многочлена и m — целое неотрицательное число не превосходящее кратность λk.
 Для чисел Фибоначчи такой формулой является формула Бине.

Пример


 Для нахождения формулы общего члена последовательности Fn, удовлетворяющей линейному рекуррентному уравнению второго порядка Fn=bFn1+cFn2 с начальными значениями F1, F2, следуе решить характеристическое уравнение
q2bqc=0
. Если уравнение имеет два различных корня q1 и q2, отличных от нуля, то для произвольных постоянных A и B, последовательность

Fn=Aq1n+Bq2n,
  удовлетворяет рекурентному соотношению; остаётся найти числа A и B, что

F1=Aq1+Bq2 и F2=Aq12+Bq22.
  Если же дискриминант характеристического уравнения равен нулю и значит уравнение имеет единственный корень q1, то для произвольных постоянных A и B, последовательность

Fn=(A+Bn)q1n
  удовлетворяет рекурентному соотношению; остаётся найти числа A и B, что

F1=(A+B)q1 и F2=(A+B2)q12.
  В частности, для последовательности, определяемой следующим линейным рекуррентным уравнением второго порядка

Fn=5Fn16Fn2; F1=1, F2=2.
  корнями характеристического уравнения q25q+6=0 являются q1=2, q2=3. Поэтому

Fn=2(3n12n1)6(3n22n2)..
  Окончательно:

Fn=52n143n1.

Приложения


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

История


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

Смотри также



  • Разностное уравнение