secuencia recursiva constante

La secuencia 0, 1, 1, 2, 3, 5, 8, 13, ... de números de Fibonacci es recursiva constante de orden 2 porque satisface la recurrencia${\displaystyle F_{n}=F_{n-1}+F_{n-2}}$con${\displaystyle F_{0}=0,F_{1}=1}$. Por ejemplo,${\displaystyle F_{2}=F_{1}+F_{0}=1+0=1}$y${\displaystyle F_{6}=F_{5}+F_{4}=5+3=8}$La secuencia 2, 1, 3, 4, 7, 11, ... de números de Lucas satisface la misma recurrencia que la secuencia de Fibonacci pero con condiciones iniciales${\displaystyle L_{0}=2}$y${\displaystyle L_{1}=1}$. De manera más general, toda secuencia de Lucas es recursiva constante de orden 2. ^{[ 2 ]}

Para cualquier${\displaystyle a}$y cualquier${\displaystyle r\neq 0}$la progresión aritmética${\displaystyle a,a+r,a+2r,\ldots }$es recursiva constante de orden 2, porque satisface${\displaystyle s_{n}=2s_{n-1}-s_{n-2}}$Generalizando esto, véanse las secuencias polinómicas a continuación.

Para cualquier${\displaystyle a\neq 0}$y${\displaystyle r}$la progresión geométrica${\displaystyle a,ar,ar^{2},\ldots }$es recursiva constante de orden 1, porque satisface${\displaystyle s_{n}=rs_{n-1}}$Esto incluye, por ejemplo, la secuencia 1, 2, 4, 8, 16, ... así como la secuencia de números racionales.${\textstyle 1,{\frac {1}{2}},{\frac {1}{4}},{\frac {1}{8}},{\frac {1}{16}},...}$.

Una secuencia que eventualmente es periódica con una duración de período${\displaystyle \ell }$es recursiva constante, ya que satisface${\displaystyle s_{n}=s_{n-\ell }}$a pesar de${\displaystyle n\geq d}$donde el orden${\displaystyle d}$es la longitud del segmento inicial que incluye el primer bloque repetitivo. Ejemplos de tales secuencias son 1, 0, 0, 0, ... (orden 1) y 1, 6, 6, 6, ... (orden 2).

Una secuencia definida por un polinomio${\displaystyle s_{n}=a_{0}+a_{1}n+a_{2}n^{2}+\cdots +a_{d}n^{d}}$es recursiva constante. La secuencia satisface una recurrencia de orden${\displaystyle d+1}$(dónde${\displaystyle d}$es el grado del polinomio), con coeficientes dados por el elemento correspondiente de la transformación binomial . ^{[ 7 ] [ 8 ]} Las primeras ecuaciones de este tipo son

${\displaystyle s_{n}=1\cdot s_{n-1}}$para un polinomio de grado 0 (es decir, constante),

${\displaystyle s_{n}=2\cdot s_{n-1}-1\cdot s_{n-2}}$para un polinomio de grado 1 o menor,

${\displaystyle s_{n}=3\cdot s_{n-1}-3\cdot s_{n-2}+1\cdot s_{n-3}}$para un polinomio de grado 2 o menor, y

${\displaystyle s_{n}=4\cdot s_{n-1}-6\cdot s_{n-2}+4\cdot s_{n-3}-1\cdot s_{n-4}}$para un polinomio de grado 3 o menor.

Una sucesión que obedece la ecuación de orden d también obedece todas las ecuaciones de orden superior. Estas identidades pueden demostrarse de varias maneras, incluyendo mediante la teoría de diferencias finitas . ^{[ 9 ]} Cualquier sucesión de${\displaystyle d+1}$Los valores enteros, reales o complejos pueden utilizarse como condiciones iniciales para una secuencia recursiva constante de orden${\displaystyle d+1}$Si las condiciones iniciales se encuentran sobre un polinomio de grado${\displaystyle d-1}$o menos, entonces la secuencia recursiva constante también obedece una ecuación de orden inferior.

