【A-LEVEL高数大学先修】差分求和与生成函数法

一、引言：从差分法到生成函数

在A Level进阶数学中，我们学习了两种重要的数列求和方法：

• 差分法（Method of Differences）：通过裂项相消，将求和转化为首尾项相减。

• 标准求和公式：如 ∑(r=1 to n) r² = n(n+1)(2n+1)/6。

这些方法虽然巧妙，但各有局限：

• 差分法需要裂项，技巧性强，有时不易观察。

• 标准公式只适用于特定幂次。

大学数学中，生成函数（Generating Function）提供了一种更系统、更强大的求和方法。它不仅能够求和，还能揭示数列的深层结构，是组合数学、数论和概率论中的核心工具。

二、生成函数的基本思想

1. 定义

给定一个数列 {a_n} (n从0到∞)，其普通生成函数（Ordinary Generating Function, OGF）定义为形式幂级数：

G(x) = ∑(n=0 to ∞) a_n x^n = a_0 + a_1 x + a_2 x² + a_3 x³ + ...

这里 x 是形式变量，我们暂时不关心收敛性，只关注系数之间的代数关系。

2. 直观理解

生成函数将数列编码为幂级数的系数。对生成函数进行代数运算（加、减、乘、求导、积分等），相当于对原数列进行某种组合操作。

三、经典数列的生成函数

例1：常数数列 a_n = 1

G(x) = ∑(n=0 to ∞) 1·x^n = 1 + x + x² + x³ + ... = 1/(1-x) (|x| < 1)

这是几何级数公式。

例2：等差数列 a_n = n

G(x) = ∑(n=0 to ∞) n x^n = 0 + 1x + 2x² + 3x³ + ...

注意到 d/dx (1/(1-x)) = 1/(1-x)² = ∑(n=1 to ∞) n x^(n-1)，所以：

∑(n=0 to ∞) n x^n = x · 1/(1-x)² = x/(1-x)²

例3：平方数列 a_n = n²

利用导数技巧：

∑(n=0 to ∞) n² x^n = x d/dx (x/(1-x)²) = x(1+x)/(1-x)³

四、用生成函数求 ∑(r=1 to n) r²

我们已知：

∑(r=0 to ∞) r² x^r = x(1+x)/(1-x)³

但我们需要的是有限和 ∑(r=1 to n) r²。

技巧：考虑部分和生成函数。设 S_n = ∑(r=1 to n) r²，则 {S_n} 也是一个数列。它的生成函数 H(x) = ∑(n=0 to ∞) S_n x^n 与平方数列生成函数有何关系？

注意到：

S_n - S_{n-1} = n² (n ≥ 1, S_0 = 0)

在生成函数层面，这对应：

H(x) - x H(x) = ∑(n=1 to ∞) n² x^n = x(1+x)/(1-x)³ - 0

因为 n=0 时 0²=0。所以：

(1-x) H(x) = x(1+x)/(1-x)³

H(x) = x(1+x)/(1-x)⁴

现在，我们需要从 H(x) 中提取 S_n 的表达式。将 1/(1-x)⁴ 展开为二项级数：

1/(1-x)⁴ = ∑(k=0 to ∞) C(k+3, 3) x^k (负二项式定理)

所以：

H(x) = x(1+x) ∑(k=0 to ∞) C(k+3, 3) x^k = ∑(k=0 to ∞) C(k+3, 3) x^{k+1} + ∑(k=0 to ∞) C(k+3, 3) x^{k+2}

令第一项中 n = k+1，第二项中 n = k+2：

H(x) = ∑(n=1 to ∞) C(n+2, 3) x^n + ∑(n=2 to ∞) C(n+1, 3) x^n

合并 x^n 的系数（注意 n=1 时第二项为0）：

S_n = C(n+2, 3) + C(n+1, 3) (n ≥ 1)

计算组合数：

C(n+2, 3) = (n+2)(n+1)n/6, C(n+1, 3) = (n+1)n(n-1)/6

相加：

S_n = [(n+2)(n+1)n + (n+1)n(n-1)]/6 = n(n+1)[(n+2)+(n-1)]/6 = n(n+1)(2n+1)/6

这正是A Level公式。