Función generadora

El artículo de Knuth "Polinomios de convolución" ^{[ 9 ]} define una clase generalizada de secuencias de polinomios de convolución mediante sus funciones generadoras especiales de la forma $${\displaystyle F(z)^{x}=\exp {\bigl (}x\log F(z){\bigr )}=\sum _{n=0}^{\infty }f_{n}(x)z^{n},}$$ para alguna función analítica F con una expansión en serie de potencias tal que F (0) = 1 .

Decimos que una familia de polinomios, f ₀ , f ₁ , f ₂ , ... , forma una familia de convolución si deg f _n ≤ n y si se cumple la siguiente condición de convolución para todo x , y y para todo n ≥ 0 : $${\displaystyle f_{n}(x+y)=f_{n}(x)f_{0}(y)+f_{n-1}(x)f_{1}(y)+\cdots +f_{1}(x)f_{n-1}(y)+f_{0}(x)f_{n}(y).}$$

Vemos que, para familias de convolución no idénticamente nulas, esta definición es equivalente a exigir que la secuencia tenga una función generadora ordinaria de la primera forma dada anteriormente.

Una secuencia de polinomios de convolución definida en la notación anterior tiene las siguientes propiedades:

• La secuencia n ! · f _n ( x ) es de tipo binomial.
• Los valores especiales de la secuencia incluyen f _n (1) = [ z ⁿ ] F ( z ) y f _n (0) = δ _{n ,0} , y
• Para arbitrario (fijo)${\displaystyle x,y,t\in \mathbb {C} }$, estos polinomios satisfacen fórmulas de convolución de la forma

$${\displaystyle {\begin{aligned}f_{n}(x+y)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(y)\\f_{n}(2x)&=\sum _{k=0}^{n}f_{k}(x)f_{n-k}(x)\\xnf_{n}(x+y)&=(x+y)\sum _{k=0}^{n}kf_{k}(x)f_{n-k}(y)\\{\frac {(x+y)f_{n}(x+y+tn)}{x+y+tn}}&=\sum _{k=0}^{n}{\frac {xf_{k}(x+tk)}{x+tk}}{\frac {yf_{n-k}(y+t(n-k))}{y+t(n-k)}}.\end{aligned}}}$$

Para un parámetro fijo distinto de cero${\displaystyle t\in \mathbb {C} }$, hemos modificado las funciones generadoras para estas secuencias de polinomios de convolución dadas por $${\displaystyle {\frac {zF_{n}(x+tn)}{(x+tn)}}=\left[z^{n}\right]{\mathcal {F}}_{t}(z)^{x},}$$ donde 𝓕 _t ( z ) se define implícitamente mediante una ecuación funcional de la forma 𝓕 _t ( z ) = F ( x 𝓕 _t ( z ) ^t ) . Además, podemos usar métodos matriciales (como en la referencia) para demostrar que dadas dos secuencias de polinomios de convolución, ⟨ f _n ( x ) ⟩ y ⟨ g _n ( x ) ⟩ , con sus respectivas funciones generadoras correspondientes, F ( z ) ^x y G ( z ) ^x , entonces para cualquier t tenemos la identidad $${\displaystyle \left[z^{n}\right]\left(G(z)F\left(zG(z)^{t}\right)\right)^{x}=\sum _{k=0}^{n}F_{k}(x)G_{n-k}(x+tk).}$$

Ejemplos de secuencias de polinomios de convolución incluyen la serie de potencias binomiales , 𝓑 _t ( z ) = 1 + z 𝓑 _t ( z ) ^t , los denominados polinomios de árbol , los números de Bell , B ( n ) , los polinomios de Laguerre y los polinomios de convolución de Stirling .

La multiplicación de funciones generadoras ordinarias produce una convolución discreta (el producto de Cauchy ) de las secuencias. Por ejemplo, la secuencia de sumas acumulativas (compárese con la fórmula de Euler-Maclaurin, ligeramente más general ). $${\displaystyle (a_{0},a_{0}+a_{1},a_{0}+a_{1}+a_{2},\ldots )}$$ de una secuencia con función generadora ordinaria G ( a _n ; x ) tiene la función generadora $${\displaystyle G(a_{n};x)\cdot {\frac {1}{1-x}}}$$ porque ⁠ 1 / 1 − x ⁠ es la función generadora ordinaria para la secuencia (1, 1, ...) . Véase también la sección sobre convoluciones en la sección de aplicaciones de este artículo, más abajo, para ver más ejemplos de resolución de problemas con convoluciones de funciones generadoras e interpretaciones.

