数列展示架:母函数普通母函数篇

数列展示架: 母函数(Generating Function)

Updated on Oct14th 2024

A generating function is a clothesline on which we hang up a sequence of numbers for display.
----Herbert Wilf

GF 有很多不同的形式, 在解决不同的问题时我们按需选择合适的形式, 常用的一般有 OGF (Ordinary GF), EGF (Exponential GF).

假设序列 $a_i$ 的 OGF 为 $F(x)$ , EGF 为 $G(x)$ , 则:

F(x) = \sum_{i = 0}^{\infin} a_ix^i\\ G(x) = \sum_{i = 0}^{\infin} \dfrac{a_ix^i}{i!}

级数的价值一般体现在它们收敛的时候, 这时候就可以用一个有限的值或表达式表达一个无穷的东西. GF 也是一样, 我们找到令含有 GF 的表达式收敛的 $x$ 取值, 借此找到我们想要的性质.

一般情况下, 母函数可以用来求解线性递推问题. 即, 某个数列满足递推式, 即 $a_i$ 可以表示为 $a_{i - k_1}$ , $a_{i - k_2}$ , …一些项的线性组合.

问题: 对于 $q \neq 1$ , 求:

\sum_{i = 0}^n aq^i

假设 $a_i$ 为常数序列, $a_i = a$ , 它的 GF 为 $F(x)$ .

\begin{aligned} F(x) &= \sum_{i = 0}^{\infin} ax^i\\ a + xF(x) &= ax^0 + \sum_{i = 1}^{\infin} ax^i\\ a + xF(x) &= \sum_{i = 0}^{\infin} ax^i\\ a + xF(x) &= F(x)\\ a &= (1 - x)F(x)\\ \frac a{1 - x} &= F(x) \end{aligned}

结合中学知识, 我们知道当 $x\in (-1,1)$ 时, 和式 $\displaystyle{\sum_{i = 0}^{\infin} x^i}$ 收敛. 根据上面的式子, 我们可以直接读出收敛值 $\frac 1{1 - x}$ .

当 $x$ 超出此范围, 我们仍可以借助这个式子求出前 $n$ 项和.

F(x) - x^{n + 1}F(x) = \sum_{i = 0}^{n} ax^i\\ (1 - x^{n + 1})F(x) = \sum_{i = 0}^{n} ax^i\\ \frac{a(1 - x^{n + 1})}{1 - x} = \sum_{i = 0}^{n} ax^i\\ \frac{(1 - x^{n + 1})}{1 - x} = \sum_{i = 0}^{n} x^i\\

因此, 对于所有 $q \neq 1$ , 我们得到了等比数列的前 $n$ 项和公式:

\sum_{i = 0}^n q^i = \frac{(1 - q^{n + 1})}{1 - q}\\ \sum_{i = 1}^n a_1q^{i - 1} = \frac{a_1(1 - q^{n})}{1 - q}

思考在这个过程中 GF 帮我们做了什么. 在传统推到中, 我们使用到了错位相减法:

(1 - x)\sum_{i = 0}^{n} = 1 - x^{n + i}\\ \sum_{i = 0}^{n} = \frac{1 - x^{n + i}}{(1 - x)}

而 GF 则是把这种方法推广到了无穷项, 更加普适, 更加形式化.

既然 GF 可以帮我们进行错位相减, 那么等差乘等比这个经典错位相减问题自然也可以从这个角度思考.

问题: 对于 $q \neq 1$ , 求:

\sum_{i = 0}^n (a + id)q^i

假设等差数列 $a_i = a + id$ , 设它的 OGF 为 $F(x)$ .

\begin{aligned} F(x) &= \sum_{i = 0}^{\infin} (a + id)x^i\\ xF(x) &= \sum_{i = 1}^{\infin} (a + (i - 1)d)x^i\\ (1 - x)F(x) &= a + \sum_{i = 1}^{\infin} dx^i\\ (1 - x)F(x) &= a + \frac{dx}{1 - x}\\ F(x) &= \frac a{1 - x} + \frac{dx}{(1 - x)^2}\\ \sum_{i = 0}^n (a + id)q^i &= (1 - x^{n + 1})F(x) - \sum_{i = n + 1}^{\infin} (n + 1)dx^i\\ \sum_{i = 0}^n (a + id)q^i &= (1 - x^{n + 1})(\frac a{1 - x} + \frac{dx}{(1 - x)^2}) - \frac{(n + 1)dx^{n + 1}}{1 - x}\\ \sum_{i = 0}^n (a + id)q^i &= \frac {(1 - x^{n + 1})a}{1 - x} + \frac{(1 - x^{n + 1})dx}{(1 - x)^2} - \frac{(n + 1)dx^{n + 1}}{1 - x}\\ \sum_{i = 0}^n (a + id)q^i &= \frac a{1 - x} + \frac{dx}{(1 - x)^2} - \frac{x^{n + 1}}{1 - x}(a + \frac{dx}{1 - x} + (n + 1)d)\\ \sum_{i = 0}^n (a + id)q^i &= \frac a{1 - x} + \frac{dx}{(1 - x)^2} - \frac{x^{n + 1}}{1 - x}(a + \frac{d}{1 - x} + nd)\\ \end{aligned}

因此, 我们得到了差比数列的前 $n$ 项和公式:

