Secuencia recursiva constante

Infinite sequence of numbers satisfying a linear equation

La secuencia de Fibonacci es constante-recursiva: cada elemento de la secuencia es la suma de los dos anteriores.

Diagrama de Hasse de algunas subclases de secuencias recursivas constantes, ordenadas por inclusión

En matemáticas , una secuencia infinita de números se denomina recursiva constante si satisface una ecuación de la forma ${\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},}$$

para todos , donde son constantes . La ecuación se denomina relación de recurrencia lineal . El concepto también se conoce como secuencia de recurrencia lineal , secuencia recursiva lineal , secuencia recurrente lineal o secuencia C-finita . ^[1] ${\displaystyle n\geq d}$ ${\displaystyle c_{i}}$

Por ejemplo, la secuencia de Fibonacci

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

es recursiva constante porque satisface la recurrencia lineal : cada número en la secuencia es la suma de los dos anteriores. ^[2] Otros ejemplos incluyen la secuencia de potencia de dos , donde cada número es la suma del doble del número anterior, y la secuencia de números al cuadrado . Todas las progresiones aritméticas , todas las progresiones geométricas y todos los polinomios son recursivas constantes. Sin embargo, no todas las secuencias son recursivas constantes; por ejemplo, la secuencia factorial no es recursiva constante. ${\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 }$

Las secuencias recursivas constantes se estudian en combinatoria y en la teoría de diferencias finitas . También surgen en la teoría algebraica de números , debido a la relación de la secuencia con las raíces polinómicas ; en el análisis de algoritmos , como el tiempo de ejecución de funciones recursivas simples ; y en la teoría de lenguajes formales , donde cuentan cadenas hasta una longitud dada en un lenguaje regular . Las secuencias recursivas constantes se cierran bajo operaciones matemáticas importantes como la adición término por término , la multiplicación término por término y el producto de Cauchy .

El teorema de Skolem-Mahler-Lech establece que los ceros de una secuencia recursiva constante tienen una forma que se repite regularmente (eventualmente, de forma periódica). El problema de Skolem , que pide un algoritmo para determinar si una recurrencia lineal tiene al menos un cero, es un problema sin resolver en matemáticas .

Definición

Una secuencia recursiva constante es cualquier secuencia de números enteros , números racionales , números algebraicos , números reales o números complejos (escritos como abreviatura) que satisfacen una fórmula de la forma ${\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},}$$

para todos, para algunos coeficientes fijos que se extienden sobre el mismo dominio que la secuencia (números enteros, números racionales, números algebraicos, números reales o números complejos). La ecuación se llama recurrencia lineal con coeficientes constantes de orden d . El orden de la secuencia es el entero positivo más pequeño tal que la secuencia satisface una recurrencia de orden d , o para la secuencia de cero en todas partes. ^{[ cita requerida ]} ${\displaystyle n\geq d,}$ ${\displaystyle c_{1},c_{2},\dots ,c_{d}}$ ${\displaystyle d}$ ${\displaystyle d=0}$

La definición anterior permite secuencias eventualmente periódicas como y . Algunos autores exigen que , lo que excluye dichas secuencias. ^{[3] [4] [5]} ${\displaystyle 1,0,0,0,\ldots }$ ${\displaystyle 0,1,0,0,\ldots }$ ${\displaystyle c_{d}\neq 0}$

Ejemplos

Secuencias de Fibonacci y Lucas

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 con . Por ejemplo, y . 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 y . De manera más general, toda secuencia de Lucas es recursiva constante de orden 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}$

Progresiones aritméticas

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

Progresiones geométricas

Para cualquier y , la progresión geométrica es recursiva constante de orden 1, porque satisface . Esto incluye, por ejemplo, la secuencia 1, 2, 4, 8, 16, ... así como la secuencia de números racionales . ^{[ cita requerida ]} ${\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}},...}$

Secuencias eventualmente periódicas

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

Sucesiones polinómicas

