Лучшие вопросы
Таймлайн
Чат
Перспективы

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

числовая последовательность, задаваемая однородным линейным рекуррентным соотношением с постоянными коэффициентами Из Википедии, свободной энциклопедии

Remove ads

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

для всех

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

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

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

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

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

Remove ads

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

Суммиров вкратце
Перспектива

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

,

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

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

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

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

.

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

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

и .

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

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

и .

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

; ,

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

.

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

.
Remove ads

Примечания

Литература

Loading related searches...

Wikiwand - on

Seamless Wikipedia browsing. On steroids.

Remove ads