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

Линейной рекуррентной последовательностью (линейной рекуррентой) называется всякая числовая последовательность [math]\displaystyle{ x_0,x_1,\dots }[/math], задаваемая линейным рекуррентным соотношением:

[math]\displaystyle{ x_n= a_1\cdot x_{n-1}+\dots+a_d\cdot x_{n-d} }[/math] для всех [math]\displaystyle{ n\geqslant d }[/math]

с заданными начальными членами [math]\displaystyle{ x_0,\dots,x_{d-1} }[/math], где d — фиксированное натуральное число, [math]\displaystyle{ a_1,\dots,a_d }[/math] — заданные числовые коэффициенты, [math]\displaystyle{ a_d\ne 0 }[/math]. При этом число d называется порядком последовательности.

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

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

Примеры

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

• последовательности Люка, удовлетворяющие [math]\displaystyle{ x_n= P\cdot x_{n-1} - Q\cdot x_{n-2} }[/math], в частности:
  • арифметические прогрессии с [math]\displaystyle{ (P,Q) = (2,1) }[/math];
  • геометрическая прогрессия с [math]\displaystyle{ Q=0 }[/math];
  • числа Фибоначчи с [math]\displaystyle{ (P,Q) = (1,-1) }[/math];
  • числа Люка с [math]\displaystyle{ (P,Q) = (1,-1) }[/math];
• числа трибоначчи, удовлетворяющие [math]\displaystyle{ x_n= x_{n-1} + x_{n-2} + x_{n-3} }[/math].

См. также: Обобщённые числа Фибоначчи

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

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

[math]\displaystyle{ \lambda^d-a_1 \lambda^{d-1}-\dots-a_{d-1}\lambda - a_d. }[/math]

А именно, общий член выражается в виде линейной комбинации [math]\displaystyle{ d }[/math] последовательностей вида

[math]\displaystyle{ x_n=\lambda_k^n\cdot n^m, }[/math]

где [math]\displaystyle{ \lambda_k }[/math] — корень характеристического многочлена и [math]\displaystyle{ m }[/math] — целое неотрицательное число меньшее, чем кратность [math]\displaystyle{ \lambda_k }[/math].

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

Пример

Для нахождения формулы общего члена последовательности [math]\displaystyle{ F_n }[/math], удовлетворяющей линейному рекуррентному уравнению второго порядка [math]\displaystyle{ F_n=b\cdot F_{n-1}+c\cdot F_{n-2} }[/math] с начальными значениями [math]\displaystyle{ F_1 }[/math], [math]\displaystyle{ F_2 }[/math], следует решить характеристическое уравнение

[math]\displaystyle{ q^2-bq-c=0 }[/math].

Если уравнение имеет два различных корня [math]\displaystyle{ q_1 }[/math] и [math]\displaystyle{ q_2 }[/math], отличных от нуля, то для произвольных постоянных [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], последовательность

[math]\displaystyle{ F_n=A\cdot q_1^n+ B\cdot q_2^n, }[/math]

удовлетворяет рекурентному соотношению; остаётся найти числа [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], что

[math]\displaystyle{ F_1=A\cdot q_1+ B\cdot q_2 }[/math] и [math]\displaystyle{ F_2=A\cdot q_1^2+ B\cdot q_2^2 }[/math].

Если же дискриминант характеристического уравнения равен нулю и значит уравнение имеет единственный корень [math]\displaystyle{ q_1 }[/math], то для произвольных постоянных [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], последовательность

[math]\displaystyle{ F_n=(A+B\cdot n)\cdot q_1^{n} }[/math]

удовлетворяет рекурентному соотношению; остаётся найти числа [math]\displaystyle{ A }[/math] и [math]\displaystyle{ B }[/math], что

[math]\displaystyle{ F_1=(A+B)\cdot q_1 }[/math] и [math]\displaystyle{ F_2=(A+B\cdot 2)\cdot q_1^{2} }[/math].

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

[math]\displaystyle{ F_n=5\cdot F_{n-1}-6\cdot F_{n-2} }[/math]; [math]\displaystyle{ F_1=1 }[/math], [math]\displaystyle{ F_2=-2 }[/math].

корнями характеристического уравнения [math]\displaystyle{ q^2-5\cdot q+6=0 }[/math] являются [math]\displaystyle{ q_1=2 }[/math], [math]\displaystyle{ q_2=3 }[/math]. Поэтому

[math]\displaystyle{ F_n=-2\cdot (3^{n-1}-2^{n-1})-6\cdot (3^{n-2}-2^{n-2}). }[/math].

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

[math]\displaystyle{ F_n=5\cdot 2^{n-1}-4\cdot 3^{n-1}. }[/math]

Приложения

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

История

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

См. также

• Разностное уравнение
• Теорема Скулема

Литература

• А. И. Маркушевич. Возвратные последовательности. — Гос. Издательство Технико-Теоретической Литературы, 1950. — Т. 1. — (Популярные лекции по математике).
• М. М. Глухов, В. П. Елизаров, А. А. Нечаев. Глава XXV. Линейные рекуррентные последовательности // Алгебра. — Учебник. В 2-x томах. — М.: Гелиос АРВ, 2003. — Т. 2. — ISBN 8-85438-072-2.
• А. Егоров. Числа Пизо // Квант. — 2005. — № 5. — С. 8—13.
• Чебраков Ю. В. Глава 2.7. Рекуррентные уравнения // Теория магических матриц. Выпуск ТММ-1. — СПб., 2010.