Para enteros m ≥ 1 , tenemos las siguientes dos identidades análogas para las funciones generadoras modificadas que enumeran las variantes de secuencia desplazadas de ⟨ g _{n − m} ⟩ y ⟨ g _{n + m} ⟩ , respectivamente: $${\displaystyle {\begin{aligned}&z^{m}G(z)=\sum _{n=m}^{\infty }g_{n-m}z^{n}\\[4px]&{\frac {G(z)-g_{0}-g_{1}z-\cdots -g_{m-1}z^{m-1}}{z^{m}}}=\sum _{n=0}^{\infty }g_{n+m}z^{n}.\end{aligned}}}$$

Tenemos las siguientes expansiones en series de potencias respectivas para la primera derivada de una función generadora y su integral: $${\displaystyle {\begin{aligned}G'(z)&=\sum _{n=0}^{\infty }(n+1)g_{n+1}z^{n}\\[4px]z\cdot G'(z)&=\sum _{n=0}^{\infty }ng_{n}z^{n}\\[4px]\int _{0}^{z}G(t)\,dt&=\sum _{n=1}^{\infty }{\frac {g_{n-1}}{n}}z^{n}.\end{aligned}}}$$

La operación de diferenciación-multiplicación de la segunda identidad se puede repetir k veces para multiplicar la secuencia por n ^k , pero eso requiere alternar entre diferenciación y multiplicación. Si en cambio se realizan k diferenciaciones en secuencia, el efecto es multiplicar por el k- ésimo factorial descendente : $${\displaystyle z^{k}G^{(k)}(z)=\sum _{n=0}^{\infty }n^{\underline {k}}g_{n}z^{n}=\sum _{n=0}^{\infty }n(n-1)\dotsb (n-k+1)g_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .}$$

Utilizando los números de Stirling de segunda especie , eso se puede convertir en otra fórmula para multiplicar por${\displaystyle n^{k}}$de la siguiente manera (véase el artículo principal sobre transformaciones de funciones generadoras ): $${\displaystyle \sum _{j=0}^{k}{\begin{Bmatrix}k\\j\end{Bmatrix}}z^{j}F^{(j)}(z)=\sum _{n=0}^{\infty }n^{k}f_{n}z^{n}\quad {\text{for all }}k\in \mathbb {N} .}$$

Una inversión de orden negativo de esta fórmula de potencias de secuencia correspondiente a la operación de integración repetida se define mediante la transformación de la serie zeta y sus generalizaciones definidas como una transformación basada en derivadas de funciones generadoras , o alternativamente término a término mediante y realizando una transformación integral en la función generadora de secuencia. Las operaciones relacionadas de realizar integración fraccionaria en una función generadora de secuencia se discuten aquí .

En esta sección proporcionamos fórmulas para generar funciones que enumeran la secuencia { f _{an + b} } dada una función generadora ordinaria F ( z ) , donde a ≥ 2 , 0 ≤ b < a , y a y b son enteros (véase el artículo principal sobre transformaciones ). Para a = 2 , se trata simplemente de la conocida descomposición de una función en partes pares e impares (es decir, potencias pares e impares): $${\displaystyle {\begin{aligned}\sum _{n=0}^{\infty }f_{2n}z^{2n}&={\frac {F(z)+F(-z)}{2}}\\[4px]\sum _{n=0}^{\infty }f_{2n+1}z^{2n+1}&={\frac {F(z)-F(-z)}{2}}.\end{aligned}}}$$

De forma más general, supongamos que a ≥ 3 y que ω _a = exp ⁠ 2 πi / a ⁠ denota la a -ésima raíz primitiva de la unidad . Entonces, como aplicación de la transformada discreta de Fourier , tenemos la fórmula ^{[ 15 ].}$${\displaystyle \sum _{n=0}^{\infty }f_{an+b}z^{an+b}={\frac {1}{a}}\sum _{m=0}^{a-1}\omega _{a}^{-mb}F\left(\omega _{a}^{m}z\right).}$$

