8.3: Relaciones de recurrencia

En esta sección comenzaremos nuestro estudio de las relaciones de recurrencia y sus soluciones. Nuestro enfoque principal estará en la clase de relaciones de recurrencia lineal de orden finito con coeficientes constantes (acortadas a relaciones lineales de orden finito). Primero, examinaremos expresiones de forma cerrada de las que surgen estas relaciones. Segundo, presentaremos un algoritmo para resolverlos. En secciones posteriores consideraremos algunas otras relaciones comunes (8.4) e introduciremos dos herramientas adicionales para estudiar las relaciones de recurrencia: funciones generadoras (8.5) y métodos matriciales (Capítulo 12).

Definición y Terminología

Definición\(\PageIndex{1}\): Recurrence Relation

Dejar\(S\) ser una secuencia de números. Una relación de recurrencia on\(S\) es una fórmula que relaciona todos menos un número finito de términos de\(S\) a términos anteriores de Es\(S\text{.}\) decir, hay un\(k_0\) en el dominio de\(S\) tal que si\(k \geq k_0\text{,}\) entonces\(S(k)\) se expresa en términos de algunos (y posiblemente todos) de los términos que precede\(S(k)\text{.}\) Si el dominio de\(S\) es\(\{0,1,2,\dots \}\text{,}\) los términos no\(S (0), S(1), . . . , S\left(k_0-1\right)\) están definidos por la fórmula de recurrencia. Sus valores son las condiciones iniciales (o condiciones límite, o base) que completan la definición de\(S\text{.}\)

Ejemplo\(\PageIndex{1}\): Some Examples of Recurrence Relations

1. La secuencia de Fibonacci se define por la relación de recurrencia\(F_k= F_{k-2}+ F_{k-1}\text{,}\)\(k\geq 2,\) con las condiciones iniciales\(F_0=1\) y\(F_1=1\text{.}\) La relación de recurrencia se denomina relación de segundo orden porque\(F_k\) depende de los dos términos anteriores de\(F\text{.}\) Recordar que la secuencia\(C\) en Sección 8.2, Ejemplo 8.2.1, se puede definir con la misma relación de recurrencia, pero con diferentes condiciones iniciales.
2. La relación\(T(k) = 2T(k - 1)^2 - k T(k - 3)\) es una relación de recurrencia de tercer orden. Si\(T(2)\) se especifican los valores de\(T(0)\text{,}\)\(T(1)\text{,}\) y, entonces\(T\) está completamente definido.
3. La relación de recurrencia\(S(n) = S(\lfloor n/2\rfloor ) + 5\text{,}\)\(n > 0\text{,}\) con\(S(0)=0\) tiene orden infinito. Para determinar\(S(n)\) cuándo\(n\) es parejo, hay que volver a\(n/2\) términos. Dado que\(n/2\) crece sin límites sin\(n\text{,}\) ningún orden finito se puede dar a\(S\text{.}\)

Resolución de relaciones de recurrencia

Las secuencias suelen definirse más fácilmente con una relación de recurrencia; sin embargo, el cálculo de términos aplicando directamente una relación de recurrencia puede llevar mucho tiempo. El proceso de determinar una expresión de forma cerrada para los términos de una secuencia a partir de su relación de recurrencia se llama resolver la relación. No existe una sola técnica o algoritmo que pueda utilizarse para resolver todas las relaciones de recurrencia. De hecho, algunas relaciones de recurrencia no se pueden resolver. La relación que define\(T\) anteriormente es uno de esos ejemplos. La mayoría de las relaciones de recurrencia que es probable que encuentre en el futuro se clasifican como relaciones de recurrencia lineal de orden finito con coeficientes constantes. Esta clase es con la que pasaremos la mayor parte del tiempo en este capítulo.

Definición\(\PageIndex{2}\): \(n^{th}\) Order Linear Recurrence Relation

Dejar\(S\) ser una secuencia de números con dominio\(k\geq 0\text{.}\) Una relación de recurrencia lineal de\(n^{\textrm{th}}\) orden en\(S\) con coeficientes constantes es una relación de recurrencia que se puede escribir en la forma

\ comenzar {ecuación*} S (k) + C_1 S (k - 1) +.. + C_n S (k - n) = f (k)\ textrm {para} k\ geq n\ fin {ecuación*}

donde\(C_1, C_2, \ldots , C_n\) son constantes y\(f\) es una función numérica que se define para\(k \geq n\text{.}\)

Nota\(\PageIndex{1}\)

Acortaremos el nombre de esta clase de relaciones para\(n^{\textrm{th}}\) ordenar relaciones lineales. Por lo tanto, en discusiones posteriores, no se\(S(k) + 2k S(k - 1) = 0\) consideraría una relación lineal de primer orden.

Ejemplo\(\PageIndex{2}\): Some Finite Order Linear Relations

1. La secuencia de Fibonacci se define por la relación lineal de segundo orden porque\(F_k- F_{k-1}- F_{k-2}=0\)
2. La relación\(P(j) + 2P(j - 3) = j^2\) es una relación lineal de tercer orden. En este caso,\(C_1= C_2= 0\text{.}\)
3. La relación se\(A(k)= 2(A(k - 1) + k)\) puede escribir como\(A(k) - 2A(k - 1) = 2k\text{.}\) Por lo tanto, es una relación lineal de primer orden.

Relaciones de recurrencia obtenidas de “Soluciones”

Antes de dar un algoritmo para resolver relaciones lineales de orden finito, examinaremos las relaciones de recurrencia que surgen de ciertas expresiones de forma cerrada. Se seleccionan las expresiones de forma cerrada para que obtengamos relaciones lineales de orden finito a partir de ellas. Este enfoque puede parecer un poco artificial, pero si escribieras algunas expresiones algebraicas simples, lo más probable es que la mayoría de ellas sean similares a las que estamos a punto de examinar.

