В математике , A постоянной рекурсивной последовательности или С-конечная последовательность представляет собой последовательность , удовлетворяющая линейному повторения с постоянными коэффициентами.
Определение
Однородная линейная рекуррентность порядка d с постоянными коэффициентами - это уравнение вида
где коэффициенты d - константы.
Последовательность является константно-рекурсивной последовательностью, если существует однородная линейная рекуррентность порядка d с постоянными коэффициентами, которым она удовлетворяет для всех .
Эквивалентно, является константно-рекурсивным, если набор последовательностей
содержится в векторном пространстве конечной размерности.
Примеры
Последовательность Фибоначчи
Последовательность 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ... чисел Фибоначчи удовлетворяет рекуррентности
с начальными условиями
Явно повторение дает значения
и т.п.
Последовательности Лукаса
Последовательность 2, 1, 3, 4, 7, 11, 18, 29, 47, 76, 123, 199, ... (последовательность A000032 в OEIS ) чисел Люка удовлетворяет той же повторяемости, что и последовательность Фибоначчи, но с начальным условия
В более общем смысле каждая последовательность Лукаса является константно-рекурсивной последовательностью.
Геометрические последовательности
Геометрическая последовательность является постоянной рекурсией, так как она удовлетворяет повторения для всех .
В конечном итоге периодические последовательности
Последовательность, которая в конечном итоге является периодической с длиной периода, является константно-рекурсивной, поскольку она удовлетворяет для всех для некоторых .
Полиномиальные последовательности
Для любого многочлена s ( n ) последовательность его значений является константно-рекурсивной последовательностью. Если степень полинома равна d , последовательность удовлетворяет рекуррентности порядка с коэффициентами, заданными соответствующим элементом биномиального преобразования . Первые несколько таких уравнений:
-
для полинома степени 0 (т. е. постоянного),
-
для полинома степени 1 или меньше,
-
для полинома степени 2 или меньше, и
-
для полинома степени 3 или меньше.
Последовательность, подчиняющаяся уравнению порядка d, также подчиняется всем уравнениям более высокого порядка. Эти тождества можно доказать разными способами, в том числе с помощью теории конечных разностей . Каждое отдельное уравнение может быть также проверена путем замены градусов- д многочлена
где коэффициенты являются символическими. Любая последовательность целых, действительных или комплексных значений может использоваться в качестве начальных условий для константно-рекурсивной последовательности порядка . Если начальные условия лежат на полиноме степени или меньше, то постоянно-рекурсивная последовательность также подчиняется уравнению более низкого порядка.
Перечисление слов на обычном языке
Позвольте быть регулярным языком , и пусть будет количество слов длины в . Тогда является константно-рекурсивным.
Другие примеры
Последовательности чисел Якобсталь , PADOVAN чисел и числа Пеллы являются постоянной рекурсией.
Характеризация в терминах экспоненциальных многочленов
Характеристический полином (или «вспомогательный многочлен») от рецидива многочлен
коэффициенты которого совпадают с коэффициентами рекуррентности. П - й член постоянной рекурсией последовательности можно записать в терминах корней ее характеристического полинома. Если все d корней различны, то n- й член последовательности равен
где коэффициенты k i - константы, которые можно определить из начальных условий.
Для последовательности Фибоначчи характеристический многочлен имеет вид , корни и фигурируют в формуле Бине
В более общем случае, если корень r характеристического многочлена имеет кратность m , то этот член умножается на многочлен степени от n . То есть, пусть будут различные корни характеристического многочлена. потом
где - многочлен степени . Например, если характеристический полином множителей as , с одним и тем же корнем r, встречающимся три раза, то n- й член имеет вид
Наоборот, если существуют такие многочлены , что
то является константно-рекурсивным.
Характеристика в терминах рациональных производящих функций
Последовательность является константно-рекурсивной именно тогда, когда ее производящая функция
является рациональной функцией . Знаменатель - это многочлен, полученный из вспомогательного многочлена путем изменения порядка коэффициентов на обратный, а числитель определяется начальными значениями последовательности.
Производящая функция последовательности Фибоначчи:
В общем, умножая производящую функцию на многочлен
дает серию
где
Если удовлетворяет рекуррентному соотношению
потом для всех . Другими словами,
так что мы получаем рациональную функцию
В частном случае периодической последовательности, удовлетворяющей для , производящая функция равна
за счет расширения геометрического ряда.
Производящая функция чисел каталонских не является рациональной функция, которая предполагает , что число Каталонского не удовлетворяет линейные рецидивы с постоянными коэффициентами.
Свойства закрытия
Почленное сложение или умножение двух константно-рекурсивных последовательностей снова константно-рекурсивное. Это следует из характеризации в терминах экспоненциальных многочленов.
Произведение Коши двух константно-рекурсивных последовательностей константно-рекурсивно. Это следует из характеризации в терминах рациональных производящих функций.
Последовательности, удовлетворяющие неоднородным повторениям
Последовательность, удовлетворяющая неоднородной линейной рекурсии с постоянными коэффициентами, является константно-рекурсивной.
Это потому, что повторение
можно решить для получения
Подставляя это в уравнение
показывает, что удовлетворяет однородной рекуррентности
порядка .
Обобщения
Естественное обобщение получается, если ослабить условие постоянства коэффициентов рекуррентности. Если коэффициенты могут быть полиномами, то получается голономная последовательность .
A -регулярной последовательность удовлетворяет линейные рецидивы с постоянными коэффициентами, но рецидивы принимать различные формы. Вместо того, чтобы быть линейной комбинацией некоторых целых чисел , которые близки к , каждый член в -регулярной последовательности является линейной комбинацией некоторых целых чисел , базовые представления которых близки к . Постоянная рекурсией последовательность можно рассматривать как -регулярные последовательности, где представление базового 1 из состоит из копий цифры .
Заметки
Рекомендации
Смотрите также
Внешние ссылки
-
"Индекс OEIS Rec" . Индекс OEIS на несколько тысяч примеров линейных повторений, отсортированных по порядку (количеству терминов) и сигнатуре (вектор значений постоянных коэффициентов)