生成函数

生成函数是一种求解递推关系的方法。

假设有一个实数序列 a₀, a₁, a₂....a_r。对于某个包含零值的实数区间，在 t 处的值由以下级数定义的函数 G(t) 给出：
            G(t)= a₀, a₁t+a₂ t²+⋯+a_r t_r+............公式 (i)

该函数 G(t) 称为序列 a_r 的生成函数。

现在，对于常数序列 1, 1, 1, 1.....，生成函数为

它可以表示为

            G(t) =(1-t)^-1=1+t+t² +t³+t⁴+⋯[通过二项式展开]

将其与公式 (i) 进行比较，我们得到

            a₀=1,a₁=1,a₂=1 等等。

对于常数序列 1,2,3,4,5,..，生成函数为
            G(t) = 因为它能表示为
            G(t) =(1-t)^-2=1+2t+3t² +4t³+⋯+(r+1) t^r

将其与公式 (i) 进行比较，我们得到
a₀=1,a₁=2,a₂=3,a₃=4 等等。

Z^r 的生成函数 (Z≠0 且 Z 为常数) 由以下公式给出
            G(t)= 1+Zt+Z² t²+Z³ t³+⋯+Z^r t^r
            G(t)=       [假设 |Zt|<1]
因此，      G(t)= 生成 Z^r,Z≠0

此外，如果 a⁽¹⁾_r 具有生成函数 G₁(t) 且 a⁽²⁾_r 具有生成函数 G₂(t)，则 λ₁ a⁽¹⁾_r+λ₂ a⁽²⁾_r 具有生成函数 λ₁ G₁(t)+ λ₂ G₂(t)。这里 λ₁ 和 λ₂ 是常数。

应用领域

生成函数可用于以下目的 -

• 求解递推关系
• 证明一些组合恒等式
• 求序列项的渐近公式

示例： 求解递推关系 a_r+2-3a_r+1+2a_r=0

通过具有初始条件 a₀=2 和 a₁=3 的生成函数的方法。

解决方案： 让我们假设

将方程 (i) 乘以 t^r 并从 r = 0 到 ∞ 求和，我们有

(a₂+a₃ t+a₄ t²+⋯)-3(a₁+a₂ t+a₃ t²+⋯)+2(a₀+a₁ t+a₂ t²+⋯)=0
     [∴ G(t)=a₀+a₁ t+a₂ t²+⋯]

+2G(t)=0............公式 (ii)

现在，在方程 (ii) 中代入 a₀=2 和 a₁=3 并求解，我们得到

在方程 (iii) 的两边都代入 t=1 以求得 A。因此
            -1=- A       ∴ A = 1

在方程 (iii) 的两边都代入 t= 以求得 B。因此
            = B       ∴ B = 1

因此 G (t) = 。因此，a_r=1+2^r。