Para enteros m ≥ 1 , otra fórmula útil que proporciona progresiones aritméticas redondeadas hacia abajo algo invertidas —que efectivamente repiten cada coeficiente m veces— se genera mediante la identidad ^{[ 16 ].}$${\displaystyle \sum _{n=0}^{\infty }f_{\left\lfloor {\frac {n}{m}}\right\rfloor }z^{n}={\frac {1-z^{m}}{1-z}}F(z^{m})=\left(1+z+\cdots +z^{m-2}+z^{m-1}\right)F(z^{m}).}$$

Se dice que una serie de potencias formal (o función) F ( z ) es holonómica si satisface una ecuación diferencial lineal de la forma ^{[ 17 ].}$${\displaystyle c_{0}(z)F^{(r)}(z)+c_{1}(z)F^{(r-1)}(z)+\cdots +c_{r}(z)F(z)=0,}$$

donde los coeficientes c _i ( z ) están en el campo de las funciones racionales,${\displaystyle \mathbb {C} (z)}$. De forma equivalente,${\displaystyle F(z)}$es holónomo si el espacio vectorial sobre${\displaystyle \mathbb {C} (z)}$El conjunto generado por todas sus derivadas es de dimensión finita.

Dado que podemos eliminar los denominadores si es necesario en la ecuación anterior, podemos suponer que las funciones c _i ( z ) son polinomios en z . Por lo tanto, podemos ver una condición equivalente de que una función generadora es holonómica si sus coeficientes satisfacen una P -recurrencia de la forma $${\displaystyle {\widehat {c}}_{s}(n)f_{n+s}+{\widehat {c}}_{s-1}(n)f_{n+s-1}+\cdots +{\widehat {c}}_{0}(n)f_{n}=0,}$$

para todo n suficientemente grande ≥ n ₀ y donde los ĉ _i ( n ) son polinomios fijos de grado finito en n . En otras palabras, las propiedades de que una sucesión sea P -recursiva y tenga una función generadora holonómica son equivalentes. Las funciones holonómicas son cerradas bajo la operación de producto de Hadamard ⊙ sobre funciones generadoras.

Las funciones e ^z , log z , cos z , arcsin z ,${\displaystyle {\sqrt {1+z}}}$, la función dilogaritmo Li ₂ ( z ) , las funciones hipergeométricas generalizadas _p F _q (...; ...; z ) y las funciones definidas por la serie de potencias $${\displaystyle \sum _{n=0}^{\infty }{\frac {z^{n}}{(n!)^{2}}}}$$

y la no convergente $${\displaystyle \sum _{n=0}^{\infty }n!\cdot z^{n}}$$ son todos holonómicos.

Ejemplos de secuencias P -recursivas con funciones generadoras holonómicas incluyen f _n ≔ ⁠ 1 / n + 1 ⁠ ( ^{2 n} _n ) y f _n ≔ ⁠ 2 ⁿ / n ² + 1 ⁠ , donde secuencias como${\displaystyle {\sqrt {n}}}$y log n no son P -recursivas debido a la naturaleza de las singularidades en sus funciones generadoras correspondientes. De manera similar, las funciones con infinitas singularidades como tan z , sec z y Γ( z ) no son funciones holonómicas.

Las herramientas para procesar y trabajar con secuencias P -recursivas en Mathematica incluyen los paquetes de software proporcionados para uso no comercial en el sitio de software de combinatoria algorítmica del Grupo de Combinatoria RISC . A pesar de ser en su mayoría de código cerrado, herramientas particularmente potentes en este conjunto de software son el Guesspaquete para adivinar P -recurrencias para secuencias de entrada arbitrarias (útil para matemáticas experimentales y exploración) y el Sigmapaquete que puede encontrar P-recurrencias para muchas sumas y resolver para obtener soluciones de forma cerrada para P -recurrencias que involucran números armónicos generalizados . ^{[ 18 ]} Otros paquetes listados en este sitio RISC en particular están dirigidos a trabajar específicamente con funciones generadoras holonómicas .

