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

В математике бесконечная последовательность чисел называется константно-рекурсивной, если она удовлетворяет уравнению вида${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }$

$${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}$$

для всех , где константы . Уравнение называется линейным рекуррентным соотношением . Концепция также известна как линейная рекуррентная последовательность , линейно-рекурсивная последовательность , линейно-рекуррентная последовательность или C-конечная последовательность . ^[1]${\displaystyle n\geq d}$${\displaystyle c_{i}}$

Например, последовательность Фибоначчи

${\displaystyle 0,1,1,2,3,5,8,13,\ldots }$,

является константно-рекурсивной, поскольку она удовлетворяет линейному рекурсивному соотношению : каждое число в последовательности является суммой двух предыдущих. ^[2] Другие примеры включают последовательность степени двойки , где каждое число является суммой удвоенного предыдущего числа, и последовательность квадратов чисел . Все арифметические прогрессии , все геометрические прогрессии и все многочлены являются константно-рекурсивными. Однако не все последовательности являются константно-рекурсивными; например, факториальная последовательность не является константно-рекурсивной.${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$${\displaystyle 1,2,4,8,16,\ldots }$${\displaystyle 0,1,4,9,16,25,\ldots }$${\displaystyle 1,1,2,6,24,120,\ldots }$

Константно-рекурсивные последовательности изучаются в комбинаторике и теории конечных разностей . Они также возникают в алгебраической теории чисел из-за связи последовательности с корнями полинома ; в анализе алгоритмов как время выполнения простых рекурсивных функций ; и в теории формальных языков , где они подсчитывают строки до заданной длины в регулярном языке . Константно-рекурсивные последовательности замкнуты относительно важных математических операций, таких как почленное сложение , почленное умножение и произведение Коши .

Теорема Скулема –Малера–Леха утверждает, что нули постоянно-рекурсивной последовательности имеют регулярно повторяющуюся (в конечном итоге периодическую) форму. Задача Скулема , которая требует алгоритма для определения, имеет ли линейная рекуррентность хотя бы один ноль, является нерешенной проблемой в математике .

Константно -рекурсивная последовательность — это любая последовательность целых чисел , рациональных чисел , алгебраических чисел , действительных чисел или комплексных чисел (записанных в сокращенном виде), удовлетворяющая формуле вида${\displaystyle s_{0},s_{1},s_{2},s_{3},\ldots }$${\displaystyle (s_{n})_{n=0}^{\infty }}$

$${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d},}$$

для всех для некоторых фиксированных коэффициентов, находящихся в той же области, что и последовательность (целые числа, рациональные числа, алгебраические числа, действительные числа или комплексные числа). Уравнение называется линейной рекуррентностью с постоянными коэффициентами порядка d . Порядок последовательности — это наименьшее положительное целое число, такое, что последовательность удовлетворяет рекуррентности порядка d , или для последовательности, содержащей всюду ноль. ^{[ необходима цитата ]}${\displaystyle n\geq d,}$ ${\displaystyle c_{1},c_{2},\dots ,c_{d}}$${\displaystyle d}$${\displaystyle d=0}$

Определение выше допускает периодические последовательности, такие как и . Некоторые авторы требуют, чтобы , что исключает такие последовательности. ^{[3] [4] [5]}${\displaystyle 1,0,0,0,\ldots }$${\displaystyle 0,1,0,0,\ldots }$${\displaystyle c_{d}\neq 0}$

Избранные примеры целочисленных константно-рекурсивных последовательностей ^[6]

