Relación de recurrencia

Relación de recurrencia

Saltar a navegación, búsqueda

Definición

Una relación de recurrencia para una sucesión $\{a_0,a_1,a_2,\cdots\, \}$ es una fórmula que expresa cada término $a_n\,$ a partir de cierto $n_0 \in \mathbb{N}\,$, en función de uno o más de los términos que le preceden. Los valores de los términos necesarios para empezar a calcular se llaman condiciones iniciales. Se dice que una sucesión es una solución de la relación de recurrencia si su término general verifica dicha relación.

Ejemplo

Ejemplos particulares de relaciones de recurrencia son las de las formas: $a_n = a_{n-1} + d\,$ (progresión aritmética), $a_n = ra_{n-1}\,$ (progresión geométrica). Sus soluciones son respectivamente, $a_n = a_0 + dn\,$ y $a_n = a_0r^n\,$. Por otra parte uno de los ejemplos más estudiados es la sucesión de Fibonacci que viene dada por: $a_0 = a_1 = 1\,$ y $a_n = a_{n-1} + a_{n-2}\,$ para todo $n\ge2\,$

Relaciones de recurrencia lineales homogéneas

Si $a_n = c_1a_{n-1} + c_2a_{n-2} \cdots + c_ma_{n-m}\,$ para $n\ge m\,$, se dice que la relación de recurrencia es lineal homogénea de orden $m\,$.

Definíción

Llamaremos ecuación característica de la relación de recurrencia $a_n = c_1a_{n-1} + c_2a_{n-2}\,$ a la ecuación $r^2 -c_1r - c_2 = 0\,$. A sus valores de solucion se les llama raices caracteristicas

Teorema 1

Dada la relación de recurrencia $a_n = c_1a_{n-1} + c_2a_{n-2}\,$ con $c_1 \neq 0 \neq c_2\,$, se verifica:

1- $\alpha \,$ es raíz característica si y solo si $a_n = \alpha^n \,$ es solución de la relación de recurrencia.
2- si $\alpha\,$ es raíz doble de la ecuación característica, entonces $a_n = n\alpha^n\,$ es solución de la relación de recurrencia.
3- si $T\,$ y $S\,$ son soluciones de la relación de recurrencia, entonces $S + T\,$ y $kS\,$ también lo son, para todo $k \in \mathbb{R}\,$

Teorema 2

Dada la relación de recurrencia $a_n=c_1a_{n-1}+c_2a_{n-2}\,$ con $c_1 \neq 0 \neq c_2\,$:

1- Si la ecuación $x^2-c_1x-c_2=0\,$ tiene dos soluciones reales distintas a $\alpha\,$ y $\beta\,$ se tiene que $a_n=C_1\alpha^n + C_2\beta^n\,$
2- Si la ecuación $x^2-c_1x-c_2=0\,$ tiene una solución real doble $\alpha\,$ se tiene que $a_n=(C_1+C_2n)\alpha^n\,$.
  $C_1\,$ y $C_2\,$ se determinan a partir de las condiciones iniciales $a_0\,$ y $a_1\,$.

Relaciones de recurrencia lineales no homogéneas

Si $a_n=c_1a_{n-1}+c_2a_{n-2}\dots + c_ma_{n-m}+g(n)\,$ para $n\ge m\,$, se dice que la relación de recurencia es lineal no homogénea de orden $m\,$. A la relación $a_n=c_1a_{n-1}+c_2a_{n-2}\dots +c_ma_{m-n}\,$ resultante de eliminar $g(n)\,$ se le llama relación de recurrencia lineal homogénea asociada.

Proposición

Si $T\,$ y $S\,$ son soluciones de la relación de recurrencia lineal no homogénea, entonces $S-T\,$ es solución de la relación de recurrencia lineal homogénea asociada.

Pasos para resolver una relación de recurrencia lineal no homogénea

- Se obtiene la solución general de la ecuación homogénea asociada. - Se obtiene una solución particular de la relación de recurrencia no homogénea. - La suma de la solución general de la ecuación lineal homogénea asociada y de una solución particular de la relación de recurrencia lineal no homogénea nos da la solución general de la relación de recurrencia lineal no homogénea. - La solución específica se obtiene a partir de las condiciones iniciales.

Observación

Una solución particular $(x_n)\,$ de la relación de recurrencia lineal no homogénea se puede encontrar en algunos casos especiales. - Si $g(n) = P_k(n)\,$ (polinomio de grado $k\,$, entonces $x_n = Q_k(n)\,$ (polinomio de grado $k\,$, excepto si 1 es raíz característica con multiplicidad s, en cuyo caso $x_n = n^sQ_k(n)\,$. - Si $g(n) = pa^n, p\in \mathbb{R}\,$, entonces $x_n=qa^n, q\in \mathbb{R}\,$, excepto si a es raíz característica con multiplicidad s, en cuyo caso $x_n=qn^sa^n\,$ - Si $g(n)=a^nP_k(n)\,$, entonces $x_n=a^nQ_k(n)\,$, excepto si a es raíz característica con multiplicidad s, en cuyo caso $x_n=n^sa^nQ_k(n)\,$

Obtenido de "Relaci%C3%B3n de recurrencia"