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

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

для всех

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

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

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

Примеры

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

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

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

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

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

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

Пример

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

.

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

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

и .

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

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

и .

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

; , .

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

.

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

Приложения

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

История

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

См. также

Примечания

  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 .
  • Чебраков Ю. В. // . — СПб. , 2010.
Источник —

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