Secuencia recurrente lineal

En matemáticas , llamamos secuencia recurrente lineal de orden p a cualquier secuencia con valores en un campo conmutativo K (por ejemplo ℝ o ℂ ; solo nos ubicaremos en este caso en este artículo) definida para todos por una relación de recurrencia lineal de la forma $n \ geq n_ {0}$

{\ Displaystyle \ forall n \ geq n_ {0} \ quad u_ {n + p} = a_ {0} u_ {n} + a_ {1} u_ {n + 1} + \ cdots + a_ {p-1} u_ {n + p-1}}

donde , , ... son p conjunto escalar de K ( distinto de cero). $a_0$ $a_1$ $a _ {{p-1}}$ $a_0$

Tal secuencia está completamente determinada por los datos de sus p primeros términos y por la relación de recurrencia.

Las secuencias lineales recurrentes de orden 1 son las secuencias geométricas .

El estudio de secuencias recurrentes lineales de orden superior se reduce a un problema de álgebra lineal . La expresión del término general de tal secuencia es posible siempre que se pueda factorizar un polinomio asociado a ella, llamado polinomio característico; el polinomio característico asociado con una secuencia que satisface la relación de recurrencia anterior es:

P (X) = X ^ {p} - \ sum _ {{i = 0}} ^ {{p-1}} a_ {i} X ^ {i} = X ^ {p} -a _ {{p - 1}} X ^ {{p-1}} - a _ {{p-2}} X ^ {{p-2}} - \ dots -a_ {1} X-a_ {0}.

Por tanto, su grado es igual al orden de la relación de recurrencia. En particular, en el caso de secuencias de orden 2, el polinomio es de grado 2 y, por tanto, puede factorizarse mediante un cálculo discriminante . Así, el término general de sucesiones lineales recurrentes de orden 2 se puede expresar usando solo los dos primeros términos, algunos valores constantes, algunas operaciones aritméticas elementales (suma, resta, multiplicación, exponencial) y las funciones seno y coseno (si el campo de escalares es el campo de los reales). Una de las secuencias de este tipo es la famosa secuencia de Fibonacci , que se puede expresar a partir de poderes que involucran la proporción áurea .

Secuencia lineal recurrente de orden 1

Las secuencias lineales recurrentes de orden 1 son las secuencias geométricas .

Si la relación de recurrencia es , el término general es . ${\ Displaystyle u_ {n + 1} = qu_ {n}}$ ${\ Displaystyle u_ {n} = u_ {n_ {0}} q ^ {n-n_ {0}}}$

Secuencia lineal recurrente de orden 2

un y b son dos escalares fijos de K con b no es cero, la relación de recurrencia es

{\ Displaystyle u_ {n + 2} = au_ {n + 1} + bu_ {n} \ quad (R).}

Los escalares r tales que la secuencia satisfaga $($ $R$ $)$ son las soluciones de la ecuación cuadrática . El polinomio se denomina polinomio característico de la secuencia. Su discriminante es . Entonces será necesario distinguir varios casos, según el número de raíces del polinomio característico. ${\ Displaystyle (r ^ {n}) _ {n \ in \ mathbb {N}}}$ ${\ Displaystyle r ^ {2} -ar-b = 0}$ ${\ Displaystyle X ^ {2} -aX-b}$ ${\ Displaystyle \ Delta = a ^ {2} + 4b}$

Teorema : el término general de una secuencia con valores en K y que satisface ( R ) es:

$\ lambda r_ {1} ^ {n} + \ mu r_ {2} ^ {n}$ si y son dos raíces distintas (en K ) del polinomio , $r_1$ $r_2$ $X ^ {2} -aX-b$
$(\ lambda + \ mu n) r_ {0} ^ {n}$ si es doble raíz del polinomio , $r_ {0}$ $X ^ {2} -aX-b$

con parámetros en K determinados por los dos primeros valores de la secuencia. $\ lambda, \ mu$

El caso 1 ocurre, por ejemplo, si y si el discriminante es estrictamente positivo, o si y . Además, si las dos raíces del polinomio son dos complejos conjugados y , entonces el término general de dicha secuencia también se escribe: ${\ Displaystyle K = \ mathbb {R}}$ ${\ Displaystyle \ Delta = a ^ {2} + 4b}$ ${\ Displaystyle K = \ mathbb {C}}$ ${\ Displaystyle \ Delta \ neq 0}$ $r_ {1}, r_ {2}$ $X ^ {2} -aX-b$ ${\ Displaystyle \ rho \ mathrm {e} ^ {\ mathrm {i} \ theta}}$ ${\ Displaystyle \ rho \ mathrm {e} ^ {- \ mathrm {i} \ theta}}$

