5.1: Generando funciones

Template:MathjaxLevin

Existe una herramienta extremadamente poderosa en matemáticas discretas que se utiliza para manipular secuencias llamadas función generadora. La idea es la siguiente: en lugar de una secuencia infinita (por ejemplo:\(2, 3, 5, 8, 12, \ldots\)) miramos una sola función que codifica la secuencia. Pero no una función que da el término\(n\) th como salida. En cambio, una función cuya serie de potencia (como del cálculo) “muestra” los términos de la secuencia. Entonces, por ejemplo, veríamos la serie de potencia\(2 + 3x + 5x^2 + 8x^3 + 12x^4 + \cdots\) que muestra la secuencia\(2, 3, 5, 8, 12, \ldots\) como coeficientes.

Una serie de poder infinito es simplemente una suma infinita de términos de la forma\(c_nx^n\) eran\(c_n\) es alguna constante. Entonces podríamos escribir una serie de poder como esta:

\ begin {ecuación*}\ suma_ {k=0} ^\ infty c_k x^k.\ end {ecuación*}

o expandido así

\ begin {ecuación*} c_0 + c_1x + c_2x^2 + c_3x^3 + c_4x^4 + c_5x^5 +\ cdots. \ end {ecuación*}

Cuando se ve en el contexto de funciones generadoras, llamamos a tal serie de potencia una serie generadora. La serie generadora genera la secuencia

\ begin {ecuación*} c_0, c_1, c_2, c_3, c_4, c_5,\ ldots. \ end {ecuación*}

En otras palabras, la secuencia generada por una serie generadora es simplemente la secuencia de coeficientes del polinomio infinito.

Ejemplo\(\PageIndex{1}\)

Qué secuencia está representada por la serie generadora\(3 + 8x^2 + x^3 + \frac{x^5}{7} + 100x^6 + \cdots\text{?}\)

Solución

Acabamos de leer los coeficientes de cada\(x^n\) term. So \(a_0 = 3\) since the coefficient of \(x^0\) is 3 (\(x^0 = 1\) so this is the constant term). What is \(a_1\text{?}\) It is NOT 8, since 8 is the coefficient of \(x^2\text{,}\) so 8 is the term \(a_2\) of the sequence. To find \(a_1\) we need to look for the coefficient of \(x^1\) which in this case is 0. So \(a_1 = 0\text{.}\) Continuing, we have \(a_2 = 8\text{,}\) \(a_3 = 1\text{,}\) \(a_4 = 0\text{,}\) and \(a_5 = \frac{1}{7}\text{.}\) So we have the sequence

\ begin {ecuación*} 3, 0, 8, 1,\ frac {1} {7}, 100,\ ldots\ end {ecuación*}

Tenga en cuenta que al discutir la generación de funciones, siempre comenzamos nuestra secuencia con\(a_0\text{.}\)

Ahora podría preguntarse muy naturalmente por qué haríamos tal cosa. Una razón es que la codificación de una secuencia con una serie de potencia nos ayuda a realizar un seguimiento de qué término es cuál en la secuencia. Por ejemplo, si escribimos la secuencia es\(1, 3, 4, 6, 9, \ldots, 24, 41,\ldots\) imposible determinar qué término\(24\) es (aunque estuviéramos de acuerdo en que se suponía que el primer término era\(a_0\)). No obstante, si en cambio escribiéramos la serie generadora, tendríamos\(1 + 3x + 4x^2 + 6x^3 + 9x^4 + \cdots + 24 x^{17} + 41 x^{18} + \cdots\text{.}\) Ahora bien está claro que 24 es el término 17 de la secuencia (es decir,\(a_{17} = 24\)). Por supuesto para obtener este beneficio podríamos haber mostrado nuestra secuencia de muchas maneras, quizás\(\fbox{1}_0 \fbox{3}_1 \fbox{4}_2 \fbox{6}_3 \fbox{9}_4 \cdots \fbox{24}_{17}\fbox{41}_{18}\cdots\text{,}\) pero no lo hacemos. El motivo es que la serie generadora parece una serie power ordinaria (aunque la estamos interpretando de manera diferente) así podemos hacer cosas con ella que ordinariamente hacemos con series power como escribir a qué converge.

