9.2: Ecuaciones de recurrencia lineal

Última actualización
Guardar como PDF

Page ID: 118562

Mitchel T. Keller & William T. Trotter
Georgia Tech & Morningside College

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)

¿Qué tienen en común todos los ejemplos de la sección anterior? El resultado final que pudimos lograr es una recurrencia lineal, que nos dice cómo podemos calcular el\(n^{th}\) término de una secuencia dado algún número de valores anteriores (y quizás también dependiendo no recursivamente de también, como en el último ejemplo).\(n\) Más precisamente, se dice que una ecuación de recurrencia es lineal cuando tiene la siguiente forma

\(c_0a_{n+k} + c_1a_{n+k-1} + c_2a_{n+k-2} + \cdot \cdot \cdot + c_ka_n = g(n)\),

donde\(k \geq 1\) es un entero,\(c_0,c_1,…,c_k\) son constantes con\(c_0,c_k \neq 0\), y\(g: \mathbb{Z} \rightarrow \mathbb{R}\) es una función. (Lo que acabamos de definir puede llamarse más propiamente una ecuación de recurrencia lineal con coeficientes constantes, ya que requerimos\(c_i\) que las sean constantes y les prohíba depender de ellas\(n\). Evitaremos este descriptor adicional, en lugar de elegir hablar de ecuaciones de recurrencia lineal con coeficientes no constantes en caso de que permitamos\(c_i\) que sean funciones de\(n\).) Una ecuación lineal es homogénea si la función del\(g(n)\) lado derecho es la función cero. Por ejemplo, la secuencia de Fibonacci satisface la ecuación de recurrencia lineal homogénea

\(a_{n+2} - a_{n+1} - a_n = 0\).

Tenga en cuenta que en este ejemplo,\(k=2\),\(c_0=1\) y\(c_k = -1\).

Como segundo ejemplo, la secuencia del Ejemplo 9.4 satisface la ecuación de recurrencia lineal homogénea

\(t_{n+2} - 3t_{n+1} + t_n = 0\).

Nuevamente,\(k=2\) con\(c_0 = c_k = 1\).

Por otro lado, la secuencia\(r_n\) definida en la Subsección 9.1.3 satisface la ecuación de recurrencia lineal no homogénea

\(r_{n+1}-r_n = n+1\).

En este caso,\(k=1, c_0=1\) y\(c_k = -1\).

Nuestro objetivo inmediato es desarrollar técnicas para resolver ecuaciones de recurrencia lineal de tipos homogéneos y no homogéneos. Seremos capaces de resolver completamente la cuestión de resolver ecuaciones de recurrencia lineal homogéneas y discutir una especie de método de “conjetura y prueba” que se puede utilizar para abordar el tipo no homogéneo más complicado.