( ext{1.0 Prework})
((1-x) ^ {-k} = sum_{n geq 0} inom{n + k - 1}{k - 1} x^n).
更常用的应用大概是(k = 1)或(k = 2).
( ext{1.1 An easy two term recurrence})
对于这个式子，不难列出序列(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):)
(egin{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})
至此，我们通过了母函数来导出了该数列的通项公式。
( ext{1.2 An slightly harder two term recurrence})
现在打表就没法一眼看出规律了。。。
考虑母函数：
(sum_{ngeq 0} a_{n+1} x^n = (A(x) - a_0) / x = (A(x) - 1) / x)
(sum_{ngeq 0} (2a_n + n) x^n = 2A(x) + frac{x}{(1 - x)^2})
（注意后面那一坨是前置知识）
联立得
((A(x) - 1) / x = frac{x}{(1 - x)^2})，求得(A(x) = frac{1 - 2x + 2x^2}{(1 - x)^2 (1 - 2x)})
接下来考虑待定系数分解(A(x))，解得(A(x) = frac{-1}{(1 - x)^2} +frac{2}{1 - 2x})
故
(egin{aligned} A(x) &= (-1)(x^0 + 1x^1 + 2x^2 + 3x^3) + 2 * (1 + 2x + 4x^2 + 8x^3)... \ &= -1x^0 -1x^1 -2x^2 -3x^3... + 2x^0 + 4x^1 + 8x^2 + 16x^3 ...\ &= sum_{n geq 0} (2^{n + 1} - n - 1) x^n end{aligned})
那么得通项公式(a_n = 2^{n+1} - n - 1)。