Dejar${\displaystyle L}$ser un idioma regular y dejar${\displaystyle s_{n}}$sea ​​el número de palabras de longitud${\displaystyle n}$en${\displaystyle L}$. Entonces${\displaystyle (s_{n})_{n=0}^{\infty }}$es recursivo constante. ^{[ 10 ]} Por ejemplo,${\displaystyle s_{n}=2^{n}}$para el lenguaje de todas las cadenas binarias,${\displaystyle s_{n}=1}$para el lenguaje de todas las cadenas unarias, y${\displaystyle s_{n}=F_{n+2}}$para el lenguaje de todas las cadenas binarias que no tienen dos unos consecutivos. Más generalmente, cualquier función aceptada por un autómata ponderado sobre el alfabeto unario.${\displaystyle \Sigma =\{a\}}$sobre el semianillo${\displaystyle (\mathbb {R} ,+,\times )}$(que de hecho es un anillo , e incluso un cuerpo ) es recursivo constante.

Las secuencias de números de Jacobsthal , números de Padovan , números de Pell y números de Perrin ^{[ 2 ]} son ​​recursivas constantes.

La secuencia factorial${\displaystyle 1,1,2,6,24,120,720,\ldots }$no es recursiva constante. En términos más generales, toda función recursiva constante está asintóticamente acotada por una función exponencial (véase #Caracterización en forma cerrada ) y la sucesión factorial crece más rápido que esto.

La secuencia catalana${\displaystyle 1,1,2,5,14,42,132,\ldots }$no es recursivo constante. Esto se debe a que la función generadora de los números de Catalan no es una función racional (ver #Definiciones equivalentes ).

Una secuencia${\displaystyle (s_{n})_{n=0}^{\infty }}$es recursiva constante de orden menor o igual a${\displaystyle d}$si y solo si se puede escribir como

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

dónde${\displaystyle u}$es un${\displaystyle 1\times d}$vector,${\displaystyle A}$es un${\displaystyle d\times d}$matriz y${\displaystyle v}$es un${\displaystyle d\times 1}$vector, donde los elementos provienen del mismo dominio (enteros, números racionales, números algebraicos, números reales o números complejos) que la secuencia original. Específicamente,${\displaystyle v}$puede tomarse como el primero${\displaystyle d}$valores de la secuencia,${\displaystyle A}$la transformación lineal que calcula${\displaystyle s_{n+1},s_{n+2},\ldots ,s_{n+d}}$de${\displaystyle s_{n},s_{n+1},\ldots ,s_{n+d-1}}$, y${\displaystyle u}$el vector${\displaystyle [0,0,\ldots ,0,1]}$. ^{[ 11 ]}

Definición de la sucesión de números naturales${\displaystyle s_{n}=n}$, utilizando una recurrencia no homogénea y la versión homogénea equivalente.

Una recurrencia lineal no homogénea es una ecuación de la forma

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

dónde${\displaystyle c}$es una constante adicional. Cualquier secuencia que satisfaga una recurrencia lineal no homogénea es recursiva constante. Esto se debe a que restar la ecuación para${\displaystyle s_{n-1}}$de la ecuación para${\displaystyle s_{n}}$produce una recurrencia homogénea para${\displaystyle s_{n}-s_{n-1}}$, a partir de lo cual podemos resolver${\displaystyle s_{n}}$para obtener

${\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}}}$

Una secuencia es recursiva constante precisamente cuando su función generadora

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

es una función racional${\displaystyle p(x)\,/\,q(x)}$, dónde${\displaystyle p}$y${\displaystyle q}$son polinomios y${\displaystyle q(0)=1}$. ^{[ 3 ]} Además, el orden de la secuencia es el mínimo${\displaystyle d}$de tal manera que tenga tal forma con${\displaystyle {\text{deg }}q(x)\leq d}$y${\displaystyle {\text{deg }}p(x)<d}$. ^{[ 12 ]}

El denominador es el polinomio obtenido a partir del polinomio auxiliar invirtiendo el orden de los coeficientes , y el numerador está determinado por los valores iniciales de la secuencia: ^{[ 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}}},}$

dónde

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

De lo anterior se deduce que el denominador${\displaystyle q(x)}$debe ser un polinomio no divisible por${\displaystyle x}$(y en particular distinto de cero).

