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

Перейти к навигацииПерейти к поиску

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

для всех

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

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

Частными случаями линейных рекуррентных последовательностей являются последовательности Люка , в частности арифметические прогрессии (), геометрические прогрессии (, где ), числа Фибоначчи (), числа Люка (); числа трибоначчи, удовлетворяющие и ряд других обобщений чисел Фибоначчи.

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

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

Характеристический многочлен

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

,

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

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

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

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

.

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

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

и .

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

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

и .

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

; ,

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

.

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

.

Примечания

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

Литература

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