Por ejemplo, a partir del cálculo sabemos que la serie power\(1 + x + \frac{x^2}{2} + \frac{x^3}{6} + \frac{x^4}{24} + \cdots + \frac{x^n}{n!} + \cdots\) converge a la función\(e^x\text{.}\) Así podemos usar\(e^x\) como una forma de hablar de la secuencia de coeficientes de la serie power para\(e^x\text{.}\) Cuando escribimos una bonita función compacta la cual tiene una serie de potencias infinitas que vemos como una serie generadora, entonces llamamos a esa función una función generadora. En este ejemplo, diríamos

\ begin {ecuación*} 1, 1,\ frac {1} {2},\ frac {1} {6},\ frac {1} {24},\ ldots,\ frac {1} {n!} ,\ ldots\ mbox {tiene función generadora} e^x\ end {ecuación*}

Funciones de generación de edificios

El\(e^x\) ejemplo es muy específico. Tenemos una secuencia bastante extraña, y la única razón por la que conocemos su función generadora es porque por casualidad conocemos la serie Taylor para\(e^x\text{.}\) Nuestro objetivo ahora es reunir algunas herramientas para construir la función generadora de una secuencia determinada en particular.

Veamos cuáles son las funciones generadoras para algunas secuencias muy simples. El más simple de todos: 1, 1, 1, 1, 1,... ¿Qué aspecto tiene la serie generadora? Es simplemente\(1 + x + x^2 + x^3 + x^4 + \cdots\text{.}\) Ahora, ¿podemos encontrar una fórmula cerrada para esta serie de potencia? ¡Sí! Esta serie en particular es realmente solo una serie geométrica con relación común\(x\text{.}\) Entonces, si usamos nuestra técnica de “multiplicar, desplazar y restar” de la Sección 2.2, tenemos

\ begin {alinear*} S\ amp = 1 + x + x^2 + x^3 +\ cdots\\\ subrayado {- xS}\ amp\ subrayado {\,\, = ~~~~~~ x + x^2 + x^3 + x^4 +\ cdots}\\ (1-x) S\ amp = 1\ end {alinear*}

Por lo tanto vemos que

\ begin {ecuación*} 1 + x + x^2 + x^3\ cdots =\ dfrac {1} {1-x}\ final {ecuación*}

Quizás recuerdes por el cálculo que esto sólo es cierto en el intervalo de convergencia para la serie power, en este caso cuando\(|x| \lt 1\text{.}\) Eso es cierto para nosotros, pero no nos importa. Nunca vamos a enchufar nada por\(x\text{,}\) lo que siempre y cuando haya algún valor del\(x\) que coincidan la función generadora y la serie generadora, estamos contentos. Y en este caso estamos contentos.

\(1,1,1,\ldots\)

La función generadora para\(1,1,1,1,1,1,\ldots\) es\(\dfrac{1}{1-x}\)

Usemos esta función generadora básica para encontrar funciones generadoras para más secuencias. Y si reemplazamos\(x\) por\(-x\text{.}\) Obtenemos

\ begin {ecuación*}\ frac {1} {1+x} = 1 - x + x^2 - x^3 +\ cdots\ mbox {que genera} 1, -1, 1, -1,\ ldots\ end {ecuación*}

Si\(3x\) reemplazamos\(x\) por obtenemos

\ begin {ecuación*}\ frac {1} {1-3x} = 1 + 3x + 9x^2 + 27x^3 +\ cdots\ mbox {que genera} 1, 3, 9, 27,\ lpuntos\ final {ecuación*}

Al reemplazar el\(x\) in\(\frac{1}{1-x}\) podemos obtener funciones generadoras para una variedad de secuencias, pero no todas. Por ejemplo, no se puede enchufar nada\(x\) para obtener la función generadora para\(2,2,2,2, \ldots\text{.}\) Sin embargo, aún no estamos perdidos. Observe que cada término de\(2, 2, 2, 2, \ldots\) es el resultado de multiplicar los términos de\(1, 1, 1, 1, \ldots\) por la constante 2. Así que multiplicar la función generadora por 2 también.