Como se derivó anteriormente, la función generatriz ordinaria para la secuencia de cuadrados es: $${\displaystyle G(n^{2};x)={\frac {x(x+1)}{(1-x)^{3}}}.}$$

Con r = 1 , α = −1 , β = 3 , A ( x ) = 0 , y B ( x ) = x + 1 , podemos verificar que los cuadrados crecen como se esperaba, como los cuadrados: $${\displaystyle a_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {1+1}{1^{-1}\,\Gamma (3)}}\,n^{3-1}\left({\frac {1}{1}}\right)^{n}=n^{2}.}$$

La función generadora ordinaria para los números de Catalan es $${\displaystyle G(C_{n};x)={\frac {1-{\sqrt {1-4x}}}{2x}}.}$$

Con r = 1/4 , α = 1 , β = -1/2 , A ( x ) = 1/2 y B ( x ) = -1/2 , podemos concluir que , para los números de Catalan :​​​$${\displaystyle C_{n}\sim {\frac {B(r)}{r^{\alpha }\Gamma (\beta )}}\,n^{\beta -1}\left({\frac {1}{r}}\right)^{n}={\frac {-{\frac {1}{2}}}{\left({\frac {1}{4}}\right)^{1}\Gamma \left(-{\frac {1}{2}}\right)}}\,n^{-{\frac {1}{2}}-1}\left({\frac {1}{\,{\frac {1}{4}}\,}}\right)^{n}={\frac {4^{n}}{n^{\frac {3}{2}}{\sqrt {\pi }}}}.}$$

La función generadora ordinaria de una matriz bidimensional a _{m , n} (donde n y m son números naturales) es: $${\displaystyle G(a_{m,n};x,y)=\sum _{m,n=0}^{\infty }a_{m,n}x^{m}y^{n}.}$$Por ejemplo, dado que (1 + x ) ⁿ es la función generatriz ordinaria para los coeficientes binomiales para un n fijo , se puede buscar una función generatriz bivariada que genere los coeficientes binomiales ( ⁿ _k ) para todo k y n . Para ello, consideremos (1 + x ) ⁿ como una sucesión en n y encontremos la función generatriz en y que tenga estos valores de sucesión como coeficientes. Dado que la función generatriz para un ⁿ es: $${\displaystyle {\frac {1}{1-ay}},}$$La función generadora para los coeficientes binomiales es: $${\displaystyle \sum _{n,k}{\binom {n}{k}}x^{k}y^{n}={\frac {1}{1-(1+x)y}}={\frac {1}{1-y-xy}}.}$$Otros ejemplos de tales incluyen las siguientes funciones generadoras de dos variables para los coeficientes binomiales , los números de Stirling y los números eulerianos , donde ω y z denotan las dos variables: ^{[ 19 ]}$${\displaystyle {\begin{aligned}e^{z+wz}&=\sum _{m,n\geq 0}{\binom {n}{m}}w^{m}{\frac {z^{n}}{n!}}\\[4px]e^{w(e^{z}-1)}&=\sum _{m,n\geq 0}{\begin{Bmatrix}n\\m\end{Bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1}{(1-z)^{w}}}&=\sum _{m,n\geq 0}{\begin{bmatrix}n\\m\end{bmatrix}}w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {1-w}{e^{(w-1)z}-w}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}n\\m\end{matrix}}\right\rangle w^{m}{\frac {z^{n}}{n!}}\\[4px]{\frac {e^{w}-e^{z}}{we^{z}-ze^{w}}}&=\sum _{m,n\geq 0}\left\langle {\begin{matrix}m+n+1\\m\end{matrix}}\right\rangle {\frac {w^{m}z^{n}}{(m+n+1)!}}.\end{aligned}}}$$