Espacio vectorial bidimensional de secuencias generadas por la secuencia${\displaystyle s_{n}=n}$.

Una secuencia${\displaystyle (s_{n})_{n=0}^{\infty }}$es recursiva constante si y solo si el conjunto de secuencias

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

está contenido en un espacio de secuencias ( espacio vectorial de secuencias) cuya dimensión es finita. Es decir,${\displaystyle (s_{n})_{n=0}^{\infty }}$está contenido en un subespacio de dimensión finita de${\displaystyle \mathbb {C} ^{\mathbb {N} }}$cerrado bajo el operador de desplazamiento a la izquierda . ^{[ 16 ] [ 17 ]}

Esta caracterización se debe al orden-${\displaystyle d}$La relación de recurrencia lineal puede entenderse como una prueba de dependencia lineal entre las secuencias.${\displaystyle (s_{n+r})_{n=0}^{\infty }}$para${\displaystyle r=0,\ldots ,d}$. Una extensión de este argumento muestra que el orden de la secuencia es igual a la dimensión del espacio de secuencias generado por${\displaystyle (s_{n+r})_{n=0}^{\infty }}$a pesar de${\displaystyle r}$. ^{[ 18 ] [ 17 ]}

La suma de dos secuencias recursivas constantes también es recursiva constante. ^{[ 25 ] [ 26 ]} Por ejemplo, la suma de${\displaystyle s_{n}=2^{n}}$y${\displaystyle t_{n}=n}$es${\displaystyle u_{n}=2^{n}+n}$(${\displaystyle 1,3,6,11,20,\ldots }$), que satisface la recurrencia${\displaystyle u_{n}=4u_{n-1}-5u_{n-2}+2u_{n-3}}$La nueva recurrencia se puede encontrar sumando las funciones generadoras para cada secuencia.

De manera similar, el producto de dos secuencias recursivas constantes es recursivo constante. ^{[ 25 ]} Por ejemplo, el producto de${\displaystyle s_{n}=2^{n}}$y${\displaystyle t_{n}=n}$es${\displaystyle u_{n}=n\cdot 2^{n}}$(${\displaystyle 0,2,8,24,64,\ldots }$), que satisface la recurrencia${\displaystyle u_{n}=4u_{n-1}-4u_{n-2}}$.

La secuencia de desplazamiento a la izquierda${\displaystyle u_{n}=s_{n+1}}$y la secuencia de desplazamiento a la derecha${\displaystyle u_{n}=s_{n-1}}$(con${\displaystyle u_{0}=0}$) son recursivas constantes porque satisfacen la misma relación de recurrencia. Por ejemplo, porque${\displaystyle s_{n}=2^{n}}$es recursivo constante, por lo que también lo es.${\displaystyle u_{n}=2^{n+1}}$.

En general, las secuencias recursivas constantes son cerradas bajo las siguientes operaciones, donde${\displaystyle s=(s_{n})_{n\in \mathbb {N} },t=(t_{n})_{n\in \mathbb {N} }}$denotan secuencias recursivas constantes,${\displaystyle f(x),g(x)}$son sus funciones generadoras y${\displaystyle d,e}$son sus órdenes, respectivamente. ^{[ 27 ]}

El cierre bajo la suma y multiplicación término a término se deduce de la caracterización en forma cerrada en términos de polinomios exponenciales. El cierre bajo el producto de Cauchy se deduce de la caracterización de la función generadora. ^{[ 27 ]} El requisito${\displaystyle s_{0}=1}$para la inversa de Cauchy es necesaria para el caso de secuencias de enteros, pero puede ser reemplazada por${\displaystyle s_{0}\neq 0}$si la sucesión está sobre cualquier cuerpo (números racionales, algebraicos, reales o complejos). ^{[ 27 ]}

A pesar de satisfacer una fórmula local simple, una secuencia recursiva constante puede exhibir un comportamiento global complejo. Definimos el cero de una secuencia recursiva constante como un número entero no negativo.${\displaystyle n}$de tal manera que${\displaystyle s_{n}=0}$El teorema de Skolem-Mahler-Lech establece que los ceros de la secuencia se repiten eventualmente: existen constantes${\displaystyle M}$y${\displaystyle N}$de tal manera que para todos${\displaystyle n>M}$,${\displaystyle s_{n}=0}$si y solo si${\displaystyle s_{n+N}=0}$Este resultado es válido para una secuencia recursiva constante sobre los números complejos, o más generalmente, sobre cualquier cuerpo de característica cero. ^{[ 30 ]}