Para nuestro primer ejemplo, considere\(D\text{,}\) definido por\(D(k) =5\cdot 2^k\text{,}\)\(k \geq 0\text{.}\) If\(k \geq 1\text{,}\)\(\quad\)\(D(k) =5\cdot 2^k = 2\cdot 5\cdot 2^{k-1} = 2 D(k - 1)\text{.}\) Therefore,\(D\) satisface la relación lineal de primer orden\(D(k) - 2 D(k - 1) = 0\) y la condición inicial\(D(0) = 5\) sirve como condición inicial para\(D\text{.}\)

Como segundo ejemplo, consideremos\(C(k) =3^{k-1}+2^{k+1}+k\), se requiere\(k \geq 0\text{.}\) bastante más manipulación algebraica para obtener nuestro resultado:

Mesa\(\PageIndex{1}\)

\(C(k) =3^{k-1}+2^{k+1}+k\)	Ecuación original
\(3C(k-1) =3^{k-1}+3\cdot 2^k+3(k-1)\)	Sustituir\(k-1\)\(k\) y multiplicar por\(3\)
	Restar la segunda ecuación de la primera.
\(C(k)-3C(k-1)=-2^k-2k+3\)	\(3^{k-1}\)término se elimina. Esta es una relación de primer orden.
\(2C(k-1)-6C(k-2)=-2^k-2(2(k-1))+6\)	Sustituto\(k-1\)\(k\) en la tercera ecuación, multiplicar por\(2\).
\(C(k)-5C(k-1)+6C(k-2)=2k-7\)	Restar la 4ta ecuación de la 3ra. \(2^{k+1}\)término se elimina. Esta es la relación de 2do orden.

La relación de recurrencia que acabamos de obtener, definida\(k \geq 2\text{,}\) junto con las condiciones iniciales\(C(0) = 7/3\) y\(C(1) = 6\text{,}\) definir\(C\text{.}\)

La tabla\(\PageIndex{2}\) resume nuestros resultados junto con algunos otros ejemplos que dejaremos derivar al lector. Con base en estos resultados, podríamos conjeturar que cualquier expresión de forma cerrada para una secuencia que combine expresiones exponenciales y expresiones polinómicas será soluciones de relaciones lineales de orden finito. Esto no sólo es cierto, sino que lo contrario es cierto: una relación lineal de orden finito define una expresión de forma cerrada que es similar a las que acabamos de examinar. La única información adicional que se necesita es un conjunto de condiciones iniciales.

Tabla\(\PageIndex{2}\): Relaciones de recurrencia obtenidas de secuencias dadas

Expresión de Forma Cerrada	Relación de recurrencia
\(D(k)=5\cdot 2^k\)	\(D(k)-2D(k-1)=0\)
\(C(k)=3^{k-1}+2^{k+1}+k\)	\(C(k)-2C(k-1)-6C(k-2)=2k-7\)
\(Q(k)=2k + 9\)	\(Q(k)-Q(k-1)=2\)
\(A(k)=k^2-k\)	\(A(k)-2A(k-1)+A(k-2)=2\)
\(B(k)=2 k^2+1\)	\(B(k)-2B(k-1)+B(k-2)=4\)
\(G(k)=2\cdot 4^k-5(-3)^k\)	\(G(k)-G(k-1)+12G(k-2)=0\)
\(J(k)=(3+k) 2^k\)	\(J(k)-4J(k-1)+4J(k-2)=0\)

Definición\(\PageIndex{3}\): Homogeneous Recurrence Relation

Una relación lineal de\(n^{th}\) orden es homogénea si\(f(k) = 0\) para todos\(k\text{.}\) Para cada relación de recurrencia\(S(k) + C_1S(k - 1) +\ldots + C_n S(k - n) = f(k)\text{,}\) la relación homogénea asociada es\(S(k) + C_1S(k - 1) +\ldots + C_n S(k - n) =0\)

Ejemplo\(\PageIndex{3}\): First Order Homogeneous Recurrence Relations

\(D(k) - 2D(k - 1) = 0\)es una relación homogénea de primer orden. Ya que también se puede escribir como no\(D(k) = 2D(k - 1)\text{,}\) debería sorprender que surgiera de una expresión que involucra poderes de 2. De manera más general, se esperaría que la solución de\(L(k) - a L(k - 1)\) implicaría\(a^k\text{.}\) En realidad, la solución es\(L(k) = L(0)a^k\text{,}\) donde el valor de\(L(0)\) viene dado por la condición inicial.

Ejemplo\(\PageIndex{4}\): A Second Order Example

Considerar la relación homogénea de segundo orden\(S(k) - 7S(k - 1) + 12 S(k- 2) = 0\) junto con las condiciones iniciales\(S(0) = 4\) y\(S(1) = 4\text{.}\) A partir de nuestra discusión anterior, podemos predecir que la solución a esta relación implica términos de la forma\(b a^k\text{,}\) donde\(b\) y\(a\) son constantes distintas de cero que deben ser determinado. Si la solución fuera a igualar esta cantidad exactamente, entonces

\ begin {equation*}\ quad\ quad\ quad\ begin {array} {ccc} S (k) =b a^k & &\\ S (k-1) =b a^ {k-1} &\ textrm {} &\ textrm {}\\ S (k-2) =b a^ {k-2} & &\\ end {array}\ end {ecuación*}

Sustituir estas expresiones en la relación de recurrencia para obtener

\ comenzar {ecuación*} b a^k-7 b a^ {k-1} +12 b a^ {k-2} =0\ final {ecuación*}

