8.3: Uso de Funciones Generadoras para Resolver Secuencias Definidas Recursiblemente

Por fin, estamos listos para aplicar la mecánica que hemos introducido en este capítulo, para encontrar una fórmula explícita para el\(n^{\text{th}}\) término de una secuencia definida recursiblemente.

Este método es probablemente más fácil de entender usando ejemplos.

Ejemplo\(\PageIndex{1}\)

Considere la secuencia definida recursiblemente:\(a_0 = 2\), y para cada\(n ≥ 1\),\(a_n = 3a_{n−1} − 1\). Encuentra una fórmula explícita para un en términos de\(n\).

Solución

La función generadora para esta secuencia es\(a(x) = \sum_{i=0}^{\infty} a_ix^i \).

Ahora, vamos a usar la relación recursiva. Eso lo sabemos\(a_n = 3a_{n−1} − 1\), o, reordenando esto,\(a_n - 3a_{n−1} = −1\). Así, si pudiéramos obtener el coeficiente de\(x^n\) para parecerse\(a_n −3a_{n−1}\), podríamos usar la relación recursiva para reemplazar esto por\(−1\). Ahora mismo, el coeficiente de\(x^n\) es\(a_n\), y el único lugar que se\(a_{n−1}\) presenta es como el coeficiente de\(x^{n−1}\). Pero si multiplicamos\(a(x)\) por\(x\), entonces\(a_{n−1}x^{n−1}\) se vuelve\(a_{n−1}x^n\), así que si también multiplicamos por\(−3\), obtenemos un coeficiente de\(−3a_{n−1}\) for\(x^n\) in\(−3xa(x)\). Ahora agregue esto a\(a(x)\). Esto puede ser más fácil de ver como se escribe a continuación:

\( \begin{equation} \begin{split} a(x)&= a_0 &+ a_1x &+a_2x^2 &+... &+ a_mx^m &+ ...\\ −3xa(x)&= &−3a_0x &−3a_1x^2 &−... &−3a_{m-1}x^m &-... \\ \therefore (1 − 3x)a(x)&= a_0 &−x &−x^2 &−... &−x^m &−... \end{split} \end{equation} \)

Vemos que esto da

\((1 − 3x)a(x) = 3 − (1 + x + x^2 + x^3 + . . .)\),

y sabemos que

\(1 + x + x^2 + x^3 + . . . = \dfrac{1}{(1 − x)}\),

así\((1 − 3x)a(x) = 3 − \dfrac{1}{(1 − x)}\). Dividiendo por\(1 − 3x\) da

\(a(x) = \dfrac{3}{1 − 3x} - \dfrac{1}{(1 − x)(1 − 3x)} \)

Ahora es el momento de aplicar lo que aprendimos en las secciones anteriores de este capítulo. El denominador ya está factorizado, por lo que podemos aplicar inmediatamente el método de fracciones parciales a la segunda fracción. Si

\(\dfrac{-1}{(1 − x)(1 − 3x)} = \dfrac{A}{1 − x} + \dfrac{B}{1 − 3x} = \dfrac{A(1 − 3x) + B(1 − x)}{(1 − 3x)(1 − x)} \),

entonces\(A + B = −1\) y\(−3A − B = 0\), así\(B = −3A\), lo que da\(−2A = −1\), así\(A = \dfrac{1}{2}\) y\(B = -\dfrac{3}{2}\). Por lo tanto,

\(a(x) = \dfrac{3}{1 − 3x} + \dfrac{\dfrac{1}{2}}{1-x} - \dfrac{\dfrac{3}{2}}{1-3x} = \dfrac{\dfrac{1}{2}}{1-x} + \dfrac{\dfrac{3}{2}}{1-3x} \)

El coeficiente de\(x^n\) en el primero de estos términos es\(\dfrac{1}{2}\), mientras que en el segundo término, el coeficiente de\(x^n\) es\((\dfrac{3}{2})3^n\). Por lo tanto,\(a_n = \dfrac{1}{2} + (\dfrac{3}{2})3^n\). Desde que nuestra función generadora comenzó con\(a_0x^0\), esta fórmula aplica para cada\(n ≥ 0\).

Al pasar por tanto álgebra, es fácil cometer un error en algún lugar del camino, así que es prudente hacer algunas comprobaciones dobles. Para una secuencia definida recursiblemente, si la fórmula que trabajas da la respuesta correcta para los primeros tres o cuatro términos de la secuencia, entonces es muy probable que hayas hecho los cálculos correctamente. Comprobemos los tres primeros términos de este. Sabemos por nuestra condición inicial que\(a_0 = 2\), y nuestra nueva fórmula da

\(a_0 = \dfrac{1}{2} + (\dfrac{3}{2})3^0 = \dfrac{1}{2} + \dfrac{3}{2} = 2\)