Las funciones generadoras multivariadas surgen en la práctica al calcular el número de tablas de contingencia de enteros no negativos con totales de filas y columnas específicos. Supongamos que la tabla tiene r filas y c columnas; las sumas de las filas son t ₁ , t ₂ ... t _r y las sumas de las columnas son s ₁ , s ₂ ... s _c . Entonces, según IJ Good , ^{[ 20 ]} el número de tales tablas es el coeficiente de: $${\displaystyle x_{1}^{t_{1}}\cdots x_{r}^{t_{r}}y_{1}^{s_{1}}\cdots y_{c}^{s_{c}}}$$en:$${\displaystyle \prod _{i=1}^{r}\prod _{j=1}^{c}{\frac {1}{1-x_{i}y_{j}}}.}$$

Las expansiones de fracciones continuas de tipo Jacobi ( fracciones J y fracciones S , respectivamente), cuyos convergentes racionales h -ésimos representan series de potencias de orden 2h , son otra forma de expresar las funciones generadoras ordinarias típicamente divergentes para muchas secuencias especiales de una y dos variables. La forma particular de las fracciones continuas de tipo Jacobi ( fracciones J ) se expande como en la siguiente ecuación y tiene las siguientes expansiones de series de potencias correspondientes con respecto a z para algunas secuencias de componentes específicas, dependientes de la aplicación, {ab _i } y { c _i } , donde z ≠ 0 denota la variable formal en la segunda expansión de series de potencias que se da a continuación: ^{[ 21 ]}$${\displaystyle {\begin{aligned}J^{[\infty ]}(z)&={\cfrac {1}{1-c_{1}z-{\cfrac {{\text{ab}}_{2}z^{2}}{1-c_{2}z-{\cfrac {{\text{ab}}_{3}z^{2}}{\ddots }}}}}}\\[4px]&=1+c_{1}z+\left({\text{ab}}_{2}+c_{1}^{2}\right)z^{2}+\left(2{\text{ab}}_{2}c_{1}+c_{1}^{3}+{\text{ab}}_{2}c_{2}\right)z^{3}+\cdots \end{aligned}}}$$

Los coeficientes de${\displaystyle z^{n}}$, denotado abreviadamente por j _n ≔ [ z ⁿ ] J ^[∞] ( z ) , en las ecuaciones anteriores corresponden a soluciones matriciales de las ecuaciones: $${\displaystyle {\begin{bmatrix}k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\k_{0,3}&k_{1,3}&k_{2,3}&k_{3,3}&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}={\begin{bmatrix}k_{0,0}&0&0&0&\cdots \\k_{0,1}&k_{1,1}&0&0&\cdots \\k_{0,2}&k_{1,2}&k_{2,2}&0&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}}\cdot {\begin{bmatrix}c_{1}&1&0&0&\cdots \\{\text{ab}}_{2}&c_{2}&1&0&\cdots \\0&{\text{ab}}_{3}&c_{3}&1&\cdots \\\vdots &\vdots &\vdots &\vdots \end{bmatrix}},}$$

donde j ₀ ≡ k _0,0 = 1 , j _n = k _{0, n} para n ≥ 1 , k _{r , s} = 0 si r > s , y donde para todos los enteros p , q ≥ 0 , tenemos una relación de fórmula de adición dada por: $${\displaystyle j_{p+q}=k_{0,p}\cdot k_{0,q}+\sum _{i=1}^{\min(p,q)}{\text{ab}}_{2}\cdots {\text{ab}}_{i+1}\times k_{i,p}\cdot k_{i,q}.}$$

Para h ≥ 0 (aunque en la práctica cuando h ≥ 2 ), podemos definir las convergencias racionales h -ésimas a la fracción J infinita , J ^[∞] ( z ) , expandidas por: $${\displaystyle \operatorname {Conv} _{h}(z):={\frac {P_{h}(z)}{Q_{h}(z)}}=j_{0}+j_{1}z+\cdots +j_{2h-1}z^{2h-1}+\sum _{n=2h}^{\infty }{\widetilde {j}}_{h,n}z^{n}}$$

componente a componente a través de las secuencias P _h ( z ) y Q _h ( z ) , definidas recursivamente por: $${\displaystyle {\begin{aligned}P_{h}(z)&=(1-c_{h}z)P_{h-1}(z)-{\text{ab}}_{h}z^{2}P_{h-2}(z)+\delta _{h,1}\\Q_{h}(z)&=(1-c_{h}z)Q_{h-1}(z)-{\text{ab}}_{h}z^{2}Q_{h-2}(z)+(1-c_{1}z)\delta _{h,1}+\delta _{0,1}.\end{aligned}}}$$

