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

Линейной рекуррентной последовательностью (линейнойрекуррентой) называется всякая числовая последовательность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). Позднее Пафнутий Львович Чебышёв иещё позже Александр Александрович Марков изложили эту теорию в своихкурсах исчисления конечных разностей.

Смотритакже



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