Cada término en el lado izquierdo de esta ecuación tiene un factor del\(b a^{k-2}\text{,}\) cual es distinto de cero. Dividiendo por este factor común rinde

\[\label{eq:1}a^{2}-7a+12=(a-3)(a-4)=0\]

Por lo tanto, los únicos valores posibles de\(a\) son 3 y 4. Ecuación\(\eqref{eq:1}\) se llama la ecuación característica de la relación de recurrencia. El hecho es que nuestra relación de recurrencia original es cierta para cualquier secuencia de la forma\(S(k) = b_1 3^k + b_24^k\text{,}\) donde\(b_1\) y\(b_2\) son números reales. Este conjunto de secuencias se llama la solución general de la relación de recurrencia. Si no tuviéramos condiciones iniciales para\(S\text{,}\) que nos detendríamos aquí. Las condiciones iniciales nos permiten encontrar valores definidos para\(b_1\) y\(b_2\text{.}\)

\ begin {ecuation*}\ left\ {\ begin {array} {c} S (0) =4\\ S (1) =4\\\ end {array}\ right\}\ textrm {}\ Rightarrow\ left\ {\ begin {array} {c} b_13^0+b_24^0=4\\ b_13^1+b_24^1=4\\\ end {array}\ right\}\ textrm {}\ Rightarrow\ left\ {\ begin {array} {c} b_1+b_2=4\\ 3b_1+4b_2=4\\ end {array}\ right\}\ textrm {}\ end {ecuación*}

La solución de este conjunto de ecuaciones simultáneas es\(b_1 = 12\) y\(b_2 = -8\) y así la solución es\(S(k) = 12 \cdot 3^k - 8 \cdot 4^k\text{.}\)

Definición\(\PageIndex{4}\): Characteristic Equation

La ecuación característica de la relación lineal de\(n^{\textrm{th}}\) orden homogéneo\(S(k) + C_1 S(k- 1) +\ldots + C_n S(k - n) =0\) es la ecuación polinómica de grado\(n\) th

\ begin {ecuación*} a^n+\ suma_ {j=1} ^n C_j a^ {n-j} =a^n+ C_1a^ {n-1} +\ cdots +C_ {n-1} a+C_n=0\ end {ecuación*}

El lado izquierdo de esta ecuación se llama polinomio característico. Las raíces del polinomio característico se denominan raíces características de la ecuación.

Ejemplo\(\PageIndex{5}\): Some Characteristic Equations

1. La ecuación característica de\(F(k) - F(k - 1) - F(k - 2) = 0\) es\(a^2-a-1=0\text{.}\)
2. La ecuación característica de\(Q(k) + 2Q(k - 1) - 3Q(k - 2) - 6 Q(k- 4) = 0\) es\(a^4+ 2a^3 - 3a^2 - 6 = 0.\) Tenga en cuenta que la ausencia de un\(Q(k - 3)\) término significa que no hay un\(x^{4-3}=x\) término que aparezca en la ecuación característica.

Algorithm \(\PageIndex{1}\): Algorithm for Solving Homogeneous Finite Order Linear Relations

