9.5: Formalizar nuestro enfoque de ecuaciones de recurrencia
- Page ID
- 118561
Hasta ahora, nuestro enfoque para resolver ecuaciones de recurrencia se ha basado en la intuición, y no hemos dado mucha explicación de por qué las soluciones que hemos dado han sido la solución general. En esta sección, procuramos remediar esto. Algo de familiaridad con el lenguaje del álgebra lineal será útil para el resto de esta sección, pero no es esencial.
Nuestras técnicas para resolver ecuaciones de recurrencia tienen sus raíces en un concepto fundamentalmente importante en matemáticas, la noción de un espacio vectorial. Recordemos que un espacio vectorial consiste en un conjunto\(V\) de elementos llamados vectores; además, existe una operación binaria llamada suma con la suma de vectores\(x\) y\(y\) denotado por\(x+y\); además, existe una operación llamada multiplicación escalar que combina un escalar (número real)\(\alpha\) y un vector\(x\) para formar un producto denotado. \(\alpha x\). Estas operaciones satisfacen las siguientes propiedades:
- \(x+y = y +x\)para cada\(x,y, \in V\).
- \(x+(y+z) = (x+y) + z\), para cada\(x,y,z \in V\).
- Hay un vector llamado cero y denotado 0 de manera que\(x+0=x\) para cada\(x \in V\). Nota: Nuevamente estamos sobrecargando a un operador y usando el símbolo 0 para algo que no sea un número.
- Por cada elemento\(x \in V\), hay un elemento\(y \in V\), llamado el inverso aditivo de\(x\) y denotado de\(−x\) manera que\(x+(−x)=0\). Esta propiedad nos permite definir la resta, es decir,\(x-y = x+(-y)\).
- \(1x = x\)para cada\(x \in X\).
- \(\alpha(\beta x) = (\alpha \beta)x\), para todos\(\alpha, \beta \in \mathbb{R}\) y cada uno\(x \in V\).
- \(\alpha(x+y) = \alpha x + \alpha y\)para todos\(\alpha \in \mathbb{R}\) y cada uno\(x,y \in V\).
- \((\alpha + \beta)x = \alpha x + \beta x\), para todos\(\alpha, \beta \in \mathbb{R}\) y cada uno\(x \in V\).
Cuando\(V\) es un espacio vectorial, una función\(\phi:V \rightarrow V\) se llama operador lineal, o simplemente operador para abreviar, cuando\(\phi(x+y)=\phi(x)+ \phi(y)\) y\(\phi(\alpha x)=\alpha \phi(x)\). Cuando\(\phi:V \rightarrow V\) es un operador, es costumbre escribir\(\phi x\) en lugar de\(\phi(x)\), guardando un conjunto de paréntesis. El conjunto de todos los operadores sobre un espacio vectorial\(V\) es en sí mismo un espacio vectorial con suma definida por\((\phi+\rho)x=\phi x+ \rho x\) y multiplicación escalar por\((\alpha \phi)x= \alpha(\phi x)\).
En este capítulo, nos centramos en el espacio vectorial real V que consta de todas las funciones de la forma\(f: \mathbb{Z} \rightarrow \mathbb{R}\). La suma se define por\((f+g)(n)=f(n)+g(n)\) y la multiplicación escalar se define por\((\alpha f)(n)=\alpha (f(n))\).
9.5.1 El Teorema Principal
Aquí está el teorema básico sobre la resolución de ecuaciones de recurrencia (expresado en términos de ecuaciones de operador de avance) y aunque no probaremos el resultado completo, proporcionaremos suficiente esquema donde no debería ser demasiado difícil rellenar los detalles que faltan.
Dejar\(k\) ser un entero positivo\(k\), y dejar\(c_0,c_1,…,c_k\) ser constantes con\(c_0,c_k \neq 0\). Luego el conjunto\(W\) de todas las soluciones a la ecuación lineal homogénea
\[(c_0A^k + c_1A^{k-1} + c_2A^{k-2} + \cdot \cdot \cdot + c_k)f = 0 \label{9.5.1} \]
es un subespacio\(k\) -dimensional de\(V\).
La conclusión de que el conjunto\(W\) de todas las soluciones es un subespacio de\(V\) es inmediata, ya que
\(p(A)(f+g) = p(A)f + p(A)g\)y\(p(a)(\alpha f) = \alpha p (A)(f)\).
Lo que requiere un poco de trabajo es mostrar que\(W\) es un subespacio\(k\) -dimensional. Pero una vez hecho esto, entonces para resolver la ecuación del operador de avance dada en la forma del Teorema 9.18, basta con encontrar una base para el espacio vectorial\(W\). Cada solución es solo una combinación lineal de vectores base. En las siguientes subsecciones, esbozamos cómo se puede lograr este objetivo.
9.5.2 El Caso de Inicio
El desarrollo procede por inducción (¡sorpresa!) \(k=1\)siendo el caso el caso base. En este caso, estudiamos una ecuación simple de la forma\((c_0A+c_1)f=0\). Dividiendo por\(c_0\) y reescribiendo usando resta en lugar de suma, es claro que solo estamos hablando de una ecuación de la forma\((A−r)f=0\) donde\(r \neq 0\).
Dejar\(r \neq 0\), y dejar\(f\) ser una solución a la ecuación del operador\((A−r)f=0\). Si\(c=f(0)\), entonces\(f(n)=cr^n\) para cada\(n \in \mathbb{Z}\).
- Prueba
-
Primero mostramos eso\(f(n)=cr^n\) para cada\(n \geq 0\), por inducción en\(n\). El caso base es trivial desde entonces\(c=f(0)=cr^0\). Ahora supongamos que\(f(k)=cr^k\) para algún entero no negativo\(k\). Entonces\((A−r)f=0\) implica que\(f(k+1)−rf(k)=0\), es decir,
\(f(k+1)=rf(k)=rcr^k=cr^{k+1}\).
Un argumento muy similar lo demuestra\(f(−n)=cr^{−n}\) para cada uno\(n \leq 0\).
Considerar una ecuación de operador no homogénea de la forma
\[p(A)f=(c_0A^k+c_1A^{k−1}+c_2A^{k−2}+ \cdot \cdot \cdot +c_k)f=g \label{9.5.2} \]
con\(c_0,c_k \neq 0\), y dejar\(W\) ser el subespacio de\(V\) consistir en todas las soluciones a la ecuación homogénea correspondiente
\[p(A)f=(c_0A^k+c_1A^{k−1}+c_2A^{k−2}+ \cdot \cdot \cdot +c_k)f=0 \label{9.5.3} \]
Si\(f_0\) es una solución a\(\ref{9.5.2}\), entonces cada solución f a\(\ref{9.5.2}\) tiene la forma\(f=f_0+f_1\) donde\(f_1 \in W\).
- Prueba
-
Dejar\(f\) ser una solución de\(\ref{9.5.2}\), y dejar\(f_1=f−f_0\). Entonces
\(p(A)f_1=p(A)(f−f_0)=p(A)f−p(A)f_0=g−g=0\).
Esto implica eso\(f_1 \in W\) y eso\(f=f_0+f_1\) para que todas las soluciones a\(\ref{9.5.2}\) hacer de hecho tengan la forma deseada.
Usando los dos resultados anteriores, ahora podemos proporcionar un esquema del paso inductivo en la prueba del Teorema 9.18, al menos en el caso en que el polinomio en el operador de avance tenga raíces distintas.
Considere la siguiente ecuación del operador de avance
\[p(A)f=(A−r_1)(A−r_2)…(A−r_k)f=0 \label{9.5.4} \]
con constantes\(r_1,r_2,…,r_k\) distintas distintas de cero. Entonces cada solución\(\ref{9.5.4}\) tiene la forma
\(f(n)=c_1r_1^n+c_2r_2^n+c_3r_3^n+ \cdot \cdot \cdot +c_kr_k^n\).
- Prueba
-
El caso\(k=1\) es Lemma 9.19. Ahora supongamos que hemos establecido el teorema para algún entero positivo m y consideramos el caso\(k=m+1\). Reescribir (9.5.4) como
\((A−r_1)(A−r_2)…(A−r_m)[(A−r_{m+1})f]=0\).
Por la hipótesis inductiva, se deduce que si\(f\) es una solución a (9.5.4), entonces f es también una solución a la ecuación no homogénea
\[(A−r_{m+1})f=d_1r_1^n+d_2r_2^n+ \cdot \cdot \cdot +d_mr_m^n \label{9.5.5} \]
Para encontrar una solución particular\(f_0\) a\(\ref{9.5.5}\), buscamos una solución que tenga la forma
\[f_0(n)=c_1r_1^n+c_2r_2^n+ \cdot \cdot \cdot +c_mr_m^n \label{9.5.6}\]
Por otro lado, un simple cálculo muestra que para cada uno\(i=1,2,…,m\), tenemos
\((A−r_{m+1})c_ir_i^n=c_ir_i^{n+1}−r_{m+1}c_ir_i^n=c_i(r_i−r_{m+1})r_i^n\),
por lo que basta elegir para\(c_i\) que\(c_i(r_i−r_{m+1})=d_i\), para cada uno\(i=1,2,…,m\). Esto se puede hacer ya que\(r_{m+1}\) es distinto de\(r_i\) for\(i=1,2,…m\).
Ahora tenemos una solución particular\(f_0(n)= \sum_{i=1}^m c_ir_i^n\). A continuación consideramos la ecuación homogénea correspondiente\((A−r_{m+1})f=0\). La solución general a esta ecuación tiene la forma\ (f_1 (n) =c_ {m+1} r_ {m+1} ^n. De ello se deduce que cada solución a la ecuación original tiene la forma
\(f(n)=f_0(n)+f_1(n)=c_1r_1^n+c_2r_2^n+ \cdot \cdot \cdot +c_mr_m^n+cr_{m+1}^n\),
¡que es exactamente lo que queremos!
9.5.3 Raíces Repetidas
Es sencillo modificar la prueba dada en el apartado anterior para obtener el siguiente resultado. Dejamos los detalles como ejercicio.
Dejar\(k \geq 1\) y considerar la ecuación
\[(A−r)^kf=0. \label{9.5.7}\]
Entonces la solución general a\(\lref{9.5.7}\) tiene la siguiente forma
\[f(n)=c_1r^n+c_2nr^n+c_3n^2r^n+c_4n^3r^n+ \cdot \cdot \cdot +c_kn^{k−1}r^n. \label{9.5.8}\]
9.5.4 El Caso General
Combinando los resultados en las secciones anteriores, podemos escribir rápidamente la solución general de cualquier ecuación homogénea de la forma\(p(A)f=0\) siempre que podamos factorizar el polinomio\(p(A)\). Nótese que en general, esta solución nos lleva al campo de los números complejos, ya que las raíces de un polinomio con coeficientes reales son a veces números complejos, con partes imaginarias distintas de cero.
Cerramos esta sección con un ejemplo más para ilustrar la rapidez con la que podemos leer la solución general de una ecuación de operador de avance homogéneo\(p(A)f=0\), siempre que\(p(A)\) sea factorizada.
Considerar la ecuación del operador de avance
\((A−1)^5(A+1)^3(A−3)^2(A+8)(A−9)^4f=0\).
Entonces cada solución tiene la siguiente forma
\(f(n) = c_1 + c_2n + c_3n^2 + c_4n^3 + c_5n^4\)
\(+ c_6(-1)^n + c_7n(-1)^n + c_8n^2(-1)^n\)
\(+ c_93^n + c_{10}n3^n\)
\(+c_{11}(-8)^n\)
\(+ c_{12}9^n + c_{13}n9^n + c_{14}n^29^n + c_{15}n^39^n\).