Una secuencia definida por un polinomio es recursiva constante. La secuencia satisface una recurrencia de orden (donde es el grado del polinomio), con coeficientes dados por el elemento correspondiente de la transformada binomial . ^{[7] [8]} Las primeras ecuaciones de este tipo son ${\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}}$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 menos,

${\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 menos, 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 menos.

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

Enumeración de palabras en un lenguaje regular

Sea un lenguaje regular , y sea el número de palabras de longitud en . Entonces es recursivo constante. ^[10] Por ejemplo, para el lenguaje de todas las cadenas binarias, para el lenguaje de todas las cadenas unarias y para el lenguaje de todas las cadenas binarias que no tienen dos unos consecutivos. De manera más general, cualquier función aceptada por un autómata ponderado sobre el alfabeto unario sobre el semiring (que de hecho es un anillo e incluso un campo ) es recursiva constante. ^{[ cita requerida ]} ${\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 )}$

Otros ejemplos

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

No-ejemplos

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

La sucesión de Catalan no es recursiva 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). ${\displaystyle 1,1,2,5,14,42,132,\ldots }$

Definiciones equivalentes

En términos de matrices

Definición de la secuencia de Fibonacci utilizando matrices.

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

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

donde es un vector, es una matriz y es un vector, donde los elementos provienen del mismo dominio (números enteros, números racionales, números algebraicos, números reales o números complejos) que la secuencia original. Específicamente, pueden tomarse como los primeros valores de la secuencia, la transformación lineal que calcula a partir de y el vector . ^[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]}$

En términos de recurrencias lineales no homogéneas

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

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

donde es una constante adicional. Cualquier secuencia que satisfaga una recurrencia lineal no homogénea es recursiva constante. Esto se debe a que al restar la ecuación para de la ecuación para se obtiene una recurrencia homogénea para , de la que podemos resolver para obtener ^{[ cita requerida ]} ${\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}}}$

En términos de funciones generadoras

Definición de la secuencia de Fibonacci utilizando una función generadora.

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 , donde y son polinomios y . ^[3] Además, el orden de la secuencia es el mínimo tal que tiene una forma con y . ^[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}$

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 debe ser un polinomio no divisible por (y en particular distinto de cero). ${\displaystyle q(x)}$ ${\displaystyle x}$

En términos de espacios de secuencia

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

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