El patrón de ceros en una secuencia recursiva constante también puede investigarse desde la perspectiva de la teoría de la computabilidad . Para ello, la descripción de la secuencia${\displaystyle s_{n}}$debe proporcionarse una descripción finita ; esto puede hacerse si la secuencia está sobre los números enteros, racionales o algebraicos. ^{[ 11 ]} Dada dicha codificación para secuencias${\displaystyle s_{n}}$Se pueden estudiar los siguientes problemas:

Porque el cuadrado de una secuencia recursiva constante${\displaystyle s_{n}^{2}}$sigue siendo recursivo constante (véanse las propiedades de cierre ), el problema de la existencia de un cero en la tabla anterior se reduce a la positividad, e infinitos ceros se reduce a la positividad eventual. Otros problemas también se reducen a los de la tabla anterior: por ejemplo, si${\displaystyle s_{n}=c}$para algunos${\displaystyle n}$se reduce a la existencia de un cero para la secuencia${\displaystyle s_{n}-c}$. Como segundo ejemplo, para secuencias en los números reales, la positividad débil (es${\displaystyle s_{n}\geq 0}$a pesar de${\displaystyle n}$?) se reduce a la positividad de la secuencia${\displaystyle -s_{n}}$(dado que la respuesta debe ser negada, esto es una reducción de Turing ).

El teorema de Skolem-Mahler-Lech proporcionaría respuestas a algunas de estas preguntas, excepto que su demostración no es constructiva . Afirma que para todo${\displaystyle n>M}$, los ceros se repiten; sin embargo, el valor de${\displaystyle M}$no se sabe que sea computable, por lo que esto no conduce a una solución al problema de la existencia de un cero. ^{[ 11 ]} Por otro lado, el patrón exacto que se repite después${\displaystyle n>M}$es computable. ^{[ 11 ] [ 32 ]} Por eso el problema de los infinitos ceros es decidible: basta con determinar si el patrón que se repite infinitamente está vacío.

Se conocen resultados de decidibilidad cuando el orden de una secuencia está restringido a ser pequeño. Por ejemplo, el problema de Skolem es decidible para secuencias algebraicas de orden hasta 4. ^{[ 33 ] [ 34 ] [ 35 ]} También se sabe que es decidible para secuencias enteras reversibles de orden hasta 7, es decir, secuencias que pueden continuarse hacia atrás en los enteros. ^{[ 31 ]}

También se conocen resultados de decidibilidad bajo el supuesto de ciertas conjeturas no probadas en teoría de números . Por ejemplo, se conoce la decidibilidad para secuencias racionales de orden hasta 5 sujetas a una conjetura conocida como la conjetura de Skolem o el principio exponencial local-global. Asimismo, se conoce la decidibilidad para todas las secuencias racionales simples (aquellas con polinomio característico simple ) sujetas a la conjetura de Skolem y a la conjetura débil p-ádica de Schanuel. ^{[ 36 ]}

Dejar${\displaystyle r_{1},\ldots ,r_{n}}$sean las raíces características de una secuencia recursiva constante${\displaystyle s}$Decimos que la sucesión es degenerada si la razón${\displaystyle r_{i}/r_{j}}$es una raíz de unidad , para cualquier${\displaystyle i\neq j}$A menudo es más fácil estudiar secuencias no degeneradas, y se puede reducir a esto usando el siguiente teorema: si${\displaystyle s}$tiene orden${\displaystyle d}$y está contenido en un campo numérico${\displaystyle K}$de grado${\displaystyle k}$encima${\displaystyle \mathbb {Q} }$, entonces hay una constante${\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}}}$

de tal manera que para algunos${\displaystyle M\leq M(k,d)}$cada subsecuencia${\displaystyle s_{Mn+\ell }}$es idénticamente cero o no degenerado. ^{[ 37 ]}