1. Escribe la ecuación característica de la relación\(S(k) + C_1S(k - 1) +\ldots + C_n S(k - n) =0\text{,}\) que es\(a^n+ C_1a^{n-1}+\cdots +C_{n-1}a+C_n=0\text{.}\)
2. Encuentra todas las raíces de la ecuación característica, las raíces características.
3. Si hay raíces características\(n\) distintas,\(a_1, a_2, \dots a_n\text{,}\) entonces la solución general de la relación de recurrencia es\(S(k) = b_1a_1{}^k+ b_2a_2{}^k+\cdots +b_na_n{}^k\text{.}\) Si hay raíces menos que\(n\) características, entonces al menos una raíz es una raíz múltiple. Si\(a_j\) es una raíz doble, entonces el\(b_ja_j{}^k\) término se sustituye por\(\left(b_{j 0}+b_{j 1}k\right)a_j^{k}\textrm{.}\) En general, si\(a_j\) es una raíz de multiplicidad\(p\text{,}\) entonces el\(b_ja_j{}^k\) término se sustituye por\(\left(b_{j 0}+b_{j 1}k+\cdots +b_{j(p-1)}k^{p-1}\right)a_j^{k}\text{.}\)
4. Si se dan condiciones\(n\) iniciales, obtenemos ecuaciones\(n\) lineales en\(n\) incógnitas (la\({b_j}'s\) del Paso 3) por sustitución. Si es posible, resuelva estas ecuaciones para determinar una forma final para\(S(k)\text{.}\)

Aunque este algoritmo es válido para todos los valores de\(n\text{,}\) existen límites al tamaño de\(n\) para los cuales el algoritmo es factible. Usando solo un lápiz y papel, siempre podemos resolver ecuaciones de segundo orden. La fórmula cuadrática para las raíces de\(a x^2 + b x + c = 0\) es

\ begin {ecuación*} x=\ frac {-b\ pm\ sqrt {b^2-4 a c}} {2 a}\ end {ecuación*}

Las soluciones de\(a^2+ C_1a + C_2 = 0\) son entonces

\ begin {ecuación*}\ frac {1} {2}\ izquierda (-C_1+\ sqrt {C_1 {} ^2-4 C_2}\ derecha)\ textrm {y}\ frac {1} {2}\ izquierda (-C_1-\ sqrt {C_1 {} ^2-4 C_2}\ derecha)\ end {ecuación*}

Aunque existen fórmulas cúbicas y cuárticas, son demasiado largas para introducirlas aquí. Por ello, las únicas relaciones de orden superior (\(n\geq 3\)) que se podría esperar que resolvieran a mano son aquellas para las que existe una factorización fácil del polinomio característico.

Ejemplo\(\PageIndex{6}\): A Solution Using the Algorithm

Supongamos que\(T\) se define por\(T(k) =7T(k-1)-10T(k-2)\text{,}\) con\(T(0) = 4\) y\(T(1) = 17\text{.}\) podemos resolver esta relación de recurrencia con Algoritmo\(\PageIndex{1}\):

1. Tenga en cuenta que hemos escrito la relación de recurrencia en forma “no estándar”. Para evitar errores en este sencillo paso, se podría considerar un reordenamiento de la ecuación a, en este caso,\(T(k) -7T(k-1)+10T(k-2)=0\text{.}\) Por lo tanto, la ecuación característica es\(a^2 -7a + 10 = 0\text{.}\)
2. Las raíces características son\(\frac{1}{2}\left(7+\sqrt{49-40}\right)=5\) y\(\frac{1}{2}\left(7-\sqrt{49-40}\right)=2\text{.}\) Estas raíces se pueden obtener con la misma facilidad factorizando el polinomio característico en\((a - 5)(a - 2)\text{.}\)
3. La solución general de la relación de recurrencia es\(T(k) =b_12^k+ b_25^k\text{.}\)
4. \(\quad\)\(\left\{ \begin{array}{c} T(0)=4 \\ T(1)=17 \\ \end{array} \right\}\textrm{ }\Rightarrow \left\{ \begin{array}{c} b_12^0+b_25^0=4 \\ b_12^1+b_25^1=17 \\ \end{array} \right\}\textrm{ }\Rightarrow \left\{ \begin{array}{c} b_1+b_2=4 \\ 2b_1+5b_2=17 \\ \end{array} \right\}\textrm{ }\)Las ecuaciones simultáneas tienen la solución\(b_1=1\) y\(b_2=3\text{.}\) por lo tanto,\(T(k)=2^{k }+3\cdot 5^k\text{.}\)

Aquí hay una regla que podría ser útil: Si los coeficientes del polinomio característico son todos enteros, con el término constante igual a\(m\text{,}\) entonces las únicas raíces características racionales posibles son los divisores de\(m\) (tanto positivos como negativos).

Con la ayuda de una computadora (o posiblemente solo de una calculadora), podemos aumentar\(n\text{.}\) las aproximaciones de las raíces características que se pueden obtener por cualquiera de varios métodos bien conocidos, algunos de los cuales forman parte de paquetes de software estándar. No existe una regla general que especifique los valores\(n\) para los cuales serán factibles las aproximaciones numéricas. La precisión que obtengas dependerá de la relación que intentes resolver. (Ver Ejercicio\(\PageIndex{17}\) de esta sección.)

Ejemplo \(\PageIndex{7}\): Solution of a Third Order Recurrence Relation

Resolver\(S(k) - 7S(k - 2) + 6S(k - 3) = 0\text{,}\) dónde\(S(0) =8\text{,}\)\(S(1) = 6\text{,}\) y\(S(2) = 22\text{.}\)

1. La ecuación característica es\(a^3 - 7a + 6 = 0\text{.}\)
2. Las únicas raíces racionales que podemos intentar son\(\pm 1, \pm 2, \pm 3, \textrm{and} \pm 6\text{.}\) Al verificar estas, obtenemos las tres raíces 1, 2 y\(-3\text{.}\)
3. La solución general es\(S(k) =b_11^k+b_22^k+b_3(-3){}^k\text{.}\) El primer término simplemente puede escribirse\(b_1\).
4. \(\left\{ \begin{array}{c} S(0)=8 \\ S(1)=6 \\ S(2)=22 \\ \end{array} \right\}\textrm{ }\Rightarrow \left\{ \begin{array}{c} b_1+b_2+b_3=8 \\ b_1+2b_2-3b_3=6 \\ b_1+4b_2+9b_3=22 \\ \end{array} \right\}\textrm{ }\)Se puede resolver este sistema por eliminación para obtener\(b_1=5\text{,}\)\(b_2=2\text{,}\) y\(b_3=1\text{.}\) Por lo tanto,\(\quad\)\(S(k) = 5 + 2\cdot 2^k + (-3)^k = 5 + 2^{k+1} + (-3)^k\)

Ejemplo\(\PageIndex{8}\): Solution with a Double Characteristic Root

Resolver\(D(k) - 8D(k - 1) + 16D(k - 2) = 0\text{,}\) dónde\(D(2) = 16\) y\(D(3) = 80\text{.}\)

1. Ecuación característica:\(a^2- 8a + 16 = 0\text{.}\)
2. \(a^2- 8a + 16 = (a - 4)^2\text{.}\)Por lo tanto, existe una raíz doble característica, 4.
3. Solución general:\(D(k) = \left(b_{10}+b_{11}k\right)4^k\text{.}\)
4. \(\left\{ \begin{array}{c} D(2)=16 \\ D(3)=80 \\ \end{array} \right\}\textrm{ }\Rightarrow \left\{ \begin{array}{c} \left(b_{10}+b_{11}2\right)4^2=16 \\ \left(b_{10}+b_{11}3\right)4^3=80 \\ \end{array} \right\}\textrm{ } \\ \Rightarrow \left\{ \begin{array}{c} 16b_{10}+32b_{11}=16 \\ 64b_{10}+192b_{11}=80 \\ \end{array} \right\} \Rightarrow \left\{ \begin{array}{c} b_{10}=\frac{1}{2} \\ b_{11}=\frac{1}{4} \\ \end{array} \right\}\)
   Por lo tanto\(D (k) = (1/2 + (1/4) k) 4^k= (2 + k)4^{k-1}\text{.}\)

Solución de Relaciones Lineales de Orden Finito No Homogéneas

Nuestro algoritmo para relaciones no homogéneas no será tan completo como para el caso homogéneo. Esto se debe a que diferentes lados (\(f(k)\)s) de la derecha requieren diferentes reglas para obtener una solución particular.

Algorithm\(\PageIndex{2}\): Algorithm for Solving Nonhomogeneous Finite Order Linear Relations

Para resolver la relación de recurrencia\(S(k) + C_1S(k - 1) +\ldots + C_n S(k - n) = f(k)\)

1. Escribir la relación homogénea asociada y encontrar su solución general (Pasos (a) a (c) de Algoritmo\(\PageIndex{1}\)). Llama a esto la solución homogénea,\(S^{(h)}(k)\text{.}\)
2. Empezar a obtener lo que se llama una solución particular,\(S^{(p)}(k)\) de la relación de recurrencia tomando una conjetura educada sobre la forma de una solución particular. Para una gran clase de lados derechos, esto no es realmente una suposición, ya que la solución particular suele ser el mismo tipo de función que\(f(k)\) (ver Tabla\(\PageIndex{3}\)).
3. Sustituye tu conjetura del Paso 2 en la relación de recurrencia. Si hiciste una buena conjetura, deberías poder determinar los coeficientes desconocidos de tu conjetura. Si hiciste una conjetura equivocada, debería ser evidente a partir del resultado de esta sustitución, así que vuelve al Paso 2.
4. La solución general de la relación de recurrencia es la suma de las soluciones homogéneas y particulares. Si no se dan condiciones, entonces estás terminado. Si se dan condiciones\(n\) iniciales, se traducirán en ecuaciones\(n\) lineales en\(n\) incógnitas y resolverán el sistema para obtener una solución completa.

Tabla\(\PageIndex{3}\): Soluciones particulares para los lados de la derecha

Lado derecho,\(f(k)\)	Forma de Solución Particular,\(S^{(p)}(k)\)
Constante,\(q\)	Constante,\(d\)
Función lineal,\(q_0+q_1 k\)	Función lineal,\(d_0+d_1 k\)
\(m^{th}\)polinomio de grado,\(q_0+q_1k+\cdots +q_m k^m\)	\(m^{th}\)polinomio de grado,\(d_0+d_1k+\cdots +d_m k^m\)
función exponencial,\(q a^k\)	función exponencial,\(d a^k\)

Ejemplo\(\PageIndex{9}\): Solution of a Nonhomogeneous First Order Recurrence Relation

Resuelve\(S(k) + 5S(k - 1) = 9\text{,}\) con\(S(0) = 6\text{.}\)

1. La relación homogénea asociada,\(S(k) + 5S(k - 1) = 0\) tiene la ecuación característica\(a + 5 = 0\text{;}\) por lo tanto,\(a = -5\text{.}\) La solución homogénea es\(S^{(h)}(k) =b (-5)^k\text{.}\)
2. Dado que el lado derecho es una constante, suponemos que la solución particular será una constante,\(d\text{.}\)
3. Si sustituimos\(S^{(p)}(k) = d\) en la relación de recurrencia, obtenemos\(d + 5d = 9\text{,}\) o\(6d = 9\text{.}\) Por lo tanto,\(S^{(p)}(k)=1.5\text{.}\)
4. La solución general de la relación de recurrencia es\(\quad\)\(S(k)= S^{(h)}(k)+S^{(p)}(k) =b (-5)^k+1.5\) La condición inicial nos dará una ecuación a resolver con el fin de determinar\(b\text{.}\)\(\quad\)\(S(0) = 6 \Rightarrow \textrm{ }b(-5)^0+ 1.5 = 6\textrm{ }\Rightarrow \textrm{ }b\textrm{ }+ 1.5 = 6\) Por lo tanto,\(b = 4.5\) y\(S(k) = 4.5(-5)^k + 1.5\text{.}\)

Ejemplo\(\PageIndex{10}\): Solution of a Nonhomogeneous Second Order Recurrence Relation

Considera\(T(k) - 7T(k - 1) + 10T(k - 2) = 6 + 8k\) con\(T(0) = 1\) y\(T(1) = 2\text{.}\)

1. De Ejemplo\(\PageIndex{6}\), sabemos que\(T^{(h)}(k)=b_12^k+ b_25^k\text{.}\) Precaución:No aplique las condiciones iniciales\(T^{(h)}\) hasta que agregue\(T^{(p)}\text{!}\)
2. Dado que el lado derecho es un polinomio lineal,\(T^{(p)}\) es lineal; es decir,\(T^{(p)}(k)=d_0+d_1k\text{.}\)
3. Sustitución en la relación de recurrencia rendimientos:\(\left(d_0+d_1k\right)-7\left(d_0+d_1(k-1)\right)+10\left(d_0+d_1(k-2)\right)=6+8k\)\(\quad\)\(\Rightarrow \left(4d_0-13d_1\right)+ \left(4d_1\right)k = 6 + 8 k\) Dos polinomios son iguales solo si sus coeficientes son iguales. Por lo tanto,\(\quad\)\(\left\{ \begin{array}{c} 4d_0-13d_1=6 \\ 4d_1=8 \\ \end{array} \right\}\Rightarrow \left\{ \begin{array}{c} d_0=8 \\ d_1=2 \\ \end{array} \right\}\)
4. Utilizar la solución general\(T(k) =b_12^k+ b_25^k+8+2k\) y las condiciones iniciales para obtener una solución final:\(\quad\)\(\left\{ \begin{array}{c} T(0)=1 \\ T(1)=2 \\ \end{array} \right\}\textrm{ }\Rightarrow \left\{ \begin{array}{c} b_1+ b_2+8=1 \\ 2b_1+5b_2+10=2 \\ \end{array} \right\}\textrm{ }\\ \\ \quad \quad \Rightarrow \left\{ \begin{array}{c} b_1+b_2=-7 \\ 2b_1+5b_2=-8 \\ \end{array} \right\}\\ \\ \quad \quad \Rightarrow \left\{ \begin{array}{c} b_1=-9 \\ b_2=2 \\ \end{array} \right\}\textrm{ }\)
   Por lo tanto,\(T(k) =-9\cdot 2^k+ 2\cdot 5^k+8+2k\text{.}\)

Nota\(\PageIndex{2}\): A Quick Note on Interest Rates

Cuando una cantidad, como el saldo de una cuenta de ahorros, se incrementa en algún porcentaje fijo, se calcula más fácilmente con un multiplicador. En el caso de un\(8\%\) incremento, el multiplicador es de 1.08 porque cualquier monto original\(0.08A\) le\(A\text{,}\) ha agregado, de manera que el nuevo saldo es\(A+0.08A = (1+0.08)A = 1.08 A\text{.}\)

Otro ejemplo es que si la tasa de interés es\(3.5\%\text{,}\) el multiplicador sería 1.035. Esto supone que el interés se aplica al final del año para intereses\(3.5\%\) anuales, a menudo llamados interés simple. Si el interés se aplica mensualmente, y asumimos un caso simplificado donde cada mes tiene la misma duración, el multiplicador después de cada mes sería\(\left(1+\frac{0.035}{12}\right) \approx 1.00292\text{.}\) Después de que pase un año, este multiplicador se aplicaría 12 veces, lo cual es lo mismo que multiplicar por\(1.00292^{12}\approx 1.03557\text{.}\) Ese incremento de 1.035 a 1.03557 es el efecto de interés compuesto.

Ejemplo\(\PageIndex{11}\): A Sort of Annuity

Supongamos que abres una cuenta de ahorro que paga una tasa de interés anual de\(8\%\text{.}\) Además, supongamos que decides depositar un dólar cuando abres la cuenta, y pretendes duplicar tu depósito cada año. Deja\(B(k)\) ser tu saldo después de\(k\) años. \(B\)se puede describir por la relación\(B(k) = 1.08 B(k - 1) + 2^k\text{,}\) con\(S(0) = 1\text{.}\) Si, en lugar de duplicar el depósito cada año, depositó una cantidad constante,\(q\text{,}\) el\(2^k\) plazo sería reemplazado por\(q\text{.}\) Una secuencia de depósitos regulares como este se llama una simple anualidad.

Volviendo a la situación original,

1. \(\displaystyle B^{(h)}(k)=b_1(1.08){}^k\)
2. \(B^{(p)}(k)\)debe ser de la forma\(d 2^k\text{.}\)
3. \ begin {ecuation*}\ begin {split} d 2^k = 1.08d 2^ {k-1} +2^k &\ Rightarrow (2d) 2^ {k-1} = 1.08d 2^ {k-1} + 2\ cdot 2^ {k-1}\ &\ Rightarrow 2d = 1.08 d + 2\\ &\ Rightarrow .92d = 2\ &\\ Rightarrow d= 2.174\ textrm {a la milésima más cercana})\ end {split}\ end {equation*}
   Por lo tanto \(B^{(p)}(k)=2.174\cdot 2^k\text{.}\)
4. \(B(0) = 1 \Rightarrow \textrm{ }b_1+2.174 = 1\\ \\ \quad \Rightarrow \textrm{ }b_1= -1.174\)
   Por lo tanto,\(B(k) = -1.174\cdot 1.08^k+ 2.174\cdot 2^k\text{.}\)

Ejemplo\(\PageIndex{12}\): Matching Roots

Encuentre la solución general para\(S(k) - 3 S(k - 1) - 4 S(k - 2) = 4^k\text{.}\)

1. Las raíces características de la relación homogénea asociada son\(-1\) y 4. Por lo tanto,\(S^{(h)}(k)=b_1(-1){}^k+ b_2 4^k\text{.}\)
2. Una función de la forma no\(d 4^k\) será una solución particular de la relación no homogénea ya que resuelve la relación homogénea asociada. Cuando el lado derecho involucra una función exponencial con una base que es igual a una raíz característica, debes multiplicar tu suposición a una solución particular por\(k\text{.}\) Nuestra suposición en\(S^{(p)}(k)\) sería entonces\(d k 4^k\). Consulte Observación\(\PageIndex{1}\) para una descripción más completa de esta regla.
3. Sustituir\(d k 4^k\) en la relación de recurrencia por\(S(k)\text{:}\)
   \ begin {equation*}\ begin {array} {c} d k 4^k-3d (k-1) 4^ {k-1} -4d (k-2) 4^ {k-2} =4^k\\ 16d k 4^ {k-2} -12d (k-1) 4^ {k-2} -4d (k-2) 4^ {k-2} =4^k\\ end {array}\ end {equation*}
   Cada término del lado izquierdo tiene un factor de\(4^{k-2}\)
   \ comenzar {ecuación*} 16 d k - 12d (k - 1) - 4d (k - 2) = 4^220 d = 16\ fila derecha d=0.8\ final {ecuación*}
   Por lo tanto,\(S^{(p)}(k) = 0.8 k 4^k\text{.}\)
4. La solución general a la relación de recurrencia es
   \ begin {equation*} S (k) =b_1 (-1) {} ^k+ b_2 4^k +0.8 k 4^k\ end {ecuación*}

Observación\(\PageIndex{1}\): When the Base of Right-Hand Side is Equal to a Characteristic Root

Si el lado derecho de una relación no homogénea implica un exponencial con base\(a\text{,}\) y también\(a\) es una raíz característica de multiplicidad,\(p\text{,}\) entonces multiplique su suposición en una solución particular como se prescribe en Tabla\(\PageIndex{3}\) por\(k^p\text{,}\) donde\(k\) está el índice de la secuencia.

Ejemplo\(\PageIndex{13}\): Examples of Matching Bases

1. Si\(S(k) - 9S(k - 1) + 20 S(k - 2) = 2\cdot 5^k\text{,}\) las raíces características son 4 y 5. Ya que 5 coincide con la base del lado derecho,\(S^{(p)}(k)\) tomará la forma\(d k 5^k\text{.}\)
2. Si\(S(n)- 6S(n - 1) + 9 S(n - 2) = 3^{n+1}\) la única raíz característica es 3, pero es una raíz doble (multiplicidad 2). Por lo tanto, la forma de la solución particular es\(d n^2 3^n\text{.}\)
3. Si\(Q(j)-Q(j-1)-12Q(j-2)=(-3)^j+ 6\cdot 4^j\text{,}\) las raíces características son\(-3\) y 4. La forma de la solución particular será\(d_1j (-3)^j+ d_2j\cdot 4^j\text{.}\)
4. Si\(S(k) - 9S(k - 1) + 8S(k- 2) = 9k + 1 = (9k + 1)1^k\text{,}\) las raíces características son 1 y 8. Si el lado derecho es un polinomio, como lo es en este caso, entonces se\(1^k\) puede introducir el factor exponencial. La solución particular tomará la forma\(k\left(d_0+ d_1k\right)\text{.}\)

Concluimos esta sección con un comentario sobre la situación en la que la ecuación característica da lugar a raíces complejas. Si restringimos los coeficientes de nuestras relaciones lineales de orden finito a números reales, o incluso a números enteros, aún podemos encontrar ecuaciones características cuyas raíces son complejas. Aquí, simplemente nos tomaremos el tiempo para señalar que nuestros algoritmos siguen siendo válidos con raíces características complejas, pero el método habitual para expresar las soluciones de estas relaciones es diferente. Dado que la comprensión de estas representaciones requiere algunos antecedentes en números complejos, simplemente sugeriremos que un lector interesado pueda referirse a un tratamiento más avanzado de las relaciones de recurrencia (ver también ecuaciones de diferencia).

Ejercicios

Resuelve los siguientes conjuntos de relaciones de recurrencia y condiciones iniciales:

Ejercicio\(\PageIndex{1}\)

\(S(k) - 10S(k - 1) + 9S(k - 2) = 0\text{,}\)\(S(0) = 3\text{,}\)\(S(1) = 11\)

Responder

\(S(k)=2+9^k\)

Ejercicio\(\PageIndex{2}\)

\(S(k) - 9S(k - 1) + 18S(k - 2) = 0\text{,}\)\(S(0) = 0\text{,}\)\(S(1) = 3\)

Ejercicio\(\PageIndex{3}\)

\(S(k) - 0.25S(k - 1) = 0\text{,}\)\(S(0) = 6\)

Responder

\(S(k)=6(1/4)^k\)

Ejercicio\(\PageIndex{4}\)

\(S(k) - 20S(k - 1) + 100S(k - 2) = 0\text{,}\)\(S(0) = 2\text{,}\)\(S(1) = 50\)

Ejercicio\(\PageIndex{5}\)

\(S(k) - 2S(k - 1) + S(k - 2) = 2 \textrm{, }S(0) = 25,\textrm{ }S(1) = 16\)

Responder

\(S(k)=k^2-10k+25\)

Ejercicio\(\PageIndex{6}\)

\(S(k) - S(k - 1) - 6S(k - 2) = -30\text{,}\)\(S(0) = 7\text{,}\)\(S(1) = 6\)

Ejercicio\(\PageIndex{7}\)

\(S(k) - 5S (k - 1) = 5^k,\textrm{ }S(0) = 3\)

Responder

\(S(k)=(3+k)5^k\)

Ejercicio\(\PageIndex{8}\)

\(S(k) - 5S(k - 1) + 6S(k - 2) = 2,\textrm{ }S(0) = -1,\textrm{ }S(1) = 0\)

Ejercicio\(\PageIndex{9}\)

\(S(k) - 4S(k - 1) + 4S(k - 2) = 3k + 2^k \textrm{, }S(0) = 1, S(1) = 1\)

Responder

\(S(k)=(12+3k)+\left(k^2+7k-22\right)2^{k-1}\)

Ejercicio \(\PageIndex{10}\)

\(S(k) = r S(k - 1) + a\text{,}\)\(S(0) = 0\text{,}\)\(r, a \geq 0, r \neq 1\)

Ejercicio\(\PageIndex{11}\)

\(S(k) - 4S(k - 1) - 11S(k- 2)+ 30S(k - 3) = 0\text{,}\)\(S(0) = 0\text{,}\)\(S(1) = -35,\textrm{ }S(2) = -85\)

Responder

\(P(k)=4(-3)^k+2^k-5^{k+1}\)

Ejercicio\(\PageIndex{12}\)

Encuentra una expresión de forma cerrada para\(P(k)\) en el Ejercicio 8.2.3 de la Sección 8.2.

Ejercicio\(\PageIndex{13}\)

1. Encuentra una expresión de forma cerrada para los términos de la secuencia de Fibonacci (ver Ejemplo 8.1.3).
2. La secuencia\(C\) se definió por\(C_r\) = el número de cadenas de ceros y unos con longitud\(r\) sin ceros consecutivos (Ejemplo 8.2.1 (c)). Su relación de recurrencia es la misma que la de la secuencia de Fibonacci. Determinar una expresión de forma cerrada para\(C_r\text{,}\)\(r \geq 1\text{.}\)

Responder

1. La ecuación característica es\(a^2-a-1=0\text{,}\) cuál tiene soluciones\(\alpha =\left.\left(1+\sqrt{5}\right)\right/2\) y\(\beta =\left.\left(1-\sqrt{5}\right)\right/2\text{,}\) Es útil señalar que\(\alpha +\beta =1\) y\(\alpha -\beta =\sqrt{5}\text{.}\) La solución general es\(F(k)=b_1\alpha ^k+b_2\beta ^k\text{.}\) Usando las condiciones iniciales, obtenemos el sistema:\(b_1+b_2=1\) y\(b_1\alpha +b_2\beta =1\text{.}\) La solución a este sistema es\(b_1=\alpha /(\alpha -\beta )=\left.\left(5+\sqrt{5}\right)\right/2\sqrt{5}\) y \(b_2=\beta /(\alpha -\beta )=\left.\left(5-\sqrt{5}\right)\right/2\sqrt{5}\)
   Por lo tanto, la solución final es
   \ begin {equation*}\ begin {split} F (n) & =\ frac {\ alpha^ {n+1} -\ beta^ {n+1}} {\ alpha-\ beta}\\ & =\ frac {\ left (\ left. \ izquierda (1+\ sqrt {5}\ derecha)\ derecha/2\ derecha) ^ {n+1} -\ izquierda (\ izquierda. \ izquierda (1-\ sqrt {5}\ derecha)\ derecha/2\ derecha) ^ {n+1}} {\ sqrt {5}}\\ end {split}\ end {equation*}
2. \(\displaystyle C_r=F(r+1)\)

Ejercicio\(\PageIndex{14}\)

Si\(S(n)=\sum_{j=1}^n g(j)\text{,}\)\(n\geq 1\text{,}\) entonces se\(S\) puede describir con la relación de recurrencia\(S(n) = S(n-1) + g(n)\text{.}\) Para cada una de las siguientes secuencias que se definen mediante una suma, busque una expresión de forma cerrada:

1. \(S(n) =\sum_{j=1}^n j\text{,}\)\(n\geq 1\)
2. \(Q(n) = \sum_{j=1}^n j^2\text{,}\)\(n\geq 1\)
3. \(P(n) =\)\(\sum_{j=1}^n \left(\frac{1}{2}\right)^j\text{,}\)\(n\geq 0\)
4. \(T(n)= \sum_{j=1}^n j^3\text{,}\)\(n\geq 1\)

Ejercicio\(\PageIndex{15}\)

\(D(n)\)Sea el número de formas en que el conjunto se\(\{1, 2, . . . , n\}\text{,}\)\(n \geq 1\text{,}\) puede dividir en dos subconjuntos no vacíos.

1. Encontrar una relación de recurrencia para\(D\text{.}\) (Pista: Será una relación lineal de primer orden.)
2. Resolver la relación de recurrencia.

Responder

1. Por cada partición de dos bloques de\(\{1,2,\dots, n-1\}\text{,}\) hay dos particiones que podemos crear cuando agregamos\(n\text{,}\) pero hay una partición adicional de dos bloques a contar para la cual un bloque es\(\{n\}\text{.}\) Por lo tanto,\(D(n)=2D(n-1)+1 \textrm{ for } n \geq 2 \textrm{ and } D(1)=0.\)
2. \(\displaystyle D(n)=2^{n-1}-1\)

Ejercicio\(\PageIndex{16}\)

Si tuvieras que depositar una cierta cantidad de dinero al final de cada año por varios años, esta secuencia de pagos se llamaría anualidad (ver Ejemplo\(\PageIndex{11}\)).

1. Encuentra una expresión de forma cerrada para el saldo o valor de una anualidad que consiste en pagos de\(q\) dólares a una tasa de interés de\(i\text{.}\) Tenga en cuenta que para una anualidad normal, el primer pago se realiza después de un año.
2. Con una tasa de interés de 5.5 por ciento, ¿cuánto necesitaría depositar en una anualidad para tener un valor de un millón de dólares después de 18 años?
3. El pago de un préstamo es una forma de anualidad en la que el valor inicial es algún monto negativo (el monto del préstamo) y la anualidad termina cuando el valor se eleva a cero. ¿Cuánto podrías pedir prestado si puedes permitirte pagar $5,000 anuales durante 25 años al 11 por ciento de interés?

Ejercicio\(\PageIndex{17}\)

Supongamos que\(C\) es un pequeño número positivo. Consideremos la relación de recurrencia\(B(k) - 2B(k - 1) + \left(1 - C ^2\right)B(k - 2) = C^2\text{,}\) con las condiciones iniciales\(B(0) = 1\) y\(B(1) = 1\text{.}\) Si\(C\) es lo suficientemente pequeña, podríamos considerar aproximar la relación\(1 - C^2\) reemplazando por 1 y\(C^2\) por 0. Resolver la relación original y su aproximación. Que\(B_a\) a sea la solución de la aproximación. Comparar expresiones de forma cerrada para\(B(k)\) y\(B_a(k)\text{.}\) Sus formas son muy diferentes porque las raíces características de la relación original estaban muy juntas y la aproximación resultó en una raíz doble característica. Si las raíces características de una relación están relativamente alejadas, este problema no ocurrirá. Por ejemplo, compare las soluciones generales de\(S(k) + 1.001S(k - 1) - 2.004002 S(k - 2) = 0.0001\) y\(S_a(k) + S_a(k - 1) - 2S_a(k - 2) = 0\text{.}\)