\(\text{1.0 Prework}\)
\((1-x) ^ {-k} = \sum_{n \geq 0} \binom{n + k - 1}{k - 1} x^n\).
更常用的应用大概是\(k = 1\)或\(k = 2\).
\(\text{1.1 An easy two term sequence}\)
\[a_{n+1} = 2a_{n} + 1\ \ \ (n \geq 0; a_0 = 0)\]
对于这个式子，不难列出序列\(0, 1, 3, 7, 15, 31...\)进而找到通项公式\(a_n = 2^n - 1\).
但是接下来，我们将尝试着以母函数的思想来推导该通项公式。
由于递推式仅跟上一项有关，故尝试将\({a_n}\)的母函数\(A(x)\)移动一位：
\(G(x) = \sum_{n \geq 0} a_{n+1} x^n = a_1x^0 +a_2x^1 + a_3x^2... = (A(x) - a_0) / x\)
考虑换一个角度算\(G(x)\):
\(G(x) = \sum_{n \geq 0} (2a_n + 1) x^n = 2A(x) + \frac{1}{1-x}\)，后面的分数是等比数列求和公式。
那么通过两个方程联立可得\(A(x) = \frac{x}{(1 - x)(1 - 2x)}\)。
考虑拆掉\(A(x):\)
\(\begin{aligned} A(x) &= x(\frac{2}{1 - 2x} - \frac{1}{1-x}) \\ &= x(2(1 + 2x + 4x^2 + 8x^3...) - (1 + x + x^2 + x^3...)) \\ &= x(2 + 4x + 8x^2 + 16x^3...) - x(1 + x + x^2 + x^3...) \\ &= 2x + 4x^2 + 8x^3 + 16x^4... - x - x^2 - x^3 - ...\\ &= \sum_{n \geq 0} (2^n - 1) x^n \\ \end{aligned}\)
至此，我们通过了母函数来导出了该数列的通项公式。
原文：https://www.cnblogs.com/LiM-817/p/12005361.html