${\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, está contenido en un subespacio de dimensión finita de cerrado bajo el operador de desplazamiento a la izquierda . ^{[16] [17]} ${\displaystyle (s_{n})_{n=0}^{\infty }}$ ${\displaystyle \mathbb {C} ^{\mathbb {N} }}$

Esta caracterización se debe a que la relación de orden-recurrencia lineal puede entenderse como una prueba de dependencia lineal entre las secuencias para . Una extensión de este argumento muestra que el orden de la secuencia es igual a la dimensión del espacio de secuencia generado por para todo . ^{[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}$

Caracterización de forma cerrada

Caracterización en forma cerrada de la secuencia de Fibonacci ( fórmula de Binet )

Las secuencias recursivas constantes admiten la siguiente caracterización única en forma cerrada utilizando polinomios exponenciales : cada secuencia recursiva constante se puede escribir en la forma

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

para todos , donde ${\displaystyle n\geq 0}$

• El término es una secuencia que es cero para todos (donde es el orden de la secuencia); ${\displaystyle z_{n}}$ ${\displaystyle n\geq d}$ ${\displaystyle d}$
• Los términos son polinomios complejos; y ${\displaystyle k_{1}(n),k_{2}(n),\ldots ,k_{e}(n)}$
• Los términos son constantes complejas distintas. ^{[19] [3]} ${\displaystyle r_{1},r_{2},\ldots ,r_{k}}$

Esta caracterización es exacta: toda secuencia de números complejos que pueda escribirse en la forma anterior es constante-recursiva. ^[20]

Por ejemplo, el número de Fibonacci se escribe de esta forma utilizando la fórmula de Binet : ^[21] ${\displaystyle F_{n}}$

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

donde es la proporción áurea y . Estas son las raíces de la ecuación . En este caso, , para todos , son ambos polinomios constantes, , y . ${\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 }$

El término sólo es necesario cuando ; si , entonces corrige el hecho de que algunos valores iniciales pueden ser excepciones a la recurrencia general. En particular, para todos . ^{[ cita requerida ]} ${\displaystyle z_{n}}$ ${\displaystyle c_{d}\neq 0}$ ${\displaystyle c_{d}=0}$ ${\displaystyle z_{n}=0}$ ${\displaystyle n\geq d}$

Los números complejos son las raíces del polinomio característico de la recurrencia: ${\displaystyle r_{1},\ldots ,r_{n}}$

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

cuyos coeficientes son los mismos que los de la recurrencia. ^[22] Llamamos raíces características de la recurrencia. Si la secuencia consta de números enteros o racionales, las raíces serán números algebraicos . Si las raíces son todas distintas, entonces los polinomios son todos constantes, lo que se puede determinar a partir de los valores iniciales de la secuencia. Si las raíces del polinomio característico no son distintas, y es una raíz de multiplicidad , entonces en la fórmula tiene grado . Por ejemplo, si el polinomio característico se factoriza como , con la misma raíz r que aparece tres veces, entonces el término n es de la forma ^{[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}.}$

Propiedades del cierre

Ejemplos

La suma de dos secuencias recursivas constantes también es recursiva constante. ^{[25] [26]} Por ejemplo, la suma de y es ( ), que satisface la recurrencia . La nueva recurrencia se puede encontrar sumando las funciones generadoras para cada secuencia. ${\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}}$

De manera similar, el producto de dos secuencias recursivas constantes es recursiva constante. ^[25] Por ejemplo, el producto de y es ( ), que satisface la recurrencia . ${\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}}$

La secuencia de desplazamiento a la izquierda y la secuencia de desplazamiento a la derecha (con ) son recursivas constantes porque satisfacen la misma relación de recurrencia. Por ejemplo, como es recursiva constante, también lo es . ${\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}}$

Lista de operaciones

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

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

Comportamiento

Problema sin resolver en matemáticas :

¿Existe un algoritmo para probar si una secuencia recursiva constante tiene un cero?

(más problemas sin resolver en matemáticas)

Ceros

A pesar de satisfacer una fórmula local simple, una secuencia recursiva constante puede exhibir un comportamiento global complicado. Definamos un cero de una secuencia recursiva constante como un entero no negativo tal que . El teorema de Skolem-Mahler-Lech establece que los ceros de la secuencia se repiten eventualmente: existen constantes y tales que para todo , si y solo si . 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] ${\displaystyle n}$ ${\displaystyle s_{n}=0}$ ${\displaystyle M}$ ${\displaystyle N}$ ${\displaystyle n>M}$ ${\displaystyle s_{n}=0}$ ${\displaystyle s_{n+N}=0}$

Problemas de decisión

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 debe recibir una descripción finita ; esto puede hacerse si la secuencia está sobre números enteros o racionales, o incluso sobre números algebraicos. ^[11] Dada una codificación de este tipo para secuencias , se pueden estudiar los siguientes problemas: ${\displaystyle s_{n}}$ ${\displaystyle s_{n}}$

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

El teorema de Skolem-Mahler-Lech proporcionaría respuestas a algunas de estas preguntas, excepto que su prueba no es constructiva . Establece que para todos los , los ceros se repiten; sin embargo, no se sabe que el valor de 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 es computable. ^{[11] [32]} Es por esto que el problema de los infinitos ceros es decidible: solo determine si el patrón que se repite infinitamente está vacío. ${\displaystyle n>M}$ ${\displaystyle M}$ ${\displaystyle n>M}$

Los resultados de decidibilidad se conocen cuando el orden de una secuencia se restringe a un número 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 de números enteros reversibles de orden hasta 7, es decir, secuencias que pueden continuar hacia atrás en los números enteros. ^[31]

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

Degeneración

