Постоянно-рекурсивная последовательность - Constant-recursive sequence

В математике , 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 на несколько тысяч примеров линейных повторений, отсортированных по порядку (количеству терминов) и сигнатуре (вектор значений постоянных коэффициентов)