Secuencia recurrente lineal

Una secuencia recurrente lineal ( recurrencia lineal ) es cualquier secuencia numérica definida por una relación de recurrencia lineal : ${\ estilo de visualización x_ {0}, x_ {1}, \ puntos}$

{\displaystyle x_{n}=a_{1}\cdot x_{n-1}+\dots +a_{d}\cdot x_{nd))

para todos

{\ Displaystyle n \ geqslant d}

con términos iniciales dados , donde d es un número natural fijo , se dan coeficientes numéricos, . En este caso, el número d se llama el orden de la secuencia. ${\displaystyle x_{0},\puntos,x_{d-1))$ $a_{1},\puntos,a_{d}$ $a_{d}\neq 0$

Las secuencias recurrentes lineales a veces también se denominan secuencias recurrentes .

La teoría de las sucesiones lineales recurrentes es un análogo exacto de la teoría de las ecuaciones diferenciales lineales con coeficientes constantes .

Ejemplos

Los casos particulares de secuencias recurrentes lineales son secuencias:

Secuencias de Lucas que satisfacen en particular: ${\displaystyle x_{n}=P\cdot x_{n-1}-Q\cdot x_{n-2))$
- progresiones aritméticas con ; ${\ estilo de visualización (P, Q) = (2,1)}$
- progresión geométrica con ; ${\ estilo de visualización Q = 0}$
- Números de Fibonacci con ; ${\ estilo de visualización (P, Q) = (1, -1)}$
- Lucas numera con ; ${\ estilo de visualización (P, Q) = (1, -1)}$
números tribonacci satisfactorios . ${\displaystyle x_{n}=x_{n-1}+x_{n-2}+x_{n-3))$

Fórmula de término general

Para sucesiones lineales recurrentes, existe una fórmula que expresa el término común de la sucesión en términos de las raíces de su polinomio característico

\lambda ^{d}-a_{1}\lambda ^{d-1}-\dots -a_{d-1}\lambda -a_{d}.

Es decir, el término común se expresa como una combinación lineal de secuencias de la forma $d$

x_{n}=\lambda_{k}^{n}\cdot n^{m},

donde es la raíz del polinomio característico y es un entero no negativo menor que la multiplicidad de . $\lambda_k$ $metro$ $\lambda_k$

Para los números de Fibonacci, dicha fórmula es la fórmula de Binet .

Ejemplo

Para encontrar la fórmula del término común de la sucesión que satisface la ecuación recurrente lineal de segundo orden con valores iniciales , se debe resolver la ecuación característica $F_{n}$ ${\displaystyle F_{n}=b\cdot F_{n-1}+c\cdot F_{n-2))$ $F_{1}$ $F_{2}$

q^{2}-bq-c=0

Si la ecuación tiene dos raíces distintas de cero y , entonces para constantes arbitrarias y , la sucesión $q_{1}$ $q_{2}$ $A$ $B$

F_{n}=A\cdot q_{1}^{n}+B\cdot q_{2}^{n},

satisface la relación de recurrencia; queda encontrar los números y eso $A$ $B$

{\displaystyle F_{1}=A\cdot q_{1}+B\cdot q_{2))

y .

F_{2}=A\cdot q_{1}^{2}+B\cdot q_{2}^{2}

Si el discriminante de la ecuación característica es igual a cero y, por lo tanto, la ecuación tiene una sola raíz , entonces para constantes arbitrarias y , la sucesión $q_{1}$ $A$ $B$

{\displaystyle F_{n}=(A+B\cdot n)\cdot q_{1}^{n))

satisface la relación de recurrencia; queda encontrar los números y eso $A$ $B$

F_{1}=(A+B)\cdot q_{1}

y .

F_{2}=(A+B\cdot 2)\cdot q_{1}^{2}

En particular, para la sucesión definida por la siguiente ecuación lineal recurrente de segundo orden

F_{n}=5\cdot F_{n-1}-6\cdot F_{n-2}

; , .

{\ estilo de visualización F_ {1} = 1}

{\ estilo de visualización F_ {2} = -2}

las raíces de la ecuación característica son , . Es por eso $q^{2}-5\cdot q+6=0$ ${\ estilo de visualización q_ {1} = 2}$ ${\ estilo de visualización q_ {2} = 3}$

F_{n}=-2\cdot (3^{n-1}-2^{n-1})-6\cdot (3^{n-2}-2^{n-2}) .

Finalmente:

F_{n}=5\cdot 2^{n-1}-4\cdot 3^{n-1}.

Aplicaciones

Las secuencias recurrentes lineales sobre anillos de residuos se utilizan tradicionalmente para generar números pseudoaleatorios .

Historia

Los fundamentos de la teoría de las sucesiones lineales recurrentes fueron dados en los años veinte del siglo XVIII por Abraham de Moivre y Daniel Bernoulli . Leonhard Euler lo expuso en el capítulo trece de su Introducción al análisis de los infinitesimales (1748). [1] Más tarde , Pafnuty Lvovich Chebyshev y aún más tarde Andrey Andreevich Markov presentaron esta teoría en sus cursos sobre el cálculo de diferencias finitas. [2] [3]

Véase también

Notas

↑ L. Euler, Introducción al análisis de los infinitesimales, volumen I, M. - L., 1936, págs. 197–218
↑ P. L. Chebyshev, Theory of Probability, conferencias 1879–1880, M. - L., 1936, págs. 139–147
↑ A. A. Markov, Cálculo de diferencias finitas, 2.ª ed., Odessa, 1910, págs. 209–239

Literatura

A. I. Markushevich . secuencias de retorno . - Sra. Editorial de Literatura Técnica y Teórica, 1950. - Vol. 1. - ( Lecciones populares de matemáticas ).
M. M. Glukhov, V. P. Elizarov, A. A. Nechaev. Capítulo XXV. Sucesiones lineales recurrentes // Álgebra. - Libro de texto. En 2 tomos. - M. : Helios ARV, 2003. - T. 2. - ISBN 8-85438-072-2 .
A. Egórov. Números pisot // Kvant . - 2005. - Nº 5 . - S. 8-13 .
Chebrakov Yu. V. Capítulo 2.7. Ecuaciones recurrentes // Teoría de matrices mágicas. Lanzamiento de TMM-1 . - San Petersburgo. , 2010.

Secuencias y filas
Secuencias	Secuencia numérica Secuencia fundamental Secuencia recurrente lineal números de Fibonacci números rizados Factorial Secuencia de ladrón secuencia de bruijn
Filas, básico	Suma de fila El resto de la fila Convergencia Condicional serie alterna Fila multisección
Series numéricas ( operaciones con series numéricas )	serie armónica Serie de Leibniz Una serie de cuadrados inversos. Una serie de números primos recíprocos. Fila de Dirichlet serie Mercator Fila Grandi 1 - 2 + 3 - 4 + ... 1 + 2 + 3 + 4 + ...
filas funcionales	Serie Taylor serie laurent series de Fourier Serie trigonométrica de Fourier serie trigonométrica serie de salchichas
Otros tipos de fila	serie de Neumann Fila de puiseux