Sean las raíces características de una sucesión recursiva constante . Decimos que la sucesión es degenerada si cualquier razón es raíz de la unidad, para . A menudo es más fácil estudiar sucesiones no degeneradas, en cierto sentido se puede reducir a esto utilizando el siguiente teorema: si tiene orden y está contenido en un cuerpo de números de grado sobre , entonces existe una constante ${\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}}}$

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

Generalizaciones

Una secuencia D-finita u holonómica es una generalización natural donde se permite que los coeficientes de la recurrencia sean funciones polinómicas de en lugar de constantes. ^[38] ${\displaystyle n}$

Una secuencia -regular satisface una recurrencia lineal con coeficientes constantes, pero las recurrencias toman una forma diferente. En lugar de ser una combinación lineal de para algunos números enteros que están cerca de , cada término en una secuencia -regular es una combinación lineal de para algunos números enteros cuyas representaciones base - están cerca de la de . ^[39] Las secuencias recursivas constantes pueden considerarse como secuencias -regulares, donde la representación base 1 de consiste en copias del dígito . ^{[ cita requerida ]} ${\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}$

Notas

1. Kauers y Paule 2010, pág. 63.
2. Kauers & Paule 2010, pág. 70.
3. Stanley 2011, pág. 464.
4. Kauers y Paule 2010, pág. 66.
5. Halava, Vesa; Harju, Tero; Hirvensalo, Mika; Karhumäki, Juhani (2005). "El problema de Skolem: en la frontera entre la decidibilidad y la indecidibilidad". pag. 1. CiteSeerX  10.1.1.155.2606 .
6. "Índice de OEIS: Sección Rec - OeisWiki". oeis.org . Consultado el 18 de abril de 2024 .
7. Boyadzhiev, Boyad (2012). "Encuentros cercanos con los números de Stirling del segundo tipo" (PDF) . Math. Mag . 85 (4): 252–266. arXiv : 1806.09468 . doi :10.4169/math.mag.85.4.252. S2CID  115176876.
8. Riordan, John (1964). "Relaciones inversas e identidades combinatorias". The American Mathematical Monthly . 71 (5): 485–498. doi :10.1080/00029890.1964.11992269. ISSN  0002-9890.
9. Jordan, Charles; Jordán, Károly (1965). Cálculo de diferencias finitas. American Mathematical Soc., págs. 9-11. ISBN 978-0-8284-0033-6.Véase la fórmula en la página 9, arriba.
10. Kauers y Paule 2010, pág. 81.
11. Ouaknine, Joël; Worrell, James (2012). "Problemas de decisión para secuencias de recurrencia lineal". Problemas de accesibilidad: 6.º taller internacional, RP 2012, Burdeos, Francia, 17-19 de septiembre de 2012, Actas . Apuntes de clase en informática. Vol. 7550. Heidelberg: Springer-Verlag. págs. 21-28. doi :10.1007/978-3-642-33512-9_3. ISBN . 978-3-642-33511-2.Señor 3040104  ..
12. Stanley 2011, págs. 464–465.
13. Martino, Ivan; Martino, Luca (14 de noviembre de 2013). "Sobre la variedad de recurrencias lineales y semigrupos numéricos". Semigroup Forum . 88 (3): 569–574. arXiv : 1207.0111 . doi :10.1007/s00233-013-9551-2. ISSN  0037-1912. S2CID  119625519.
14. Kauers y Paule 2010, pág. 74.
15. Stanley 2011, págs. 468-469.
16. Kauers y Paule 2010, pág. 67.
17. Stanley 2011, pág. 465.
18. Kauers y Paule 2010, pág. 69.
19. Brousseau 1971, págs. 28-34, Lección 5.
20. Kauers y Paule 2010, págs. 68–70.
21. Brousseau 1971, pag. 16, Lección 3.
22. Brousseau 1971, pag. 28, Lección 5.
23. Greene, Daniel H.; Knuth, Donald E. (1982). "2.1.1 Coeficientes constantes – A) Ecuaciones homogéneas". Matemáticas para el análisis de algoritmos (2.ª ed.). Birkhäuser. pág. 17..
24. Brousseau 1971, págs. 29-31, Lección 5.
25. Kauers y Paule 2010, pág. 71.
26. Brousseau 1971, pag. 37, Lección 6.
27. Stanley 2011, págs. 471.
28. Pohlen, Timo (2009). "El producto de Hadamard y la serie de potencias universales" (PDF) . Universidad de Trier (tesis doctoral) : 36–37.
29. Véase producto (serie) de Hadamard y teorema de Parseval .
30. Lech, C. (1953). "Una nota sobre las series recurrentes". Arkiv för Matematik . 2 (5): 417–421. Código bibliográfico : 1953ArM.....2..417L. doi : 10.1007/bf02590997 .
31. Lipton, Richard; Luca, Florian; Nieuwveld, Joris; Ouaknine, Joël; Purser, David; Worrell, James (4 de agosto de 2022). "Sobre el problema de Skolem y la conjetura de Skolem". Actas del 37.º Simposio anual ACM/IEEE sobre lógica en informática . LICS '22. Nueva York, NY, EE. UU.: Association for Computing Machinery. págs. 1–9. doi :10.1145/3531130.3533328. ISBN 978-1-4503-9351-5.
32. Berstel, Jean; Mignotte, Mauricio (1976). "Deux propriétés décidables des suites récurrentes linéaires". Bulletin de la Société Mathématique de France (en francés). 104 : 175–184. doi : 10.24033/bsmf.1823 .
33. Vereshchagin, NK (1 de agosto de 1985). "Aparición del cero en una secuencia recursiva lineal". Notas matemáticas de la Academia de Ciencias de la URSS . 38 (2): 609–615. doi :10.1007/BF01156238. ISSN  1573-8876.
34. Tijdeman, R.; Mignotte, M.; Shorey, TN (1984). "La distancia entre términos de una secuencia de recurrencia algebraica". Journal für die reine und angewandte Mathematik . 349 : 63–76. ISSN  0075-4102.
35. Bacik, Piotr (2 de septiembre de 2024). "Completando la imagen del problema de Skolem en secuencias de recurrencia lineal de orden 4". arXiv : 2409.01221 [cs.FL].
36. Bilu, Yuri; Luca, Florián; Nieuwveld, Joris; Ouaknine, Joël; Sobrecargo, David; Worrell, James (28 de abril de 2022). "Skolem se encuentra con Schanuel". arXiv : 2204.13417 [cs.LO].
37. Everest, Graham, ed. (2003). Secuencias de recurrencia . Encuestas y monografías matemáticas. Providence, RI: American Mathematical Society. p. 5. ISBN 978-0-8218-3387-2.
38. Stanley, Richard P (1980). "Series de potencias finitas diferenciables". Revista Europea de Combinatoria . 1 (2): 175–188. doi :10.1016/S0195-6698(80)80051-5.
39. Allouche, Jean-Paul; Shallit, Jeffrey (1992). "El anillo de secuencias k-regulares". Ciencias de la Computación Teórica . 98 (2): 163–197. doi :10.1016/0304-3975(92)90001-V.

Referencias

• Brousseau, Alfred (1971). Recursión lineal y sucesiones de Fibonacci. Asociación de Fibonacci.
• Kauers, Manuel; Paule, Peter (2010). El tetraedro concreto: sumas simbólicas, ecuaciones de recurrencia, funciones generadoras, estimaciones asintóticas. Springer Vienna. p. 66. ISBN 978-3-7091-0444-6.
• Stanley, Richard P. (2011). Combinatoria enumerativa (PDF) . Vol. 1 (2.ª ed.). Estudios de Cambridge sobre matemáticas avanzadas.

Enlaces externos

• "Índice OEIS Rec". Índice OEIS de unos pocos miles de ejemplos de recurrencias lineales, ordenados por orden (número de términos) y firma (vector de valores de los coeficientes constantes)