\sum_{i = 0}^n (a + id)q^i = \frac a{1 - q} + \frac{dq}{(1 - q)^2} - \frac{q^{n + 1}}{1 - q}(a + \frac{d}{1 - q} + nd)\\ \sum_{i = 1}^n (a + (i - 1)d)q^{i - 1} = \frac a{1 - q} + \frac{dq}{(1 - q)^2} - \frac{q^n}{1 - q}(a + \frac{d}{1 - q} + (n - 1)d)

如果进行二次或多次地错位相减, 将上面的操作进行多次, 还可以解决二阶甚至多阶差比数列的求和, 如求:

\sum_{i = 0}^{n} q^i \sum_{j = 0}^m a_ji^j

$\displaystyle{A_i = \sum_{j = 0}^m a_ji^j}$ 是一个 $m$ 阶差比数列则需要 $m$ 次错位相减可以求和.

斐波那契数列 $F_{i + 2} = F_i + F_{i + 1}$ , 是一个线性递推数列, 其中 $F_0 = 0$ , $F_1 = 1$ .

我们设它的 OGF 为 $F(x)$ , 由定义式可得:

\begin{aligned} F(x) &= x + xF(x) + x^2F(x)\\ (1 - x - x^2)F(x) &= x\\ F(x) &= \frac x{1 - x - x^2} \end{aligned}

解一元二次方程 $1 - x - x^2 = 0$ , 得 $x_1 = -\frac{1 + \sqrt 5}2$ , $x_2 = -\frac{1 - \sqrt 5}2$ , 因此:

\begin{aligned} &1 - x - x^2\\ =&-(x + \frac{1 + \sqrt 5}2)(x + \frac{1 - \sqrt 5}2)\\ =&(\frac{1 + \sqrt 5}2)(\frac{1 - \sqrt 5}2)(x + \frac{1 + \sqrt 5}2)(x + \frac{1 - \sqrt 5}2)\\ =&(\frac{1 - \sqrt 5}2x - 1)(\frac{1 + \sqrt 5}2x - 1) \end{aligned}

代回原式:

\begin{aligned} F(x) &= \frac x{(\frac{1 - \sqrt 5}2x - 1)(\frac{1 + \sqrt 5}2x - 1)}\\ F(x) &= \frac 1{\sqrt5} \left(\frac 1{\frac{1 - \sqrt 5}2x - 1} - \frac 1{\frac{1 + \sqrt 5}2x - 1}\right) \end{aligned}

GF 的线性运算
这里假设两个序列 $a$ , $b$ 的 OGF 分别为 $F(x)$ , $G(x)$ , 定义 $c_i = a_i + b_i$ , 那么显然 $c$ 的 OGF $H(x)$ 满足 $H(x) = F(x) + G(x)$ .
定义序列 $a$ , $b$ 的 OGF 分别为 $F(x)$ , $G(x)$ , 其中 $b_i = qa_i$ , 那么显然有满足 $G(x) = qF(x)$ .

引入了线性运算, 我们定义 $F_i = \frac 1{\sqrt 5} (f_i - g_i)$ , 其中 $f_i$ , $g_i$ 的生成函数分别为 $G_1(x)$ , $G_2(x)$ , 则有 $F(x) = \frac 1{\sqrt 5}(G_1(x) - G_2(x))$ .

刚好满足前面我们得到的形式:

\begin{aligned} F(x) &= \frac 1{\sqrt5} \left(\frac 1{\frac{1 - \sqrt 5}2x - 1} - \frac 1{\frac{1 + \sqrt 5}2x - 1}\right)\\ \frac 1{\sqrt 5} (G_1(x) - G_2(x)) &= \frac 1{\sqrt5} \left(\frac 1{\frac{1 - \sqrt 5}2x - 1} - \frac 1{\frac{1 + \sqrt 5}2x - 1}\right)\\ G_1(x) &= \frac 1{\frac{1 - \sqrt 5}2x - 1}\\ G_2(x) &= \frac 1{\frac{1 + \sqrt 5}2x - 1} \end{aligned}

接下来用 $G_1(x)$ 求出序列 $f$ :

\begin{aligned} G_1(x) &= \frac 1{\frac{1 - \sqrt 5}2x - 1}\\ \left(\frac{1 - \sqrt 5}2x - 1\right)G_1(x) &= 1\\ -f_0 + \sum_{i = 1}^{\infin} \left(\frac{1 - \sqrt 5}2f_{i - 1} - f_i\right)x^i &= 1\\ \end{aligned}

由每一项系数分别相等得:

\left\{ \begin{aligned} &f_0 = -1\\ &\frac{1 - \sqrt 5}2f_{i - 1} - f_i = 0 \end{aligned} \right.

解得:

f_i = -\left(\frac{1 - \sqrt 5}2\right)^i

同理可得:

g_i = -\left(\frac{1 + \sqrt 5}2\right)^i

因此:

\begin{aligned} F_i &= \frac 1{\sqrt 5} (f_i - g_i)\\ F_i &= \frac 1{\sqrt 5} \left(\left(\frac{1 + \sqrt 5}2\right)^i - \left(\frac{1 - \sqrt 5}2\right)^i\right) \end{aligned}

同样地, 对于其它线性递推数列, 也存在类似的方法, 常见的仍然是二阶齐次线性递推的数列. 请读者思考一般形式的二阶齐次线性递推数列 $a_{i + 2} = \lambda a_{i + 1} + \phi a_i$ 的通项公式.