${\ Displaystyle \ rho ^ {n} (A \ cos (n \ theta) + B \ sin (n \ theta))}$ con los parámetros A y B en K ( o , según nos interesen las secuencias reales o complejas) determinados por los dos primeros valores de la secuencia. ${\ Displaystyle = \ mathbb {R}}$ $\ mathbb {C}$

El caso 2 ocurre cuando y luego la raíz doble es . $\ Delta = 0$ ${\ displaystyle r_ {0} = {\ frac {a} {2}}}$

No perdemos nada en la generalidad de la secuencia suponiendo que ésta se defina sobre todos ℕ y no solo partiendo de . De hecho, el estudio de una secuencia $u$ que se define sólo a partir de se reduce al de la secuencia $v$ definida en ℕ por . $n_ {0}$ $n_ {0}$ $v_ {n} = u _ {{n + n_ {0}}}$

Identidades notables

Si una secuencia $u$ satisface

{\ Displaystyle \ forall n \ in \ mathbb {N} \ quad u_ {n + 2} = au_ {n + 1} + bu_ {n} \ quad (R)}

luego, puede extenderse a índices negativos y relacionarse con las potencias de la matriz (llamada matriz compañera del polinomio característico)

{\ displaystyle P: = {\ begin {pmatrix} a & b \\ 1 & 0 \ end {pmatrix}}}

( invertible desde $b \neq 0$ ) por:

{\ Displaystyle \ forall n \ in \ mathbb {Z} \ quad {\ begin {pmatrix} u_ {n + 1} \\ u_ {n} \ end {pmatrix}} = P ^ {n} {\ begin {pmatrix } u_ {1} \\ u_ {0} \ end {pmatrix}}}

Esto nos permite mostrar que para $v$ igual a $u$ o a cualquier otra secuencia que satisface la misma relación de recurrencia $( R )$ y para todos los números enteros $i$ , $j$ , $k$ , $l$ y $r$ :

{\ Displaystyle i + j = k + l \ Rightarrow u_ {i + r} v_ {j + r} -u_ {k + r} v_ {l + r} = (- b) ^ {r} (u_ {i } v_ {j} -u_ {k} v_ {l})}

En particular :

{\ Displaystyle {\ text {si}} u_ {0} = 0 {\ text {luego}} \ quad \ forall m, n, r \ in \ mathbb {Z} \ quad u_ {n} v_ {m + r } -u_ {r} v_ {m + n} = (- b) ^ {r} u_ {nr} v_ {m}}

Secuencia recurrente de orden $p$

$P-$ subespacio vectorial dimensional

Si llamamos a la relación de recurrencia: $(R_ {p})$

para todo entero n ,

u _ {{n + p}} = a_ {0} u_ {n} + a_ {1} u _ {{n + 1}} + \ cdots + a _ {{p-1}} u _ {{n + p-1}}

y si denotamos el conjunto de secuencias con los valores en K y la satisfacción , se muestra que es un subespacio del espacio de secuencias con valores en K . Esto se debe a la linealidad de la relación de recurrencia. $E _ {{R_ {p}}}$ $(R_ {p})$ $E _ {{R_ {p}}}$

Además, este subespacio es de dimensión p . De hecho, existe un isomorfismo de espacios vectoriales entre y : con cada secuencia $u$ de , asociamos el p -tuplet . Entonces basta con conocer una familia libre de p secuencias de verificación , entonces el conjunto es generado por esta familia libre. $E _ {{R_ {p}}}$ $K ^ {p}$ $E _ {{R_ {p}}}$ $(u_ {0}, u_ {1}, \ cdots, u _ {{p-1}})$ $(R_ {p})$ $E _ {{R_ {p}}}$

Termino general

La búsqueda del término general y las suites específicas se realiza trabajando en . A cada secuencia asociamos la secuencia definida por $K ^ {p}$ $(u_ {n}) _ {{n \ in \ mathbb {N}}}$ ${\ Displaystyle (U_ {n}) _ {n \ in \ mathbb {N}}}$

{\ Displaystyle U_ {n} = {\ begin {pmatrix} u_ {n} \\ u_ {n + 1} \\\ vdots \\ u_ {n + p-1} \ end {pmatrix}}.}

La relación de recurrencia en induce una relación de recurrencia en $(u_ {n}) _ {{n \ in \ mathbb {N}}}$ ${\ Displaystyle (U_ {n}) _ {n \ in \ mathbb {N}}}$

U _ {{n + 1}} = AU_ {n}

A = {\ begin {pmatrix} 0 & 1 & 0 & \ cdots & 0 \\ 0 & 0 & 1 & \ cdots & 0 \\\ vdots & \ ddots & \ ddots & \ cdots & \ vdots \\ 0 & \ cdots & \ cdots & 0 & 1 \\ a_ {0} & a_ {1} & \ cdots & \ cdots & a _ {{p-1}} \ end {pmatrix}}

( A es la matriz acompañante del polinomio característico de la secuencia).

El término general de la secuencia U se determina entonces por