\ begin {ecuación*}\ frac {2} {1-x} = 2 + 2x + 2x^2 + 2x^3 +\ cdots\ mbox {que genera} 2, 2, 2, 2,\ lpuntos\ end {ecuación*}

De igual manera, para encontrar la función generadora para la secuencia\(3, 9, 27, 81, \ldots\text{,}\) observamos que esta secuencia es el resultado de multiplicar cada término de\(1, 3, 9, 27, \ldots\) por 3. Ya que tenemos la función generadora para\(1, 3, 9, 27, \ldots\) podemos decir

\ begin {ecuación*}\ frac {3} {1-3x} = 3\ cdot 1 + 3\ cdot 3x + 3\ cdot 9x^2 + 3\ cdot 27x^3 +\ cdots\ mbox {que genera} 3, 9, 27, 81,\ lpuntos\ end {ecuación*}

¿Qué pasa con la secuencia\(2, 4, 10, 28, 82, \ldots\text{?}\) Aquí los términos son siempre 1 más que poderes de 3. Es decir, hemos agregado las secuencias\(1,1,1,1,\ldots\) y\(1,3,9, 27,\ldots\) término por término. Por lo tanto, podemos obtener una función generadora agregando las respectivas funciones generadoras:

\ begin {alinear*} 2 + 4x + 10x^2 + 28x^3 +\ cdots\ amp = (1 + 1) + (1 + 3) x + (1 + 9) x^2 + (1 + 27) x^3 +\ cdots\\ amp = 1 + x + x^2 + x^3 +\ cdots + 1 + 3x + 9x^2 + 27x^3 +\ cdots\\\ amp =\ frac {1} {1-x} +\ frac {1} {1-3x}\ final {alinear*}

La diversión no se detiene ahí: si reemplazamos\(x\) en nuestra función generadora original por\(x^2\) obtenemos

\ begin {ecuación*}\ frac {1} {1-x^2} = 1 + x^2 + x^4 + x^6\ cdots\ mbox {que genera} 1, 0, 1, 0, 1, 0,\ lpuntos. \ end {ecuación*}

Cómo podríamos conseguir\(0,1,0,1,0,1,\ldots\text{?}\) Empezar con la secuencia anterior y cambiarla por 1. Pero, ¿cómo se hace esto? Para ver cómo funciona el cambio, primero intentemos obtener la función generadora para la secuencia\(0, 1, 3, 9, 27, \ldots\text{.}\) Sabemos que\(\frac{1}{1-3x} = 1 + 3x + 9x^2 + 27x^3 + \cdots\text{.}\) Para sacar el cero al frente, necesitamos que se vea la serie generadora\(x + 3x^2 + 9x^3 + 27x^4+ \cdots\) (así que no hay término constante). Multiplicar por\(x\) tiene este efecto. Entonces la función generadora para\(0, 1, 3, 9, 27, \ldots\) es\(\frac{x}{1-3x}\text{.}\) Esto también funcionará para obtener la función generadora para\(0,1,0,1,0,1,\ldots\text{:}\)

\ begin {ecuación*}\ frac {x} {1-x^2} = x + x^3 + x^5 +\ cdots\ mbox {que genera} 0, 1, 0, 1, 0, 1\ lpuntos\ final {ecuación*}

¿Y si añadimos las secuencias\(1,0,1,0,1,0,\ldots\) y\(0,1,0,1,0,1,\ldots\) término por término? Deberíamos obtener\(1,1,1,1,1,1\ldots\text{.}\) ¿Qué pasa cuando agregamos las funciones generadoras? Funciona (pruébalo)!

\ begin {ecuación*}\ frac {1} {1-x^2} +\ frac {x} {1-x^2} =\ frac {1} {1-x}. \ end {ecuación*}