Имя	Заказ (   )${\displaystyle d}$	Первые несколько значений	Повторение (для  )${\displaystyle n\geq d}$	Производящая функция	ОЭИС
Нулевая последовательность	0	0, 0, 0, 0, 0, 0, ...	${\displaystyle s_{n}=0}$	${\displaystyle {\frac {0}{1}}}$	А000004
Одна последовательность	1	1, 1, 1, 1, 1, 1, ...	${\displaystyle s_{n}=s_{n-1}}$	${\displaystyle {\frac {1}{1-x}}}$	А000012
Характерная функция${\displaystyle \{0\}}$	1	1, 0, 0, 0, 0, 0, ...	${\displaystyle s_{n}=0}$	${\displaystyle {\frac {1}{1}}}$	А000007
Степени двойки	1	1, 2, 4, 8, 16, 32, ...	${\displaystyle s_{n}=2s_{n-1}}$	${\displaystyle {\frac {1}{1-2x}}}$	А000079
Степени числа −1	1	1, -1, 1, -1, 1, -1, ...	${\displaystyle s_{n}=-s_{n-1}}$	${\displaystyle {\frac {1}{1+x}}}$	А033999
Характерная функция${\displaystyle \{1\}}$	2	0, 1, 0, 0, 0, 0, ...	${\displaystyle s_{n}=0}$	${\displaystyle {\frac {x}{1}}}$	А063524
Разложение десятичной дроби на 1/6	2	1, 6, 6, 6, 6, 6, ...	${\displaystyle s_{n}=s_{n-1}}$	${\displaystyle {\frac {1+5x}{1-x}}}$	А020793
Разложение десятичной дроби на 1/11	2	0, 9, 0, 9, 0, 9, ...	${\displaystyle s_{n}=s_{n-2}}$	${\displaystyle {\frac {9x}{1-x^{2}}}}$	А010680
Неотрицательные целые числа	2	0, 1, 2, 3, 4, 5, ...	${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$	${\displaystyle {\frac {x}{(1-x)^{2}}}}$	А001477
Нечетные положительные целые числа	2	1, 3, 5, 7, 9, 11, ...	${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$	${\displaystyle {\frac {1+x}{(1-x)^{2}}}}$	А005408
Числа Фибоначчи	2	0, 1, 1, 2, 3, 5, 8, 13, ...	${\displaystyle s_{n}=s_{n-1}+s_{n-2}}$	${\displaystyle {\frac {x}{1-x-x^{2}}}}$	А000045
числа Лукаса	2	2, 1, 3, 4, 7, 11, 18, 29,...	${\displaystyle s_{n}=s_{n-1}+s_{n-2}}$	${\displaystyle {\frac {2-x}{1-x-x^{2}}}}$	А000032
Числа Пелля	2	0, 1, 2, 5, 12, 29, 70, ...	${\displaystyle s_{n}=2s_{n-1}+s_{n-2}}$	${\displaystyle {\frac {x}{1-2x-x^{2}}}}$	А000129
Степени двойки, чередующиеся с нулями	2	1, 0, 2, 0, 4, 0, 8, 0, ...	${\displaystyle s_{n}=2s_{n-2}}$	${\displaystyle {\frac {1}{1-2x^{2}}}}$	А077957
Обратный 6-й циклотомический полином	2	1, 1, 0, −1, −1, 0, 1, 1, ...	${\displaystyle s_{n}=s_{n-1}-s_{n-2}}$	${\displaystyle {\frac {1}{1-x+x^{2}}}}$	А010892
Треугольные числа	3	0, 1, 3, 6, 10, 15, 21, ...	${\displaystyle s_{n}=3s_{n-1}-3s_{n-2}+s_{n-3}}$	${\displaystyle {\frac {x}{(1-x)^{3}}}}$	А000217

Последовательность 0, 1, 1, 2, 3, 5, 8, 13, ... чисел Фибоначчи является постоянно-рекурсивной порядка 2, поскольку она удовлетворяет рекурсии с . Например, и . Последовательность 2, 1, 3, 4, 7, 11, ... чисел Люка удовлетворяет той же рекурсии, что и последовательность Фибоначчи, но с начальными условиями и . В более общем смысле, каждая последовательность Люка является постоянно-рекурсивной порядка 2. ^[2]${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$${\displaystyle F_{0}=0,F_{1}=1}$${\displaystyle F_{2}=F_{1}+F_{0}=1+0=1}$${\displaystyle F_{6}=F_{5}+F_{4}=5+3=8}$${\displaystyle L_{0}=2}$${\displaystyle L_{1}=1}$

Для любого и любого арифметическая прогрессия является константно-рекурсивной порядка 2, поскольку она удовлетворяет . Обобщая это, см. полиномиальные последовательности ниже. ^{[ необходима цитата ]}${\displaystyle a}$${\displaystyle r\neq 0}$ ${\displaystyle a,a+r,a+2r,\ldots }$${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$

Для любого и геометрическая прогрессия является константно-рекурсивной порядка 1, поскольку она удовлетворяет . Это включает, например, последовательность 1, 2, 4, 8, 16, ..., а также рациональную числовую последовательность . ^{[ необходима цитата ]}${\displaystyle a\neq 0}$${\displaystyle r}$ ${\displaystyle a,ar,ar^{2},\ldots }$${\displaystyle s_{n}=rs_{n-1}}$${\textstyle 1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},...}$

Последовательность, которая в конечном итоге периодична с длиной периода, является постоянно-рекурсивной, поскольку она удовлетворяет для всех , где порядок — это длина начального сегмента, включая первый повторяющийся блок. Примерами таких последовательностей являются 1, 0, 0, 0, ... (порядок 1) и 1, 6, 6, 6, ... (порядок 2). ^{[ необходима цитата ]}${\displaystyle \ell }$${\displaystyle s_{n}=s_{n-\ell }}$${\displaystyle n\geq d}$${\displaystyle d}$

Последовательность, определяемая полиномом, является константно-рекурсивной. Последовательность удовлетворяет рекуррентному соотношению порядка (где — степень полинома), с коэффициентами, заданными соответствующим элементом биномиального преобразования . ^{[7] [8]} Первые несколько таких уравнений:${\displaystyle s_{n}=a_{0}+a_{1}n+a_{2}n^{2}+\cdots +a_{d}n^{d}}$${\displaystyle d+1}$${\displaystyle d}$

${\displaystyle s_{n}=1\cdot s_{n-1}}$для полинома степени 0 (то есть постоянного),

${\displaystyle s_{n}=2\cdot s_{n-1}-1\cdot s_{n-2}}$для полинома степени 1 или ниже,

${\displaystyle s_{n}=3\cdot s_{n-1}-3\cdot s_{n-2}+1\cdot s_{n-3}}$для полинома степени 2 или ниже, и

${\displaystyle s_{n}=4\cdot s_{n-1}-6\cdot s_{n-2}+4\cdot s_{n-3}-1\cdot s_{n-4}}$для полинома степени 3 или ниже.

Последовательность, подчиняющаяся уравнению порядка d , подчиняется также всем уравнениям более высокого порядка. Эти тождества могут быть доказаны несколькими способами, в том числе с помощью теории конечных разностей . ^[9] Любая последовательность целых, действительных или комплексных значений может быть использована в качестве начальных условий для константно-рекурсивной последовательности порядка . Если начальные условия лежат на полиноме степени или меньше, то константно-рекурсивная последовательность также подчиняется уравнению более низкого порядка.${\displaystyle d+1}$${\displaystyle d+1}$${\displaystyle d-1}$

Пусть будет регулярным языком , и пусть будет числом слов длины в . Тогда является константно-рекурсивным. ^[10] Например, для языка всех двоичных строк, для языка всех унарных строк и для языка всех двоичных строк, которые не имеют двух последовательных единиц. В более общем смысле, любая функция, принимаемая взвешенным автоматом над унарным алфавитом над полукольцом (которое на самом деле является кольцом и даже полем ), является константно-рекурсивной. ^{[ необходима цитата ]}${\displaystyle L}$${\displaystyle s_{n}}$${\displaystyle n}$${\displaystyle L}$${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=2^{n}}$${\displaystyle s_{n}=1}$${\displaystyle s_{n}=F_{n+2}}$${\displaystyle \Sigma =\{a\}}$ ${\displaystyle (\mathbb {R} ,+,\times )}$

Последовательности чисел Якобсталя , чисел Падована , чисел Пелля и чисел Перрена ^[2] являются константно-рекурсивными.

Факториальная последовательность не является константно-рекурсивной. В более общем случае каждая константно-рекурсивная функция асимптотически ограничена экспоненциальной функцией (см . #Характеристика замкнутой формы), а факториальная последовательность растет быстрее этой.${\displaystyle 1,1,2,6,24,120,720,\ldots }$

Последовательность Каталана не является константно-рекурсивной. Это происходит потому, что производящая функция чисел Каталана не является рациональной функцией (см. #Эквивалентные определения).${\displaystyle 1,1,2,5,14,42,132,\ldots }$

${\displaystyle F_{n}={\begin{bmatrix}0&1\end{bmatrix}}{\begin{bmatrix}1&1\\1&0\end{bmatrix}}^{n}{\begin{bmatrix}1\\0\end{bmatrix}}.}$

Определение последовательности Фибоначчи с помощью матриц.

Последовательность является константно-рекурсивной порядка меньшего или равного тогда и только тогда, когда ее можно записать в виде${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle d}$

${\displaystyle s_{n}=uA^{n}v}$

где — вектор, — матрица , а — вектор, где элементы берутся из той же области (целые числа, рациональные числа, алгебраические числа, действительные числа или комплексные числа), что и исходная последовательность. В частности, можно принять за первые значения последовательности, линейное преобразование , которое вычисляется из , и вектор . ^[11]${\displaystyle u}$${\displaystyle 1\times d}$${\displaystyle A}$${\displaystyle d\times d}$ ${\displaystyle v}$${\displaystyle d\times 1}$${\displaystyle v}$${\displaystyle d}$${\displaystyle A}$${\displaystyle s_{n+1},s_{n+2},\ldots ,s_{n+d}}$${\displaystyle s_{n},s_{n+1},\ldots ,s_{n+d-1}}$${\displaystyle u}$${\displaystyle [0,0,\ldots ,0,1]}$

Неоднородный	Однородный
${\displaystyle s_{n}=1+s_{n-1}}$	${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$
${\displaystyle s_{0}=0}$	${\displaystyle s_{0}=0;s_{1}=1}$

Определение последовательности натуральных чисел с использованием неоднородной рекуррентности и эквивалентной однородной версии.${\displaystyle s_{n}=n}$

Неоднородная линейная рекуррентность — это уравнение вида

${\displaystyle s_{n}=c_{1}s_{n-1}+c_{2}s_{n-2}+\dots +c_{d}s_{n-d}+c}$

где — дополнительная константа. Любая последовательность, удовлетворяющая неоднородной линейной рекурсии, является константно-рекурсивной. Это происходит потому, что вычитание уравнения для из уравнения для дает однородную рекурсию для , из которой мы можем решить для , чтобы получить ^{[ необходима цитата ]}${\displaystyle c}$${\displaystyle s_{n-1}}$${\displaystyle s_{n}}$${\displaystyle s_{n}-s_{n-1}}$${\displaystyle s_{n}}$

${\displaystyle {\begin{aligned}s_{n}=&(c_{1}+1)s_{n-1}\\&+(c_{2}-c_{1})s_{n-2}+\dots +(c_{d}-c_{d-1})s_{n-d}\\&-c_{d}s_{n-d-1}.\end{aligned}}}$

${\displaystyle \sum _{n=0}^{\infty }F_{n}x^{n}={\frac {x}{1-x-x^{2}}}.}$

Определение последовательности Фибоначчи с помощью производящей функции.

Последовательность является константно-рекурсивной именно тогда, когда ее производящая функция

${\displaystyle \sum _{n=0}^{\infty }s_{n}x^{n}=s_{0}+s_{1}x^{1}+s_{2}x^{2}+s_{3}x^{3}+\cdots }$

является рациональной функцией , где и являются многочленами и . ^[3] Более того, порядок последовательности является минимальным таким, что она имеет такой вид с и . ^[12]${\displaystyle p(x)\,/\,q(x)}$${\displaystyle p}$${\displaystyle q}$${\displaystyle q(0)=1}$${\displaystyle d}$${\displaystyle {\text{deg }}q(x)\leq d}$${\displaystyle {\text{deg }}p(x)<d}$

Знаменатель — это многочлен, полученный из вспомогательного многочлена путем изменения порядка коэффициентов на обратный , а числитель определяется начальными значениями последовательности: ^{[13] [14]}

${\displaystyle \sum _{n=0}^{\infty }s_{n}x^{n}={\frac {b_{0}+b_{1}x^{1}+b_{2}x^{2}+\dots +b_{d-1}x^{d-1}}{1-c_{1}x^{1}-c_{2}x^{2}-\dots -c_{d}x^{d}}},}$

где

${\displaystyle b_{n}=s_{n}-c_{1}s_{n-1}-c_{2}s_{n-2}-\dots -c_{d}s_{n-d}.}$^[15]

Из вышесказанного следует, что знаменатель должен быть многочленом, не делящимся на (и, в частности, отличным от нуля).${\displaystyle q(x)}$${\displaystyle x}$

${\displaystyle \{(an+b)_{n=0}^{\infty }:a,b\in \mathbb {R} \}}$

2-мерное векторное пространство последовательностей, генерируемых последовательностью .${\displaystyle s_{n}=n}$

Последовательность является константно-рекурсивной тогда и только тогда, когда набор последовательностей${\displaystyle (s_{n})_{n=0}^{\infty }}$

${\displaystyle \left\{(s_{n+r})_{n=0}^{\infty }:r\geq 0\right\}}$

содержится в пространстве последовательностей ( векторном пространстве последовательностей), размерность которого конечна. То есть содержится в конечномерном подпространстве замкнутом относительно оператора левого сдвига . ^{[16] [17]}${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle \mathbb {C} ^{\mathbb {N} }}$

Эта характеристика обусловлена ​​тем, что порядково -линейное рекуррентное отношение можно понимать как доказательство линейной зависимости между последовательностями для . Расширение этого аргумента показывает, что порядок последовательности равен размерности пространства последовательностей, сгенерированного для всех . ^{[18] [17]}${\displaystyle d}$${\displaystyle (s_{n+r})_{n=0}^{\infty }}$${\displaystyle r=0,\ldots ,d}$${\displaystyle (s_{n+r})_{n=0}^{\infty }}$${\displaystyle r}$

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}(1.618\ldots )^{n}-{\frac {1}{\sqrt {5}}}(-0.618\ldots )^{n}}$

Характеристика последовательности Фибоначчи в замкнутой форме ( формула Бине )

Константно-рекурсивные последовательности допускают следующую уникальную замкнутую форму характеризации с использованием экспоненциальных полиномов : каждая константно-рекурсивная последовательность может быть записана в виде

${\displaystyle s_{n}=z_{n}+k_{1}(n)r_{1}^{n}+k_{2}(n)r_{2}^{n}+\cdots +k_{e}(n)r_{e}^{n},}$

для всех , где${\displaystyle n\geq 0}$

• Член представляет собой последовательность, которая равна нулю для всех (где — порядок последовательности);${\displaystyle z_{n}}$${\displaystyle n\geq d}$${\displaystyle d}$
• Члены являются сложными многочленами; и${\displaystyle k_{1}(n),k_{2}(n),\ldots ,k_{e}(n)}$
• Эти термины представляют собой различные комплексные константы. ^{[19] [3]}${\displaystyle r_{1},r_{2},\ldots ,r_{k}}$

Эта характеристика точна: каждая последовательность комплексных чисел, которая может быть записана в указанной выше форме, является константно-рекурсивной. ^[20]

Например, число Фибоначчи записывается в такой форме с использованием формулы Бине : ^[21]${\displaystyle F_{n}}$

${\displaystyle F_{n}={\frac {1}{\sqrt {5}}}\varphi ^{n}-{\frac {1}{\sqrt {5}}}\psi ^{n},}$

где — золотое сечение и . Это корни уравнения . В этом случае , для всех , — оба постоянные многочлены, , и .${\displaystyle \varphi =(1+{\sqrt {5}})\,/\,2\approx 1.61803\ldots }$${\displaystyle \psi =-1\,/\,\varphi }$${\displaystyle x^{2}-x-1=0}$${\displaystyle e=2}$${\displaystyle z_{n}=0}$${\displaystyle n}$${\displaystyle k_{1}(n)=k_{2}(n)=1\,/\,{\sqrt {5}}}$${\displaystyle r_{1}=\varphi }$${\displaystyle r_{2}=\psi }$

Термин необходим только тогда, когда ; если тогда он корректирует тот факт, что некоторые начальные значения могут быть исключениями из общей повторяемости. В частности, для всех . ^{[ необходима цитата ]}${\displaystyle z_{n}}$${\displaystyle c_{d}\neq 0}$${\displaystyle c_{d}=0}$${\displaystyle z_{n}=0}$${\displaystyle n\geq d}$

Комплексные числа являются корнями характеристического многочлена рекуррентного соотношения:${\displaystyle r_{1},\ldots ,r_{n}}$

${\displaystyle x^{d}-c_{1}x^{d-1}-\dots -c_{d-1}x-c_{d}}$

коэффициенты которого такие же, как у рекуррентности. ^[22] Мы называем характеристические корни рекуррентности. Если последовательность состоит из целых или рациональных чисел, корни будут алгебраическими числами . Если корни все различны, то все многочлены являются константами, которые можно определить из начальных значений последовательности. Если корни характеристического многочлена не различны, и является корнем кратности , то в формуле имеет степень . Например, если характеристический многочлен разлагается на множители , причем один и тот же корень r встречается три раза, то th-й член имеет вид ^{[23] [24]}${\displaystyle r_{1},\ldots ,r_{n}}$${\displaystyle d}$${\displaystyle r_{1},r_{2},\dots ,r_{d}}$${\displaystyle k_{i}(n)}$${\displaystyle r_{i}}$ ${\displaystyle m}$${\displaystyle k_{i}(n)}$${\displaystyle m-1}$${\displaystyle (x-r)^{3}}$${\displaystyle n}$${\displaystyle s_{n}=(a+bn+cn^{2})r^{n}.}$

Сумма двух константно-рекурсивных последовательностей также является константно-рекурсивной. ^{[25] [26]} Например, сумма и равна ( ), что удовлетворяет рекуррентности . Новая рекуррентность может быть найдена путем сложения генерирующих функций для каждой последовательности.${\displaystyle s_{n}=2^{n}}$${\displaystyle t_{n}=n}$${\displaystyle u_{n}=2^{n}+n}$${\displaystyle 1,3,6,11,20,\ldots }$${\displaystyle u_{n}=4u_{n-1}-5u_{n-2}+2u_{n-3}}$

Аналогично, произведение двух константно-рекурсивных последовательностей является константно-рекурсивным. ^[25] Например, произведение и равно ( ), что удовлетворяет рекуррентному соотношению .${\displaystyle s_{n}=2^{n}}$${\displaystyle t_{n}=n}$${\displaystyle u_{n}=n\cdot 2^{n}}$${\displaystyle 0,2,8,24,64,\ldots }$${\displaystyle u_{n}=4u_{n-1}-4u_{n-2}}$

Последовательность сдвига влево и последовательность сдвига вправо (с ) являются константно-рекурсивными, поскольку они удовлетворяют одному и тому же рекуррентному соотношению. Например, поскольку является константно-рекурсивной, то и .${\displaystyle u_{n}=s_{n+1}}$${\displaystyle u_{n}=s_{n-1}}$${\displaystyle u_{0}=0}$${\displaystyle s_{n}=2^{n}}$${\displaystyle u_{n}=2^{n+1}}$

В общем случае константно-рекурсивные последовательности замкнуты относительно следующих операций, где обозначают константно-рекурсивные последовательности, — их производящие функции, а — их порядки соответственно. ^[27]${\displaystyle s=(s_{n})_{n\in \mathbb {N} },t=(t_{n})_{n\in \mathbb {N} }}$${\displaystyle f(x),g(x)}$${\displaystyle d,e}$

Операции над константно-рекурсивными последовательностями

Операция	Определение	Требование	Эквивалент функции генерации	Заказ
Сумма по срокам${\displaystyle s+t}$	${\displaystyle (s+t)_{n}=s_{n}+t_{n}}$	—	${\displaystyle f(x)+g(x)}$	${\displaystyle \leq d+e}$[25]
Срок действия продукта${\displaystyle s\cdot t}$	${\displaystyle (s\cdot t)_{n}=s_{n}\cdot t_{n}}$	—	${\displaystyle {\frac {1}{2\pi i}}\int _{\gamma }{\frac {f(\zeta )}{\zeta }}g\left({\frac {x}{\zeta }}\right)\;\mathrm {d} \zeta }$[28] [29]	${\displaystyle \leq d\cdot e}$[11] [25]
продукт Коши ${\displaystyle s*t}$	${\displaystyle (s*t)_{n}=\sum _{i=0}^{n}s_{i}t_{n-i}}$	—	${\displaystyle f(x)g(x)}$	${\displaystyle \leq d+e}$[27]
Сдвиг влево${\displaystyle Ls}$	${\displaystyle (Ls)_{n}=s_{n+1}}$	—	${\displaystyle {\frac {f(x)-s_{0}}{x}}}$	${\displaystyle \leq d}$[27]
Сдвиг вправо${\displaystyle Rs}$	${\displaystyle (Rs)_{n}={\begin{cases}s_{n-1}&n\geq 1\\0&n=0\end{cases}}}$	—	${\displaystyle xf(x)}$	${\displaystyle \leq d+1}$[27]
Обратное уравнение Коши ${\displaystyle s^{(-1)}}$	${\displaystyle (s^{(-1)})_{n}=\sum _{{i_{1}+\dots +i_{k}=n} \atop {i_{1},\ldots ,i_{k}\neq 0}}(-1)^{k}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}}$	${\displaystyle s_{0}=1}$	${\displaystyle {\frac {1}{f(x)}}}$	${\displaystyle \leq d+1}$[27]
звезда Клини ${\displaystyle s^{(*)}}$	${\displaystyle (s^{(*)})_{n}=\sum _{{i_{1}+\dots +i_{k}=n} \atop {i_{1},\ldots ,i_{k}\neq 0}}s_{i_{1}}s_{i_{2}}\cdots s_{i_{k}}}$	${\displaystyle s_{0}=0}$	${\displaystyle {\frac {1}{1-f(x)}}}$	${\displaystyle \leq d+1}$[27]

Замыкание при почленном сложении и умножении следует из замкнутой формы характеризации в терминах экспоненциальных полиномов. Замыкание при произведении Коши следует из характеризации производящей функции. ^[27] Требование для обратного Коши необходимо для случая целочисленных последовательностей, но может быть заменено на , если последовательность находится над любым полем (рациональные, алгебраические, действительные или комплексные числа). ^[27]${\displaystyle s_{0}=1}$${\displaystyle s_{0}\neq 0}$

Несмотря на удовлетворение простой локальной формулы, константно-рекурсивная последовательность может демонстрировать сложное глобальное поведение. Определим ноль константно- рекурсивной последовательности как неотрицательное целое число, такое что . Теорема Сколема–Малера–Леха утверждает, что нули последовательности в конечном итоге повторяются: существуют константы и такие, что для всех , тогда и только тогда, когда . Этот результат справедлив для константно-рекурсивной последовательности над комплексными числами или, в более общем смысле, над любым полем нулевой характеристики . [ ^30]${\displaystyle n}$${\displaystyle s_{n}=0}$${\displaystyle M}$${\displaystyle N}$${\displaystyle n>M}$${\displaystyle s_{n}=0}$${\displaystyle s_{n+N}=0}$

Шаблон нулей в константно-рекурсивной последовательности также может быть исследован с точки зрения теории вычислимости . Для этого описание последовательности должно быть дано в виде конечного описания ; это может быть сделано, если последовательность находится над целыми числами или рациональными числами, или даже над алгебраическими числами. ^[11] При наличии такого кодирования для последовательностей могут быть изучены следующие проблемы:${\displaystyle s_{n}}$${\displaystyle s_{n}}$

Известные проблемы принятия решений

Проблема	Описание	Статус [11] [31]
Существование нуля ( задача Сколема )	На входе , для некоторых ?${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=0}$${\displaystyle n}$	Открыть
Бесконечно много нулей	На входе , для бесконечного множества ?${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=0}$${\displaystyle n}$	Разрешимый
В конечном итоге все ноль	На входе , для всех достаточно большой ?${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}=0}$ ${\displaystyle n}$	Разрешимый
Позитивность	На входе , для всех ?${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}>0}$${\displaystyle n}$	Открыть
Конечный позитив	На входе , для всех достаточно большой ?${\displaystyle (s_{n})_{n=0}^{\infty }}$${\displaystyle s_{n}>0}$ ${\displaystyle n}$	Открыть

Поскольку квадрат константно-рекурсивной последовательности все еще является константно-рекурсивным (см. свойства замыкания), проблема существования нуля в таблице выше сводится к положительности, а бесконечно много нулей сводится к возможной положительности. Другие проблемы также сводятся к проблемам в таблице выше: например, сводится ли для некоторых к существованию нуля для последовательности . В качестве второго примера, для последовательностей в действительных числах слабая положительность (является ли для всех ?) сводится к положительности последовательности (потому что ответ должен быть отрицательным, это редукция Тьюринга ).${\displaystyle s_{n}^{2}}$${\displaystyle s_{n}=c}$${\displaystyle n}$${\displaystyle s_{n}-c}$${\displaystyle s_{n}\geq 0}$${\displaystyle n}$${\displaystyle -s_{n}}$

Теорема Скулема-Малера-Леха могла бы дать ответы на некоторые из этих вопросов, за исключением того, что ее доказательство неконструктивно . Она утверждает, что для всех нули повторяются; однако неизвестно , вычислимо ли значение , поэтому это не приводит к решению проблемы существования нуля. ^[11] С другой стороны, точный шаблон, который повторяется после , вычислим . ^{[11] [32]} Вот почему проблема бесконечного числа нулей разрешима: просто определите, пуст ли бесконечно повторяющийся шаблон.${\displaystyle n>M}$${\displaystyle M}$${\displaystyle n>M}$

Результаты разрешимости известны, когда порядок последовательности ограничен малым. Например, проблема Сколема разрешима для алгебраических последовательностей порядка до 4. ^{[33] [34] [35]} Также известно, что она разрешима для обратимых целочисленных последовательностей до порядка 7, то есть последовательностей, которые могут быть продолжены в обратном направлении в целых числах. ^[31]

Результаты разрешимости также известны при предположении некоторых недоказанных гипотез в теории чисел . Например, разрешимость известна для рациональных последовательностей порядка до 5, подчиняющихся гипотезе Скулема (также известной как экспоненциальный локально-глобальный принцип). Разрешимость также известна для всех простых рациональных последовательностей (с простым характеристическим полиномом), подчиняющихся гипотезе Скулема и слабой p-адической гипотезе Шануэля. ^[36]

Пусть — характеристические корни постоянной рекурсивной последовательности . Мы говорим, что последовательность вырождена, если любое отношение является корнем из единицы, для . Часто бывает проще изучать невырожденные последовательности, в определенном смысле к этому можно свести следующую теорему: если имеет порядок и содержится в числовом поле степени над , то существует константа${\displaystyle r_{1},\ldots ,r_{n}}$${\displaystyle s}$${\displaystyle r_{i}/r_{j}}$${\displaystyle i\neq j}$${\displaystyle s}$${\displaystyle d}$${\displaystyle K}$${\displaystyle k}$${\displaystyle \mathbb {Q} }$${\displaystyle M(k,d)\leq {\begin{cases}\exp(2d(3\log d)^{1/2})&{\text{if }}k=1,\\2^{kd+1}&{\text{if }}k\geq 2\end{cases}}}$

таким образом, что для некоторых каждая подпоследовательность либо тождественно равна нулю, либо невырождена. ^[37]${\displaystyle M\leq M(k,d)}$${\displaystyle s_{Mn+\ell }}$

D -конечная или голономная последовательность является естественным обобщением, в котором коэффициенты рекуррентности могут быть полиномиальными функциями, а не константами. ^[38]${\displaystyle n}$

-Регулярная последовательность удовлетворяет линейным рекуррентным соотношениям с постоянными коэффициентами, но рекуррентные соотношения принимают другую форму. Вместо того чтобы быть линейной комбинацией для некоторых целых чисел , близких к , каждый член в -регулярной последовательности является линейной комбинацией для некоторых целых чисел , чьи представления по основанию близки к представлению . ^[39] Постоянно-рекурсивные последовательности можно рассматривать как -регулярные последовательности, где представление по основанию 1 состоит из копий цифры . ^{[ требуется ссылка ]}${\displaystyle k}$${\displaystyle s_{n}}$${\displaystyle s_{m}}$${\displaystyle m}$${\displaystyle n}$${\displaystyle s_{n}}$${\displaystyle k}$${\displaystyle s_{m}}$${\displaystyle m}$${\displaystyle k}$${\displaystyle n}$${\displaystyle 1}$${\displaystyle n}$${\displaystyle n}$${\displaystyle 1}$

• «Индекс OEIS Rec». Индекс OEIS по нескольким тысячам примеров линейных рекуррентных соотношений, отсортированных по порядку (количество членов) и сигнатуре (вектор значений постоянных коэффициентов)