Usando la relación recursiva, deberíamos tener\(a_1 = 3(2) − 1 = 5\), y nuestra fórmula da

\(a_1 = \dfrac{1}{2} + (\dfrac{3}{2})3^1 = \dfrac{1}{2} + \dfrac{9}{2} = 5\)

Por último, la relación recursiva da\(a_2 = 3(5) − 1 = 14\), mientras que nuestra fórmula da

\(a_2 = \dfrac{1}{2} + (\dfrac{3}{2})3^2 = \dfrac{1}{2} + \dfrac{27}{2} = 14\)

Se puede ver el beneficio de tener una fórmula explícita si se le pidió hacer ejercicio\(a_{100}\). Claramente, es mucho más fácil determinar\(\dfrac{1}{2} + (\dfrac{3}{2})3^{100}\) que aplicar la relación recursiva cien veces.

Veamos un ejemplo más, donde la relación recursiva involucra más de un término anterior.

Ejemplo\(\PageIndex{2}\)

Considere la secuencia definida recursiblemente:\(b_0 = 1\),\(b_1 = 0\),\(b_2 = 1\), y para cada\(n ≥ 3\),\(b_n = b_{n−1} − 2b_{n−3}\). Encuentra una fórmula explícita para\(b_n\) en términos de\(n\).

Solución

La función generadora para esta secuencia es

\(b(x) = \sum_{i=0}^{\infty} b_ix^i\).

Nuevamente, usaremos la relación recursiva, que reorganizamos como

\(b_n - b_{n−1} + 2b_{n−3} = 0\)

para cada\(n ≥ 3\). Queremos terminar con un polinomio en el que\(x^m\) se vea el coeficiente de\(b_m − b_{m−1} + 2b_{m−3}\), para que podamos usar la relación recursiva para reemplazar esto por\(0\). Para hacer esto, tomaremos\(b(x)\) (para obtener la\(b_mx^m\) pieza), menos\(xb(x)\) (para obtener la\(−b_{m−1}x^m\) pieza), más\(2x^3 b(x)\) (para obtener la\(+2b_{m−3}x^m\) pieza).

El resultado se ve así:

\( \begin{equation} \begin{split} b(x)&= b_0 &+ b_1x &+b_2x^2 &+b_3x^3 &+... &+ b_mx^m &+ ...\\ −xb(x)&= &−b_0x &−b_1x^2 &-b_2x^3 &−... &−b_{m-1}x^m &-... \\ +2x^3b(x)&= & & &+2b_0x^3 &+... &+ 2b_{m-3}x^m &+ ... \\ \therefore (1 − x + 2x^3)b(x)&= b_0 &+(b_1 − b_0)x &+(b_2 − b_1)x^2 &+0x^3 &+... &+0x^m &+... \end{split} \end{equation} \)

Vemos que esto da

\((1 − x + 2x^3)b(x) = 1 + (−1)x + 1x^2\)

Dividiendo por\(1 − x + 2x^3\) da

\(b(x) = \dfrac{1 − x + x^2}{1 − x + 2x^3}\).

Si queremos poder hacer algo con esto, necesitamos factorizar el denominador. Aunque no tenemos un método general para factorizar polinomios cúbicos, en este caso no es difícil ver que\(−1\) es un cero del polinomio (porque\(1 − (−1) + 2(−1)^3 = 0)\), y por lo tanto\(x + 1\) es un factor del polinomio. No se esperará que factorialice los polinomios cúbicos usted mismo en este curso, así que no revisaremos la división larga polinomial, pero si recuerda la división larga polinomial, puede usarla para determinar que

\(1 − x + 2x^3 = (1 + x)(2x^2 − 2x + 1)\).

En cualquier caso, se puede multiplicar el lado derecho hacia afuera para verificar que sea cierto.

Ahora es el momento de usar la fórmula de factorización, con\(a = 2\), y\(b = −2\)\(c = 1\), para factorizar\(2x^2 − 2x + 1\). Esto da

\(2x^2 − 2x + 1 = 1 \left( 1 - \dfrac{2+ \sqrt{4-8}}{2}x \right)\left( 1 - \dfrac{2- \sqrt{4-8}}{2}x \right) = (1 − (1 + i)x) (1 − (1 − i)x) \).

Habiendo factorizado

\(1 − x + 2x^3 = (1 + x)(1 − (1 + i)x)(1 − (1 − i)x)\),

ahora aplicamos el método de fracciones parciales para dividirlo en tres pedazos separados.

Si

\( \begin{equation} \begin{split} \dfrac{1 − x + x^2}{1 − x + 2x^3} &= \dfrac{A}{1 + x} + \dfrac{B}{1 − (1 + i)x} + \dfrac{C}{1 − (1 − i)x} \\ &= \dfrac{A(2x^2 − 2x + 1) + B(1 + x)(1 − (1 − i)x) + C(1 + x)(1 − (1 + i)x)}{1 − x + 2x^3} \end{split} \end{equation} \)