Aquí hay uno furtivo: qué pasa si tomas la derivada de\(\frac{1}{1-x}\text{?}\) We get\(\frac{1}{(1-x)^2}\text{.}\) Por otro lado, si diferenciamos término por término en la serie power, obtenemos\((1 + x + x^2 + x^3 + \cdots)' = 1 + 2x + 3x^2 + 4x^3 + \cdots\) cual es la serie generadora para\(1, 2, 3, 4, \ldots\text{.}\) Esto dice

\(1,2,3,\ldots\)

La función generadora para\(1, 2, 3, 4, 5, \ldots\) es\(\d\frac{1}{(1-x)^2}.\)

Toma una segunda derivada:\(\frac{2}{(1-x)^3} = 2 + 6x + 12x^2 + 20x^3 + \cdots\text{.}\) Así\(\frac{1}{(1-x)^3} = 1 + 3x + 6x^2 + 10x^3 + \cdots\) es una función generadora para los números triangulares,\(1,3,6,10\ldots\) (aunque aquí tenemos\(a_0 = 1\) mientras que\(T_0 = 0\) normalmente).

Diferenciación

Hemos visto cómo encontrar funciones generadoras a partir del\(\frac{1}{1-x}\) uso de multiplicación (por una constante o por\(x\)), sustitución, adición y diferenciación. Para usar cada uno de estos, debes notar una forma de transformar la secuencia\(1,1,1,1,1\ldots\) en tu secuencia deseada. Esto no siempre es fácil. Tampoco es realmente la forma en que hemos analizado las secuencias. Una cosa que hemos considerado a menudo es la secuencia de diferencias entre términos de una secuencia. Esto también resultará útil para encontrar funciones generadoras. La secuencia de diferencias suele ser más simple que la secuencia original. Entonces, si conocemos una función generadora para las diferencias, nos gustaría usar esta para encontrar una función generadora para la secuencia original.

Por ejemplo, consideremos la secuencia\(2, 4, 10, 28, 82, \ldots\text{.}\) Cómo podríamos pasar a la secuencia de primeras diferencias:\(2, 6, 18, 54,\ldots\text{?}\) Queremos restar 2 de la 4, 4 de la 10, 10 de la 28, y así sucesivamente. Entonces, si restamos (término por término) la secuencia\(0, 2, 4, 10, 28,\ldots\) de\(2, 4, 10, 28\ldots\text{,}\) nos fijaremos. Podemos obtener la función generadora para\(0,2,4,10,28,\ldots\) a partir de la función generadora para\(2,4,10,28\ldots\) multiplicando por\(x\text{.}\) Use\(A\) para representar la función generadora para\(2, 4, 10, 28, 82, \ldots\) Entonces:

\ begin {alinear*} A\ amp = 2 + 4x + 10x^2 +28x^3 + 82x^4 +\ cdots\\\ subrayado {-xA}\ amp\ subrayado {\,\, = 0 + 2x + 4x^2 + 10x^3 + 28 x^4 + 82x^5 +\ cdots}\\ (1-x) A\ amp = 2 + 2x + 6x^2 + 18x^3 + 54x^4 +\ cdots\ end {align*}

Si bien no obtenemos exactamente la secuencia de diferencias, sí conseguimos algo cercano. En este caso particular, ya conocemos la función generadora\(A\) (la encontramos en la sección anterior) pero la mayoría de las veces utilizaremos esta técnica de diferenciación para encontrar\(A\text{:}\) si tenemos la función generadora para la secuencia de diferencias, entonces podemos resolver para\(A\text{.}\)

Ejemplo\(\PageIndex{2}\)

Encuentra una función generadora para\(1, 3, 5, 7, 9,\ldots\text{.}\)

Solución

Observe que la secuencia de diferencias es constante. Sabemos encontrar la función generadora para cualquier secuencia constante. Así denotan la función generadora para\(1, 3, 5, 7, 9, \ldots\) by \(A\text{.}\) We have

\ begin {alinear*} A\ amp = 1 + 3x + 5x^2 + 7x^3 + 9x^4 +\ cdots\\\ subrayado {-xA}\ amp\ subrayado {\,\, = 0 + x + 3x^2 + 5x^3 + 7x^4 + 9x^5 +\ cdots}\\ (1-x) A\ amp = 1 + 2x + 2x^2 + 2x^3 + 2x^4 +\ cdots\ end {align*}

Sabemos que\(2x + 2x^2 + 2x^3 + 2x^4 + \cdots = \dfrac{2x}{1-x}\text{.}\) Thus

\ begin {ecuación*} (1-x) A = 1 +\ frac {2x} {1-x}. \ end {ecuación*}

Ahora soluciona para\(A\text{:}\)

\ begin {ecuación*} A =\ frac {1} {1-x} +\ frac {2x} {(1-x) ^2} =\ frac {1+x} {(1-x) ^2}. \ end {ecuación*}

¿Esto tiene sentido? Antes de simplificar las dos fracciones en una, estábamos agregando la función generadora para la secuencia\(1,1,1,1,\ldots\) to the generating function for the sequence \(0, 2, 4, 6, 8, 10, \ldots\) (remember \(\frac{1}{(1-x)^2}\) generates \(1,2,3,4,5, \ldots\text{,}\) multiplying by \(2x\) shifts it over, putting the zero out front, and doubles each term). If we add these term by term, we get the correct sequence \(1,3,5,7, 9, \ldots\text{.}\)

Ahora que tenemos una función generadora para los números impares, podemos usarla para encontrar la función generadora para los cuadrados:

Ejemplo\(\PageIndex{3}\)

Encuentra la función generadora para\(1, 4, 9, 16, \ldots\text{.}\) Nota que tomamos\(1 = a_0\text{.}\)

Solución

Nuevamente llamamos a la función generadora para la secuencia\(A\text{.}\) Using differencing:

\ begin {alinear*} A\ amp = 1 + 4x + 9x^2 + 16x^3 +\ cdots\\\ subrayado {- xA}\ amp\ subrayado {\,\, = 0 + x + 4x^2 + 9x^3 + 16x^4 +\ cdots}\\ (1-x) A\ amp = 1 + 3x + 5x^2 + 7x^3 +\ puntos\ end {align*}

Desde\(1 + 3x + 5x^2 + 7x^3 + \cdots = \d\frac{1+x}{(1-x)^2}\) we have \(A = \d\frac{1+x}{(1-x)^3}\text{.}\)

En cada uno de los ejemplos anteriores, encontramos la diferencia entre términos consecutivos lo que nos dio una secuencia de diferencias para la cual conocíamos una función generadora. Podemos generalizar esto a relaciones más complicadas entre términos de la secuencia. Por ejemplo, si sabemos que la secuencia satisface la relación de recurrencia\(a_n = 3a_{n-1} - 2a_{n-2}\text{?}\) En otras palabras, si tomamos un término de la secuencia y restamos 3 veces el término anterior y luego sumamos 2 veces el término antes de eso, obtenemos 0 (since\(a_n - 3a_{n-1} + 2a_{n-2} = 0\)). Eso aguantará para todos menos los dos primeros términos de la secuencia. Entonces después de los dos primeros términos, la secuencia de resultados de estos cálculos sería una secuencia de 0's, para lo cual definitivamente conocemos una función generadora.

Ejemplo\(\PageIndex{4}\)

La secuencia\(1, 3, 7, 15, 31, 63, \ldots\) satisface la relación de recurrencia\(a_n = 3a_{n-1} - 2a_{n-2}\text{.}\) Encuentra la función generadora para la secuencia.

Solución

Llamar a la función generadora para la secuencia\(A\text{.}\) We have

\ begin {alinear*} A\ amp = 1 + 3x + 7x^2 + 15x^3 + 31x^4 +\ cdots + a_nx^n +\ cdots\\ -3xA\ amp = 0 - 3x - 9x^2 - 21x^3 - 45x~4 -\ cdots - 3a_ {n-1} x^n -\ cdots\\ subrayado {+~~2x^2a_ {~} ^ {~^ {~}}}\ amp\ subrayado {\,\, = 0 + 0x + 2x^2 + 6x^3 + 14x^4 +\ cdots + 2a_ {n-2} x^n +\ cdots}\\ (1-3x+2x^2) A\ amp = 1\ final {alinear*}

Nosotros multiplicamos\(A\) by \(-3x\) which shifts every term over one spot and multiplies them by \(-3\text{.}\) On the third line, we multiplied \(A\) by \(2x^2\text{,}\) which shifted every term over two spots and multiplied them by 2. When we add up the corresponding terms, we are taking each term, subtracting 3 times the previous term, and adding 2 times the term before that. This will happen for each term after \(a_1\) because \(a_n - 3a_{n-1} + 2a_{n-2} = 0\text{.}\) In general, we might have two terms from the beginning of the generating series, although in this case the second term happens to be 0 as well.

Ahora solo tenemos que resolver para\(A\text{:}\)

\ begin {ecuación*} A =\ frac {1} {1 - 3x + 2x^2}. \ end {ecuación*}

Multiplicación y Sumas Parciales

¿Qué pasa con las secuencias cuando multiplicas dos funciones generadoras? Veamos:\(A = a_0 + a_1x + a_2x^2 + \cdots\) y\(B = b_0 + b_1x + b_2x^2 + \cdots\text{.}\) Para multiplicar\(A\) y\(B\text{,}\) necesitamos hacer mucha distribución (¿infinito FOIL?) pero ten en cuenta que agruparemos como términos y solo necesitamos anotar los primeros términos para ver el patrón. El término constante es\(a_0b_0\text{.}\) El coeficiente de\(x\) es\(a_0b_1 + a_1b_0\text{.}\) Y así sucesivamente. Obtenemos:

\ begin {ecuación*} AB = a_0b_0 + (a_0b_1 + a_1b_0) x + (a_0b_2 + a_1b_1 + a_2b_0) x^2 + (a_0b_3 + a_1b_2 + a_2b_1 + a_3b_0) x^3 +\ cdots\ final {ecuación*}

Ejemplo\(\PageIndex{5}\)

“Multiplicar” la secuencia\(1, 2, 3, 4, \ldots\) por la secuencia\(1, 2, 4, 8, 16, \ldots\text{.}\)

Solución

El nuevo término constante es justo\(1 \cdot 1\text{.}\) The next term will be \(1\cdot 2 + 2 \cdot 1 = 4\text{.}\) The next term: \(1 \cdot 4 + 2 \cdot 2 + 3 \cdot 1 = 11\text{.}\) One more: \(1 \cdot 8 + 2 \cdot 4 + 3 \cdot 2 + 4 \cdot 1 = 28\text{.}\) The resulting sequence is

\ begin {ecuación*} 1, 4, 11, 28, 57,\ ldots\ end {ecuación*}

Dado que la función generadora para\(1,2,3,4, \ldots\) is \(\frac{1}{(1-x)^2}\) and the generating function for \(1,2,4,8, 16, \ldots\) is \(\frac{1}{1-2x}\text{,}\) we have that the generating function for \(1,4, 11, 28, 57, \ldots\) is \(\frac{1}{(1-x)^2(1-2x)}\)

Considera el caso especial cuando multiplicas una secuencia por\(1, 1, 1, \ldots\text{.}\) Por ejemplo, multiplicar\(1,1,1,\ldots\) por\(1, 2, 3, 4, 5\ldots\text{.}\) El primer término es\(1\cdot 1 = 1\text{.}\)\(1\cdot 2 + 1 \cdot 1 = 3\text{.}\) Entonces Entonces\(1\cdot 3 + 1\cdot 2 + 1 \cdot 1 = 6\text{.}\) El siguiente término será 10. Estamos consiguiendo los números triangulares. Más precisamente, obtenemos la secuencia de sumas parciales de\(1,2,3,4,5, \ldots\text{.}\) En cuanto a generar funciones, tomamos\(\frac{1}{1-x}\) (generando\(1,1,1,1,1\ldots\)) y la multiplicamos por\(\frac{1}{(1-x)^2}\) (generando\(1,2,3,4,5,\ldots\)) y esto da\(\frac{1}{(1-x)^3}\text{.}\) Esto no debería ser una sorpresa ya que encontramos la misma función generadora para el números triangulares anteriores.

El punto es, si necesitas encontrar una función generadora para la suma de los primeros\(n\) términos de una secuencia particular, y conoces la función generadora para esa secuencia, puedes multiplicarla por\(\frac{1}{1-x}\text{.}\) Para volver de la secuencia de sumas parciales a la secuencia original, miras la secuencia de diferencias. Cuando obtienes la secuencia de diferencias terminas multiplicando por\(1-x\text{,}\) o equivalentemente, dividiendo por\(\frac{1}{1-x}\text{.}\) Multiplicar por\(\frac{1}{1-x}\) da sumas parciales, dividiendo por\(\frac{1}{1-x}\) da diferencias.

Resolución de relaciones de recurrencia con funciones generadoras

Concluimos con un ejemplo de una de las muchas razones por las que estudiar la generación de funciones es útil. Podemos usar funciones generadoras para resolver relaciones de recurrencia.

Ejemplo\(\PageIndex{6}\)

Resolver la relación de recurrencia\(a_n = 3a_{n-1} - 2a_{n-2}\) con condiciones iniciales\(a_0 = 1\) y\(a_1 = 3\text{.}\)

Solución

Vimos en un ejemplo anterior que esta relación de recurrencia da la secuencia\(1, 3, 7, 15, 31, 63, \ldots\) which has generating function \(\dfrac{1}{1 - 3x + 2x^2}\text{.}\) We did this by calling the generating function \(A\) and then computing \(A - 3xA + 2x^2A\) which was just 1, since every other term canceled out.

Pero, ¿cómo nos ayuda conocer la función generadora? Primero, dividir la función generadora en dos más simples. Para ello, podemos utilizar la descomposición parcial de la fracción. Comience por factorizar el denominador:

\ begin {ecuación*}\ frac {1} {1-3x + 2x^2} =\ frac {1} {(1-x) (1-2x)}. \ end {ecuación*}

La descomposición parcial de la fracción nos dice que podemos escribir esta facción como la suma de dos fracciones (descomponemos la fracción dada):

\ begin {ecuación*}\ frac {1} {(1-x) (1-2x)} =\ frac {a} {1-x} +\ frac {b} {1-2x}\ text {~~ para algunas constantes} a\ text {y} b.\ end {ecuación*}

Para encontrar\(a\) and \(b\) we add the two decomposed fractions using a common denominator. This gives

\ begin {ecuación*}\ frac {1} {(1-x) (1-2x)} =\ frac {a (1-2x) + b (1-x)} {(1-x) (1-2x)}. \ end {ecuación*}

entonces

\ begin {ecuación*} 1 = a (1-2x) + b (1-x). \ end {ecuación*}

Esto debe ser cierto para todos los valores de\(x\text{.}\) If \(x = 1\text{,}\) then the equation becomes \(1 = -a\) so \(a = -1\text{.}\) When \(x = \frac{1}{2}\) we get \(1 = b/2\) so \(b = 2\text{.}\) This tells us that we can decompose the fraction like this:

\ begin {ecuación*}\ frac {1} {(1-x) (1-2x)} =\ frac {-1} {1-x} +\ frac {2} {1-2x}. \ end {ecuación*}

Esto completa la descomposición parcial de la fracción. Observe que estas dos fracciones están generando funciones que conocemos. De hecho, deberíamos poder ampliar cada una de ellas.

\ begin {ecuación*}\ frac {-1} {1-x} = -1 - x - x^2 -x^3 - x^4 -\ cdots\ mbox {que genera} -1, -1, -1, -1, -1,\ lpuntos. \ end {ecuación*}\ begin {ecuación*}\ frac {2} {1-2x} = 2 + 4x + 8x^2 + 16x^3 + 32x^4 +\ cdots\ mbox {que genera} 2, 4, 8, 16, 32,\ lpuntos. \ end {ecuación*}

Podemos dar una fórmula cerrada para\(n\)th term of each of these sequences. The first is just \(a_n = -1\text{.}\) The second is \(a_n = 2^{n+1}\text{.}\) The sequence we are interested in is just the sum of these, so the solution to the recurrence relation is

\ begin {ecuación*} a_n = 2^ {n+1} - 1\ end {ecuación*}

Ahora podemos agregar funciones generadoras a nuestra lista de métodos para resolver relaciones de recurrencia.