Es bien sabido que si las recurrencias lineales$u_n$ y$v_n$ tienen polinomios característicos$K_u$ y$K_v$, entonces$u_n + v_n$ tiene el polinomio característico$K_u K_v$. ¿Es cierto lo contrario? Si mis factores polinomiales característicos como$K_u K_v$, entonces ¿puedo encontrar$u_n$ y$v_n$ de tal manera que mi recurrencia se pueda escribir como$u_n + v_n$?
Respuesta
¿Demasiados anuncios?
jlleblanc
Puntos
2957
Por el bien de cierre, permítanme ampliar mis comentarios en una respuesta.
La respuesta es "no"; pero se convierte en un "sí" si asumimos $K_{u}$ $K_{v}$ para ser coprime. Antes de empezar la prueba, permítanme presentarles a mi propia notación, que yo creo que es más claro que el tuyo (en concreto, voy a evitar el uso de la nebulosa noción de una "recurrencia lineal" y la facilidad palabra malentendida "polinomio característico").
Arreglar un campo de $F$. Set $\mathbb{N}=\left\{ 0,1,2,\ldots\right\} $. Vamos $F^{\infty}$ el conjunto $\left\{ \left( a_{0},a_{1},a_{2},\ldots\right) \ \mid\ a_{i}\F\text{ para cada uno de los }i\in\mathbb{N}\right\} $ de todos infinito secuencias de elementos de $F$. Este conjunto $F^{\infty}$ $F$- espacio vectorial (donde las operaciones son entrywise: por ejemplo, tenemos $\left( a_{0},a_{1} ,a_{2},\ldots\right) +\left( b_{0},b_{1},b_{2},\ldots\right) =\left( a_{0}+b_{0},a_{1}+b_{1},a_{2}+b_{2},\ldots\right) $).
Definición. Deje $P\in F\left[ X\right] $ ser un polinomio. Escribir $P$ en la forma $P=\sum\limits_{i=0}^{k}p_{i}X^{i}$ algunos $k\in\mathbb{N}$ y algunos $p_{0},p_{1},\ldots,p_{k}\in F$.
Deje $\mathbf{a}=\left( a_{0},a_{1},a_{2},\ldots\right) \in F^{\infty}$ ser un de la secuencia. Entonces, podemos decir que la secuencia de $\mathbf{a}$ $P$-linealmente recursiva si y sólo si cada una de las $n\in\mathbb{N}$ satisface $\sum\limits_{i=0} ^{k}p_{i}a_{n+i}=0$. (Observe que esta definición no depende de cómo precisamente representamos $P$ en la forma $\sum\limits_{i=0}^{k}p_{i}X^{i}$; de hecho, cualquiera de las dos representaciones difieren sólo en cero sumandos, y estos cero sumandos no altera la suma $\sum\limits_{i=0}^{k}p_{i}a_{n+i}$.)
(Mi concepto de un "$P$-lineal recursiva de la secuencia" corresponde aproximadamente a su "recursiva secuencia con polinomio característico $P$", pero hay que tener en cuenta que $P$ no se determina únicamente por la secuencia. Por ejemplo, cada una de las $X$-linealmente recursiva de la secuencia también es $X^{2}$-lineal recursiva.)
Teorema 1. Deje $P$ $Q$ ser entre dos polinómios coprimos en la principal ideal dominio $F\left[ X\right] $. Deje $\mathbf{a}\in F^{\infty}$ ser un $PQ$-lineal recursiva de la secuencia. A continuación, $\mathbf{a}$ es la suma de un $P$-lineal recursiva de la secuencia con un $Q$-lineal recursiva de la secuencia.
Antes de demostrar el Teorema 1, se introduce un útil $F\left[ X\right] $-módulo de estructura en $F^{\infty}$. Es decir, vamos a $S$ $F$- lineal mapa
$F^{\infty}\rightarrow F^{\infty},\ \izquierdo( a_{0},a_{1},a_{2},\ldots\right) \mapsto\left( a_{1},a_{2},a_{3},\ldots\right) $.
Este mapa $S$ se llama el operador de desplazamiento (ya que cambia la dirección de una secuencia $1$ hacia adelante, dejando caer la primera entrada). Es fácil ver que
(1) $S^{i}\left( a_{0},a_{1},a_{2},\ldots\right) =\left( a_{0+i} ,a_{1+i},a_{2+i},\ldots\right) $
para cada una de las $i\in\mathbb{N}$ e cada $\left( a_{0},a_{1},a_{2},\ldots\right) \F^{\infty}$.
Deje $\operatorname*{End}\left( F^{\infty}\right) $ el valor del $F$-álgebra de todos endomorphisms de la $F$-espacio vectorial $F^{\infty}$. Por el universal propiedad del polinomio anillo de $F\left[ X\right] $, no existe un único $F$-álgebra homomorphism $\phi:F\left[ X\right] \rightarrow \operatorname*{End}\left( F^{\infty}\right) $ satisfying $\phi\left( X\right) =S$. Consider this $\phi$, and use it to make $F^{\infty}$ en un $F\left[ X\right] $-módulo. Por lo tanto, esta $F\left[ X\right] $-módulo de estructura en $F^{\infty}$ satisface $X\mathbf{a}=\underbrace{\phi\left( X\right) }_{=S}\mathbf{a}=\mathbf{a}$ for each $\mathbf{a}\in F^{\infty}$. Ahora podemos fácilmente describir cómo cualquier polinomio de actos en $F^{\infty}$:
Proposición 2. Deje $P\in F\left[ X\right] $ ser un polinomio. Escribir $P$ en el formulario de $P=\sum\limits_{i=0}^{k}p_{i}X^{i}$ algunos $k\in\mathbb{N}$ y algunos $p_{0},p_{1},\ldots,p_{k}\in F$.
Deje $\mathbf{a}=\left( a_{0},a_{1},a_{2},\ldots\right) \in F^{\infty}$ ser un de la secuencia. Entonces, P $\mathbf{a}=\left( \sum\limits_{i=0}^{k}p_{i}a_{0+i} ,\sum\limits_{i=0}^{k}p_{i}a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i} ,\ldots\right) $.
La prueba de la Proposición 2. Tenemos $\mathbf{a}=\left( a_{0},a_{1},a_{2} ,\ldots\right) $. Hence, each $i\in\mathbb{N}$ satisface
(2) $S^{i}\mathbf{a}=S^{i}\left( a_{0},a_{1},a_{2},\ldots\right) =\left( a_{0+i},a_{1+i},a_{2+i},\ldots\right) $
(por (1)). Por otro lado, la aplicación del mapa de $\phi$ a la igualdad $P=\sum\limits_{i=0}^{k}p_{i}X^{i}$, obtenemos
$\phi\left( P\right) =\phi\left( \sum\limits_{i=0}^{k}p_{i}X^{i}\right) =\sum\limits_{i=0}^{k}p_{i}\phi\left( X\right) ^{i}$ (since $\phi$ es un $F$-álgebra homomorphism)
$=\sum\limits_{i=0}^{k}p_{i}S^{i}$ (desde $\phi\left( X\right) =S$).
Pero la definición de la $F\left[ X\right] $-módulo de estructura en $F^{\infty}$ muestra que
P $\mathbf{a}=\underbrace{\phi\left( P\right) }_{=\sum\limits_{i=0}^{k} p_{i}S^{i}}\mathbf{a}=\sum\limits_{i=0}^{k}p_{i}\underbrace{S^{i}\mathbf{a} }_{\substack{=\left( a_{0+i},a_{1+i},a_{2+i},\ldots\right) \\\text{(por (2))}}}$
$=\sum\limits_{i=0}^{k}p_{i}\left( a_{0+i},a_{1+i},a_{2+i},\ldots\right) =\left( \sum\limits_{i=0}^{k}p_{i}a_{0+i},\sum\limits_{i=0}^{k}p_{i} a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i},\ldots\right) $.
Esto demuestra la Proposición 2.
Corolario 3. Deje $P\in F\left[ X\right] $ ser un polinomio. Vamos $\mathbf{a}\in F^{\infty}$ ser una secuencia. A continuación, $\mathbf{a}$ $P$- linealmente recursiva si y sólo si $P\mathbf{a}=0$.
La prueba del Corolario 3. Escribir $P$ en el formulario $P=\sum\limits_{i=0}^{k} p_{i}X^{i}$ for some $k\in\mathbb{N}$ and some $p_{0},p_{1},\ldots,p_{k}\en F$. Write the sequence $\mathbf{a}\in F^{\infty}$ in the form $\mathbf{a} =\left( a_{0},a_{1},a_{2},\ldots\right) $. Así, la Proposición 2 rendimientos P $\mathbf{a}=\left( \sum\limits_{i=0}^{k}p_{i}a_{0+i},\sum\limits_{i=0} ^{k}p_{i}a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i},\ldots\right) $. Por lo tanto, se tenemos la siguiente cadena de equivalencias:
$\left( P\mathbf{a}=0\right) $
$\Longleftrightarrow\ \izquierdo( \left( \sum\limits_{i=0}^{k}p_{i}a_{0+i} ,\sum\limits_{i=0}^{k}p_{i}a_{1+i},\sum\limits_{i=0}^{k}p_{i}a_{2+i} ,\ldots\right) =0\right) $
$\Longleftrightarrow\ \izquierdo( \text{cada uno de los }n\in\mathbb{N}\text{ satisface } \sum\limits_{i=0}^{k}p_{i}a_{n+i}=0\right) $
$\Longleftrightarrow\ \izquierdo( \mathbf{a}\text{ es }P\text{-linealmente recursiva}\right) $
(por la definición de "$P$-lineal recursivo"). Esto demuestra Corolario 3.
La prueba del Teorema 1. Desde $F\left[ X\right] $ es un director ideal de dominio, La identidad de Bezout muestra que hay dos polinomios $U\in F\left[ X\right] $ y $V\in F\left[ X\right] $ tal que $PU+QV=\gcd\left( P,Q\right) $. Considerar estos $U$$V$. Por lo tanto, $PU+QV=\gcd\left( P,Q\right) =1$ (desde $P$ $Q$ son coprime).
Corolario 3 (aplicado a $PQ$ en lugar de $P$) muestra que el $\mathbf{a}$ es $PQ$-lineal recursiva si y sólo si $PQ\mathbf{a}=0$. Por lo tanto, $PQ\mathbf{a} =0$ (since $\mathbf{a}$ is $PQ$lineal recursivo).
La secuencia de $PU\mathbf{a}\in F^{\infty}$ satisface $Q\left( PU\mathbf{a} \right) =\underbrace{QPU}_{=UPQ}\mathbf{a}=U\underbrace{PQ\mathbf{a}}_{y=0} =0$. But Corollary 3 (applied to $P$ and $PU\mathbf{a}$ instead of $P$ y $\mathbf{a}$) muestra que el $PU\mathbf{a}$ $Q$- lineal recursiva si y sólo si $Q\left( PU\mathbf{a}\right) =0$. Por lo tanto, $PU\mathbf{a}$ $Q$- linealmente recursivo (desde $Q\left( PU\mathbf{a}\right) =0$).
La secuencia de $QV\mathbf{a}\in F^{\infty}$ satisface P $\left( QV\mathbf{a} \right) =\underbrace{PQV}_{=VPQ}\mathbf{a}=V\underbrace{PQ\mathbf{a}}_{y=0} =0$. But Corollary 3 (applied to $QV\mathbf{a}$ instead of $\mathbf{a}$) muestra que $QV\mathbf{a}$ $P$- lineal recursiva si y sólo si $P\left( QV\mathbf{a}\right) =0$. Thus, $QV\mathbf{a}$ is $P$lineal recursiva (desde $P\left( QV\mathbf{a}\right) =0$).
Ahora, $PU\mathbf{a}+QV\mathbf{a}=\underbrace{\left( PU+QV\right) } _{=1}\mathbf{a}=\mathbf{a}$. Hence, $\mathbf{a}=PU\mathbf{a}+QV\mathbf{a} =QV\mathbf{a}+PU\mathbf{a}$ is the sum of a $P$lineal recursiva de la secuencia (es decir, $QV\mathbf{a}$) $Q$- lineal recursiva de la secuencia (es decir, $PU\mathbf{a}$). Esto demuestra el Teorema 1.
Observe que el Teorema 1 se da un enfoque alternativo para explícita fórmulas para lineal recursiva secuencias (como la fórmula de Binet para los números de Fibonacci). De hecho, la aplicación repetida del Teorema 1 se obtiene el siguiente corolario:
Corolario 4. Deje $P\in F\left[ X\right] $ ser un monic polinomio. Vamos $P=\prod\limits_{i=1}^{k}P_{i}^{m_{i}}$ ser la factorización de $P$ a monic irreductible polinomios (con $P_{1},P_{2},\ldots,P_{k}$ siendo distintos monic irreductible polinomios, y $m_{1},m_{2},\ldots,m_{k}$ ser no negativo enteros). Deje $\mathbf{a}\in F^{\infty}$ $P$- lineal recursiva de la secuencia. A continuación, $\mathbf{a}$ puede ser escrita en la forma $\mathbf{a} =\mathbf{a}_{1}+\mathbf{a}_{2}+\cdots+\mathbf{a}_{k}$, donde cada $\mathbf{a}_{i}$ $P_{i}^{m_{i}}$- lineal recursiva de la secuencia.
Por ejemplo, si $F=\mathbb{C}$$P=X^{2}-X-1$, entonces podemos aplicar el Corolario 4 para cualquier $P$-lineal recursiva de la secuencia (ajuste $k=2$, $P_{1}=X-\dfrac {1+\sqrt{5}}{2}$, $m_{1}=1$, $P_{2}=X-\dfrac{1-\sqrt{5}}{2}$, and $m_{2}=1$). Por lo tanto la conclusión de que cada una de las $\left( X^{2}-X-1\right) $-lineal recursiva la secuencia puede ser escrito como la suma de $\left( X-\dfrac{1+\sqrt{5}} {2}\right) $-lineal recursiva de la secuencia (es decir, una progresión geométrica relación $\dfrac{1+\sqrt{5}}{2}$) con un $\left( X-\dfrac{1-\sqrt{5}} {2}\right) $-lineal recursiva de la secuencia (es decir, una progresión geométrica relación $\dfrac{1-\sqrt{5}}{2}$). Esto le permite probar fácilmente que la fórmula de Binet para la secuencia de Fibonacci. En general, puede que tenga que trabajar más duro (especialmente si $P$ no es squarefree, por lo que algunas de las $m_{i}$$>1$).
Observe también que el Teorema 1 no se sostiene si nos olvidamos de exigir que $P$ y $Q$ ser coprime. Por ejemplo, la secuencia de $\left( 0,1,2,\ldots\right) $ es siempre $\left( X-1\right) ^{2}$-lineal recursiva, pero no puede ser escrito como una suma de dos $\left( X-1\right) $-lineal recursiva secuencias. (De hecho, el $\left( X-1\right) ^{2}$-lineal recursiva secuencias de la aritmética secuencias, mientras que el $\left( X-1\right) $-lineal recursiva secuencias son la constante de secuencias.) Sospecho que hay un contraejemplo para cada par $\left( P,Q\right) $ de los no-coprime polinomios $P$$Q$, al menos al $F$ tiene características de las $0$.