entonces esto nos da tres ecuaciones:

\(2A − B(1 − i) − C(1 + i) = 1\)

(a partir del coeficiente de\(x^2\));

\(−2A + B(1 − (1 − i)) + C(1 − (1 + i)) = −1\)

(del coeficiente de\(x\)); y\(A + B + C = 1\) (del término constante). El segundo de estos simplifica a\(−2A + iB − iC = −1\).

El álgebra se puede hacer de diferentes maneras y se pone un poco feo, pero estas tres ecuaciones se pueden resolver, resultando en\(A = \dfrac{3}{5}\),\(B = \dfrac{(2 − i)}{10}\),\(C = \dfrac{(2 + i)}{10}\).

Por lo tanto,

\(\dfrac{1 − x + x^2}{1 − x + 2x^3} = \dfrac{\dfrac{3}{5}}{1 + x} + \dfrac{\dfrac{(2-i)}{10}}{1 − (1 + i)x} + \dfrac{\dfrac{(2+i)}{10}}{1 − (1 − i)x} \).

El coeficiente de\(x^n\) en el primero de estos términos es\((\dfrac{3}{5})(−1)^n\); en el segundo, es\((\dfrac{(2−i)}{10}))(1+ i)^n\), y en el tercero, lo es\((\dfrac{(2 + i)}{10})(1 − i)^n\).

Concluimos que para cada\(n ≥ 0\), tenemos

\(b_n = \dfrac{3}{5} (-1)^n + \dfrac{2-i}{10}(1+i)^n + \dfrac{2+i}{10}(1-i)^n \).

Es algo sorprendente que estas fórmulas que involucran números complejos siempre funcionen (cuando\(n\) es un entero) para ser no solo números reales, ¡sino enteros! Una vez más, deberíamos verificar esta fórmula por varios valores de\(n\) para asegurarnos de que no hemos cometido errores en nuestros cálculos en el camino.

A partir de las condiciones iniciales,\(b_0 = 1\). Nuestra fórmula da

\(b_0 = \dfrac{3}{5} + \dfrac{(2 − i)}{10} + \dfrac{(2 + i)}{10} = 1\).

A partir de las condiciones iniciales,\(b_1 = 0\). Nuestra fórmula da

\(b_1 = -\dfrac{3}{5} + \dfrac{2 − i}{10} (1 + i) + \dfrac{2 + i}{10} (1 - i) = -\dfrac{3}{5} + \dfrac{(3 + i)}{10} + \dfrac{(3 - i)}{10} = 0\).

Por último, las condiciones iniciales dieron\(b_2 = 1\), y nuestra fórmula da

\(b_2 = \dfrac{3}{5} + \dfrac{2 − i}{10} (2i) + \dfrac{2 + i}{10} (2i) = \dfrac{3}{5} + \dfrac{(2i + 1)}{5} + \dfrac{(2i - 1)}{5} = 1\).

Podríamos continuar, pero esta es una verificación suficiente para inspirar una confianza razonable.

Ahora tenemos un método general que podemos aplicar para resolver relaciones recursivas lineales normales:

Método:

1) Reorganizar la relación de recurrencia en la forma

\[h_n − a_1h_{n−1} − a_2h_{n−2} − . . . − a_kh_{n−k} = f(n)\]

para alguna función\(f(n)\). Let

\[a(x) = 1 − a_1x − a_2x^2 − . . . − a_kx^k\]

2) Definir la función generadora

\[h(x) = h_0 + h_1x + h_2x^2 + . . . .\]

3) Encontrar una combinación lineal de la función generadora de manera que el coeficiente de\(x^m\) sea\(f(m)\) por cada m mayor o igual a algunos\(i ≥ k\):

\[ \begin{equation} \begin{split} h(x)&= h_0 &+ h_1x &+h_2x^2 &+h_3x^3 &+... &+ h_ix^i &+ ...\\ −a_1xh(x)&= &−a_1h_0x &−a_1h_1x^2 &-a_1h_2x^3 &−... &−a_1h_{i-1}x^i &-... \\ −a_2x^2h(x)&= & &−a_2h_0x^2 &−a_2h_1x^3 &+... &−a_2h_{i-2}x^i &+ ... \\ . & & & & & & . & \\ . & & & & & & . & \\ . & & & & & & . & \\ −a_kx^kh(x)&= & & & & &−a_kh_{i−k}x^i &+ ... \\ \therefore a(x)h(x)&= h_0 &+(h_1 − a_1h_0)x &+(h_2 − a_1h_1 − a_2h_0)x^2 &+... &... &+f(i)x^i &+... \end{split} \end{equation} \]

