Resolución de una relación de recurrencia mediante funciones generadoras

Question

Mi relación de recurrencia es D(n) = D(n - 1) + D(n - 2) + 5(n - 1); siendo las condiciones iniciales D(2),D(3) 6, 17 respectivamente. La función generadora G(z) para la secuencia D(n) viene dada

No sé cómo he conseguido esto. Por favor, ¿alguien puede dar una explicación para esto?

Gracias.

Answer 1

Tenga en cuenta que podemos trabajar hacia atrás desde $D(2)$ y $D(3)$ para descubrir lo que $D(1)$ y luego $D(0)$ debe ser para que la recurrencia se mantenga para $D(2)$ y $D(3)$ también. Encontramos que si $D(0)=0$ y $D(1)=1$ la recurrencia produce efectivamente $D(2)=6$ y $D(3)=17$ Así que podemos simplificar las cosas tomando $D(0)=0$ y $D(1)=1$ como condiciones iniciales.

Hay un par de formas ligeramente diferentes de proceder a partir de este punto; yo prefiero la utilizada en Graham, Knuth y Patashnik, Matemáticas concretas . Supongamos que $D(n)=0$ para todos $n<0$ . Entonces la recurrencia

$$D(n)=D(n-1)+D(n-2)+5(n-1)+5[n=0]+[n=1]\tag{1}$$

se mantiene para todo enteros $n$ donde los términos entre corchetes son Soportes Iverson . Multiplicar $(1)$ por $z^n$ y sumar sobre $n$ :

$$\begin{align*} \sum_nD(n)z^n&=\sum_nD(n-1)z^n+\sum_nD(n-2)z^n+5\sum_n(n-1)z^n+5+z\\\\ &=z\sum_nD(n-1)z^{n-1}+z^2\sum_nD(n-2)z^{n-2}+5\sum_nnz^n-5\sum_nz^n+5+z\\\\ &=z\sum_nD(n)z^n+z^2\sum_nD(n)z^n+\frac{5z}{(1-z)^2}-\frac5{1-z}+5+z\;. \end{align*}$$

Si $G(z)=\sum_nD(n)z^n$ ahora podemos escribir

$$G(z)=zG(z)+z^2G(z)+\frac{5z}{(1-z)^2}-\frac5{1-z}+5+z$$

y recoger los términos en $G(z)$ en el lado izquierdo de la ecuación para obtener

$$(1-z-z^2)G(z)=\frac{5z}{(1-z)^2}-\frac5{1-z}+5+z\;.$$

Como comprobación rápida, observe que

$$\begin{align*} \frac{5z}{(1-z)^2}&-\frac{5}{1-z}+5+z\\ &=5(z+2z^2+3z^3+\ldots)-5(1+z+z^2+\ldots)+5+z\\ &=5(2z^2+3z^3+4z^4+\ldots)-5(z^2+z^3+z^4+\ldots)+z\\ &=z+5z^2+10z^3+15z^4+\ldots\;, \end{align*}$$

que concuerda muy bien con

$$\begin{align*} (1-z-z^2)G(z)&=(1-z-z^2)(z+6z^2+17z^3+38z^4+\ldots)\\ &=z+5z^2+10z^3+15z^4+\ldots\;. \end{align*}$$

Así,

$$G(z)=\frac1{1-z-z^2}\left(5+z-\frac5{1-z}+\frac{5z}{(1-z)^2}\right)\;.$$

Esto no es igual a su

$$\frac1{1-z-z^2}\left(6+11z+\frac{15z^2}{1-z}+\frac{5z^3}{(1-z)^2}\right)\;,$$

como se puede comprobar al observar que el término constante cuando se expande

$$6+11z+\frac{15z^2}{1-z}+\frac{5z^3}{(1-z)^2}$$

es $6$ no $0$ .

Si se cambia la función a

$$\frac1{1-z-z^2}\left(6z^2+11z^3-\frac{5z^2}{1-z}+\frac{5z^3}{(1-z)^2}\right)\;,$$

se obtiene la función generadora de la $D$ secuencia con $D(0)$ y $D(1)$ fijado arbitrariamente en $0$ si lo cambias por

$$\frac1{1-z-z^2}\left(6+11z-\frac{5}{1-z}+\frac{5z}{(1-z)^2}\right)\;,$$

se obtiene la función generadora para la misma recurrencia, pero con condiciones iniciales $D(0)=6$ y $D(1)=17$ .

Answer 2

Definir la función generadora:

$$ G(z) = \sum_{n \ge 0} D(n) z^n $$

Toma tu recurrencia escrita como:

$$ D(n + 2) = D(n + 1) + D(n) + 5 (n + 1) $$

Multiplicar por $z^n$ , suma sobre $n \ge 0$ y reconocer algunas sumas:

$$ \frac{G(z) - D(0) - D(1) z}{z^2} = \frac{D(z) - D(0)}{z} + G(z) + \frac{5}{(1 - z)^2} $$

Resolver para $G(z)$ , dividido en fracciones parciales:

$\begin{align} G(z) &= \frac{D(0) + (D(1) - 3 D(0)) z - (2 D(1) - 3 D(0) - 5) z^2 + (D(1) - D(0)) z^3} {(1 - z)^2 (1 - z - z^2)} \\ &= \frac{(D(0) + 10) + (D(1)- D(0) + 5) z}{1 - z - z^2} - \frac{5}{1 - z} - \frac{5}{(1 - z)^2} \end{align}$

Ahora sabemos que los números de Fibonacci $F_n$ se definen por:

$$ F_{n + 2} = F_{n + 1} + F_n \qquad F_0 = 0, F_1 = 1 $$

con función generadora:

$$ F(z) = \sum_{n \ge 0} F_n z^n = \frac{z}{1 - z - z^2} $$

para que $1 / (1 - z - z^2)$ corresponde a la secuencia del $F_{n + 1}$ y así:

$$ D(n) = (D(0) + 10) F_{n + 1} + (D(1) - D(0) + 5) F_n - 5 - 5 (n + 1) $$

Introduzca los valores conocidos de $D(2)$ y $D(3)$ para obtener un sistema de ecuaciones para el $D(0)$ y $D(1)$ y ya está.