{\ Displaystyle U_ {n} = A ^ {n} U_ {0}.}

Entonces el problema parece haber terminado. Pero la verdadera dificultad consiste entonces en calcular ... Preferimos determinar una base de . $A ^ {n}$ $E _ {{R_ {p}}}$

Busca una base

El polinomio característico de la matriz A es . No es casualidad que lo encontremos para caracterizar las secuencias de verificación . $P (X) = X ^ {p} - \ sum _ {{i = 0}} ^ {{p-1}} a_ {i} X ^ {i}$ ${\ Displaystyle u = (u_ {n}) _ {n \ in \ mathbb {N}}}$ $R_ {p}$

Denotamos por f la transformación lineal que, a una secuencia, asocia la secuencia definida por . La condición " $u$ satisface " resulta entonces en P ( f ) ( $u$ ) = 0. El conjunto es, por lo tanto, el núcleo de P ( f ). Si el polinomio P se divide sobre K (lo que siempre es cierto si K = ℂ), se escribe dónde están las raíces de P y sus respectivos órdenes de multiplicidad. El núcleo de P ( f ) es entonces la suma directa de los núcleos de . Por tanto, es suficiente encontrar una base de cada uno de estos núcleos para determinar una base de . ${\ Displaystyle u = (u_ {n}) _ {n \ in \ mathbb {N}}}$ ${\ Displaystyle v = (v_ {n}) _ {n \ in \ mathbb {N}}}$ $v_ {n} = u _ {{n + 1}}$ $R_ {p}$ $E _ {{R_ {p}}}$ $P = \ prod _ {{i = 1}} ^ {k} (X-r_ {i}) ^ {{\ alpha _ {i}}}$ ${\ Displaystyle r_ {1}, r_ {2}, \ dots, r_ {k}}$ ${\ Displaystyle \ alpha _ {1}, \ alpha _ {2}, \ dots, \ alpha _ {k}}$ $(f-r_ {i} Id) ^ {{\ alpha _ {i}}}$ $E _ {{R_ {p}}}$

Podemos mostrar que cualquier secuencia de términos generales es un elemento del núcleo de siempre que el grado de Q sea estrictamente menor que . Esta demostración se realiza por inducción . Como las secuencias , para j = 0 a , formar una parte libre de elementos, las secuencias , para j de 0 a y i de 1 a k , forman una familia libre de elementos de (de dimensión p ) por lo tanto, una base de . Los elementos de son, por tanto, sumas de sucesiones cuyo término general es con grado de Q estrictamente menor que . $Q (n) r_ {i} ^ {n}$ $(f-r_ {i} Id) ^ {{\ alpha _ {i}}}$ $\ alpha_i$ $\ alpha_i$ ${\ Displaystyle (n ^ {j} r_ {i} ^ {n}) _ {n \ in \ mathbb {N}}}$ ${\ Displaystyle \ alpha _ {i} -1}$ $\ alpha_i$ ${\ Displaystyle (n ^ {j} r_ {i} ^ {n}) _ {n \ in \ mathbb {N}}}$ $\ alpha _ {i} -1$ ${\ Displaystyle \ alpha _ {1} + \ alpha _ {2} + \ cdots + \ alpha _ {k} = p}$ $E _ {{R_ {p}}}$ $E _ {{R_ {p}}}$ $E _ {{R_ {p}}}$ $Q (n) r_ {i} ^ {n}$ $\ alpha_i$

Regresar a la recurrencia de segundo orden

Si el polinomio característico se divide en entonces los polinomios Q son de grado 0 y los elementos de son secuencias cuyo término general es . $(X-r_ {1}) (X-r_ {2})$ $E _ {{R_ {2}}}$ $\ lambda _ {1} r_ {1} ^ {n} + \ lambda _ {2} r_ {2} ^ {n}$

Si el polinomio característico se divide en, entonces los polinomios Q son de grado 1 y los elementos de son secuencias cuyo término general es . $(X-r_ {0}) ^ {2}$ $E _ {{R_ {2}}}$ $(\ lambda _ {1} n + \ lambda _ {2}) r_ {0} ^ {n}$

Notas y referencias

Para una prueba, véase por ejemplo el capítulo "Afín recurrencia de orden 2" en Wikiversidad .
(en) Robert C. Johnson, " Números y matrices de Fibonacci " en la Universidad de Durham ,2009, p. 40 (A.10).
Para ver una demostración, consulte, por ejemplo, el ejercicio corregido correspondiente sobre Wikiversity .
Jean-Marie Monier, Álgebra y geometría PC - PSI - PT : Cursos, métodos y ejercicios corregidos , Dunod ,2008, 5 ª ed. ( leer en línea ) , pág. 125.
En realidad, este resultado solo es cierto si , pero el caso de una raíz cero se trata fácilmente mediante un cambio de índice. $r_ {i} \ neq 0$