Además, la racionalidad de la función convergente Conv _h ( z ) para todo h ≥ 2 implica ecuaciones de diferencias finitas adicionales y propiedades de congruencia satisfechas por la secuencia de j _n , y para M _h ≔ ab ₂ ⋯ ab _{h + 1} si h ‖ M _h entonces tenemos la congruencia $${\displaystyle j_{n}\equiv [z^{n}]\operatorname {Conv} _{h}(z){\pmod {h}},}$$

para elecciones no simbólicas y determinadas de las secuencias de parámetros {ab _i } y { c _i } cuando h ≥ 2 , es decir, cuando estas secuencias no dependen implícitamente de un parámetro auxiliar como q , x , o R como en los ejemplos contenidos en la tabla siguiente.

La siguiente tabla proporciona ejemplos de fórmulas de forma cerrada para las secuencias de componentes encontradas computacionalmente (y posteriormente demostradas como correctas en las referencias citadas ^{[ 22 ]} ) en varios casos especiales de las secuencias prescritas, j _n , generadas por las expansiones generales de las J -fracciones definidas en la primera subsección. Aquí definimos 0 < | a | , | b | , | q | < 1 y los parámetros${\displaystyle R,\alpha \in \mathbb {Z} ^{+}}$y x son indeterminadas con respecto a estas expansiones, donde las secuencias prescritas enumeradas por las expansiones de estas J- fracciones se definen en términos del símbolo q -Pochhammer , el símbolo Pochhammer y los coeficientes binomiales .

Los radios de convergencia de estas series, correspondientes a la definición de las fracciones J de tipo Jacobi dada anteriormente, son en general diferentes de los de las expansiones en series de potencias correspondientes que definen las funciones generadoras ordinarias de estas secuencias.

Las funciones generadoras nos brindan varios métodos para manipular sumas y establecer identidades entre ellas.

El caso más simple ocurre cuando s _n = Σ ⁿ _{k = 0} a _k . Entonces sabemos que S ( z ) = ⁠ A ( z ) / 1 − z ⁠ para las funciones generadoras ordinarias correspondientes.

Por ejemplo, podemos manipular $${\displaystyle s_{n}=\sum _{k=1}^{n}H_{k}\,,}$$ donde H _k = 1 + ⁠ 1 / 2 ⁠ + ⋯ + ⁠ 1 / k ⁠ son los números armónicos . Sea $${\displaystyle H(z)=\sum _{n=1}^{\infty }{H_{n}z^{n}}}$$ Sea la función generadora ordinaria de los números armónicos. Entonces $${\displaystyle H(z)={\frac {1}{1-z}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,,}$$ y por lo tanto $${\displaystyle S(z)=\sum _{n=1}^{\infty }{s_{n}z^{n}}={\frac {1}{(1-z)^{2}}}\sum _{n=1}^{\infty }{\frac {z^{n}}{n}}\,.}$$

Usando $${\displaystyle {\frac {1}{(1-z)^{2}}}=\sum _{n=0}^{\infty }(n+1)z^{n}\,,}$$La convolución con el numerador produce $${\displaystyle s_{n}=\sum _{k=1}^{n}{\frac {n+1-k}{k}}=(n+1)H_{n}-n\,,}$$ que también se puede escribir como $${\displaystyle \sum _{k=1}^{n}{H_{k}}=(n+1)(H_{n+1}-1)\,.}$$

Como otro ejemplo del uso de funciones generadoras para relacionar secuencias y manipular sumas, para una secuencia arbitraria ⟨ f _n ⟩ definimos las dos secuencias de sumas $${\displaystyle {\begin{aligned}s_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}f_{m}3^{n-m}\\[4px]{\tilde {s}}_{n}&:=\sum _{m=0}^{n}{\binom {n}{m}}(m+1)(m+2)(m+3)f_{m}3^{n-m}\,,\end{aligned}}}$$ para todo n ≥ 0 , y buscamos expresar las segundas sumas en términos de las primeras. Sugerimos un enfoque mediante funciones generadoras.