Entonces

\[h(x) = \dfrac{h_0 + (h_1 − a_1h_0)x + . . . + (h_{i−1} − a_1h_{i−2} + . . . + a_{k−1}h_{i−k})x^{i−1} + \sum_{n=i}^{\infty} f(n)x^n}{a(x)} \]

4) Factor\(a(x)\) (recuerde que puede usar raíces complejas), y encontrar una forma cerrada para

\[\sum_{n=i}^{\infty} f(n)x^n \]

5) Usar fracciones parciales para obtener expresiones que podamos expandir usando el teorema binomial generalizado.

6) Hacer sustituciones de variables si es necesario para obtener formularios que se parecen

\[\dfrac{A}{(1 + y)^n}\]

7) Utilizar el teorema binomial generalizado para encontrar\(h_n\), el coeficiente de\(x^n\) in\(h(x)\).

Ejercicio\(\PageIndex{1}\)

Para cada una de las siguientes secuencias definidas recursiblemente, utilice el método de generación de funciones para encontrar una fórmula explícita para el\(n^{\text{th}}\) término de la secuencia.

1. \(c_0 = 2\),\(c_1 = 0\),\(c_n = c_{n−1} + 2c_{n−2}\) para cada\(n ≥ 2\).
2. \(d_0 = 0\),\(d_1 = 1\),\(d_n = 2d_{n−2} + 1\) para cada\(n ≥ 2\).
3. \(e_0 = 2\),\(e_n = 3e_{n−1} − 2\) para cada\(n ≥ 1\).
4. \(f_0 = 1\),\(f_1 = 3\), y\(f_n = 4(f_{n−1} − f_{n−2})\) para cada\(n ≥ 2\).
5. \(g_0 = 2\),\(g_1 = 0\), y\(g_n = 2g_{n−1} − 2g_{n−2}\) para cada\(n ≥ 2\).
6. \(h_0 = \dfrac{1}{2}\)y\(h_n = 3h_{n−1} − \dfrac{1}{2}\) para cada\(n ≥ 1\).
7. \(i_0 = i_1 = 2\),\(i_2 = 0\), y\(i_n = 3i_{n−1} − 3i_{n−2} + i_{n−3}\) para cada\(n ≥ 3\).
8. \(j_0 = −1\),\(j_1 = 0\), y\(j_n = 2j_{n−1} + 3j_{n−2}\) para cada\(n ≥ 2\).
9. \( k_0 = 10\)y\(k_n = 11k_{n−1} − 10\) para cada\(n ≥ 1\).

Ejercicio\(\PageIndex{2}\)

1) Dejar\(p_n\) denotar el número de formas de construir una tubería de\(n\) unidades de largo, utilizando segmentos que son de plástico o metal, y (para cada material) vienen en longitudes de\(1\) unidad o\(2\) unidades. Por ejemplo,\(p_1 = 2\) ya que podemos usar un segmento\(1\) -unidad que sea de plástico o metal, y\(p_2 = 6\) ya que podemos usar cualquier tipo de segmento\(2\) -unidad, o cualquiera de las\(22\) posibles elecciones ordenadas de\(2\) segmentos que tienen cada uno una longitud de\(1\) unidad. Definir\(p_0 = 1\).

Determinar una relación de recurrencia para\(p_n\). Dar una prueba combinatoria de que tu relación de recurrencia sí resuelve este problema de conteo. Usa tu relación de recurrencia y el método de generación de funciones para encontrar una fórmula para\(p_n\).

Pista: Tu respuesta final debe ser

\(p_n = \dfrac{1}{2 \sqrt{3}} (1 + \sqrt{3})^{n+1} − \dfrac{1}{2 \sqrt{3}} (1 - \sqrt{3})^{n+1}\)

para cada\(n ≥ 0\).]

2) Dejar\(s_n\) denotar el número de listas de cualquier longitud que tengan la suma fija de\(n\), y de cuyas entradas provienen\(\{1, 2, 3\}\). Por ejemplo,\(s_2 = 2\) porque\((1, 1)\) y\((2)\) son las únicas listas de este tipo; y\(s_4 = 7\) porque las listas son\((3, 1)\)\((1, 3)\),,\((2, 2)\),\((2, 1, 1)\),\((1, 2, 1)\),\((1, 1, 2)\), y\((1, 1, 1, 1)\). Definir\(s_0 = 1\).

Determinar\(s_1\)\(s_3\),, y\(s_5\) encontrando todas las listas posibles. Dar una prueba combinatoria de que\(s_n = s_{n−1} + s_{n−2} + s_{n−3}\) para cada\(n ≥ 3\). Utilice esta relación de recurrencia para mostrar que la función generadora\(S(x)\) para\(\{sn\}\) es\(\dfrac{1}{1−x−x^2−x^3}\)