生成函数解析

生成函数是一种解决递归关系的方法。

让我们考虑一下实数的序列a0, a1, a2 …. ar。对于给定的在t处包含零值的实数区间, 函数G（t）由以下序列定义：G（t）= a0, a1t + a2 t2 +⋯+ ar tr + ……….等式（i）

该函数G（t）被称为序列ar的生成函数。

现在, 对于恒定序列1、1、1、1 ….., 生成函数为

可以表示为

G（t）=（1-t）-1 = 1 + t + t2 + t3 + t4 +⋯[通过二项式展开]

与等式（i）进行比较, 我们得到

a0 = 1, a1 = 1, a2 = 1, 依此类推。

例如, 常数序列1, 2, 3, 4, 5, ..生成函数为G（t）=, 因为它可以表示为G（t）=（1-t）-2 = 1 + 2t + 3t2 + 4t3 +⋯+（r + 1）tr

与等式（i）进行比较, 我们得到a0 = 1, a1 = 2, a2 = 3, a3 = 4, 依此类推。

Zr的生成函数（Z≠0且Z为常数）由G（t）= 1 + Zt + Z2 t2 + Z3 t3 +⋯+ Zr tr G（t）= [假定| Zt | <1]给出因此, G（t）=生成Zr, Z≠0

同样, 如果a（1）r具有生成函数G1（t）, 而a（2）r具有生成函数G2（t）, 则λ1a（1）r +λ2a（2）r具有生成函数λ1 G1（t）+λ2G2（t）。在这里, λ1和λ2是常数。

应用领域

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

示例：解决递归关系ar + 2-3ar + 1 + 2ar = 0

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

解决方案：让我们假设

将等式（i）乘以tr并从r = 0到∞求和

（a2 + a3 t + a4 t2 +⋯）-3（a1 + a2 t + a3 t2 +⋯）+2（a0 + a1 t + a2 t2 +⋯）= 0 [∴G（t）= a0 + a1 t + a2 t2 + ⋯]

+ 2G（t）= 0 …………公式（ii）

现在, 将a0 = 2和a1 = 3代入方程式（ii）并求解, 我们得到

将t = 1放在等式（iii）的两边以找到A。因此-1 =-A∴A = 1

将t =放在等式（iii）的两边即可找到B。因此= B∴B = 1

因此, G（t）= .hence, ar = 1 + 2r。