Primero, utilizamos la transformación binomial para escribir la función generadora para la primera suma como $${\displaystyle S(z)={\frac {1}{1-3z}}F\left({\frac {z}{1-3z}}\right).}$$

Dado que la función generadora para la secuencia ⟨ ( n + 1)( n + 2)( n + 3) f _n ⟩ está dada por $${\displaystyle 6F(z)+18zF'(z)+9z^{2}F''(z)+z^{3}F'''(z)}$$ Podemos escribir la función generadora para la segunda suma definida anteriormente de la forma $${\displaystyle {\tilde {S}}(z)={\frac {6}{(1-3z)}}F\left({\frac {z}{1-3z}}\right)+{\frac {18z}{(1-3z)^{2}}}F'\left({\frac {z}{1-3z}}\right)+{\frac {9z^{2}}{(1-3z)^{3}}}F''\left({\frac {z}{1-3z}}\right)+{\frac {z^{3}}{(1-3z)^{4}}}F'''\left({\frac {z}{1-3z}}\right).}$$

En particular, podemos escribir esta función generadora de suma modificada en la forma de $${\displaystyle a(z)\cdot S(z)+b(z)\cdot zS'(z)+c(z)\cdot z^{2}S''(z)+d(z)\cdot z^{3}S'''(z),}$$ para a ( z ) = 6(1 − 3 z ) ³ , b ( z ) = 18(1 − 3 z ) ³ , c ( z ) = 9(1 − 3 z ) ³ , y d ( z ) = (1 − 3 z ) ³ , donde (1 − 3 z ) ³ = 1 − 9 z + 27 z ² − 27 z ³ .

Finalmente, se deduce que podemos expresar las segundas sumas a través de las primeras sumas de la siguiente forma: $${\displaystyle {\begin{aligned}{\tilde {s}}_{n}&=[z^{n}]\left(6(1-3z)^{3}\sum _{n=0}^{\infty }s_{n}z^{n}+18(1-3z)^{3}\sum _{n=0}^{\infty }ns_{n}z^{n}+9(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)s_{n}z^{n}+(1-3z)^{3}\sum _{n=0}^{\infty }n(n-1)(n-2)s_{n}z^{n}\right)\\[4px]&=(n+1)(n+2)(n+3)s_{n}-9n(n+1)(n+2)s_{n-1}+27(n-1)n(n+1)s_{n-2}-(n-2)(n-1)ns_{n-3}.\end{aligned}}}$$

En este ejemplo, reformulamos un ejemplo de función generadora presentado en la Sección 7.3 de Matemáticas Concretas (véase también la Sección 7.1 de la misma referencia para ver ilustraciones de series de funciones generadoras). En particular, supongamos que buscamos el número total de maneras (denotado U _n ) de cubrir un rectángulo de 3xn con piezas de dominó sin marcar de 2x1. Sea la secuencia auxiliar, V _n , definida como el número de maneras de cubrir una sección rectangular de 3xn menos una esquina del rectángulo completo. Buscamos utilizar estas definiciones para dar una fórmula cerrada para U _n sin desglosar aún más esta definición para manejar los casos de dominós verticales y horizontales. Nótese que las funciones generadoras ordinarias para nuestras dos secuencias corresponden a la serie: $${\displaystyle {\begin{aligned}U(z)=1+3z^{2}+11z^{4}+41z^{6}+\cdots ,\\V(z)=z+4z^{3}+15z^{5}+56z^{7}+\cdots .\end{aligned}}}$$

Si consideramos las posibles configuraciones que se pueden dar comenzando desde el borde izquierdo del rectángulo de 3 por n , podemos expresar las siguientes relaciones de recurrencia mutuamente dependientes, o mutuamente recursivas , para nuestras dos secuencias cuando n ≥ 2 definidas como arriba donde U ₀ = 1 , U ₁ = 0 , V ₀ = 0 , y V ₁ = 1 : $${\displaystyle {\begin{aligned}U_{n}&=2V_{n-1}+U_{n-2}\\V_{n}&=U_{n-1}+V_{n-2}.\end{aligned}}}$$