其实你没漏掉太复杂的东西，核心是这两个递推属于完全不同的类型——一个是齐次线性递推，另一个是非齐次线性递推，这直接决定了生成函数的求解模式差异。我给你拆解清楚：

1. 第一个例子：二阶常系数齐次线性递推 #

递推式：a_n = 3a_{n-1} + 2a_{n-2}, a_0 = 1, a_1 = 2
这类递推的核心特征是：递推式的右边只有序列自身前几项的线性组合，没有任何额外的、和序列无关的“干扰项”（比如指数函数、多项式等）。

用生成函数求解的典型步骤：

• 设生成函数 G(x) = \sum_{n=0}^\infty a_n x^n，展开后就是 G(x) = a_0 + a_1x + a_2x^2 + ... = 1 + 2x + \sum_{n=2}^\infty a_n x^n
• 把递推式 a_n = 3a_{n-1} + 2a_{n-2}（n≥2）代入求和项：
  \sum_{n=2}^\infty a_n x^n = 3\sum_{n=2}^\infty a_{n-1}x^n + 2\sum_{n=2}^\infty a_{n-2}x^n
• 对右边的求和式做移位变形（利用生成函数的移位性质：x^k \cdot G(x) 对应序列 a_{n-k} 的生成函数）：
  3x\sum_{n=2}^\infty a_{n-1}x^{n-1} + 2x^2\sum_{n=2}^\infty a_{n-2}x^{n-2} = 3x(G(x) - a_0) + 2x^2G(x)
• 把变形后的式子代回G(x)的表达式，整理求解：
  G(x) - 1 - 2x = 3x(G(x) - 1) + 2x^2G(x)
  最终得到 G(x) = \frac{1 - x}{1 - 3x - 2x^2}，后续可以通过部分分式拆分得到序列的通项公式。

2. 第二个例子：一阶常系数非齐次线性递推 #

递推式：a_n = 2a_{n-1} + 4^{n-1}, a_0 = 1
这类递推的关键区别是：递推式右边除了序列自身的项，还有一个独立的非齐次项（这里是指数函数 4^{n-1}），求解时需要单独处理这个非齐次项的生成函数。

用生成函数求解的典型步骤：

• 同样设生成函数 G(x) = \sum_{n=0}^\infty a_n x^n = 1 + \sum_{n=1}^\infty a_n x^n
• 代入递推式 a_n = 2a_{n-1} + 4^{n-1}（n≥1）：
  \sum_{n=1}^\infty a_n x^n = 2\sum_{n=1}^\infty a_{n-1}x^n + \sum_{n=1}^\infty 4^{n-1}x^n
• 分别处理右边的两个求和项：
  • 第一项移位变形：2x\sum_{n=1}^\infty a_{n-1}x^{n-1} = 2xG(x)
  • 第二项是等比数列求和：\sum_{n=1}^\infty 4^{n-1}x^n = x\sum_{n=1}^\infty (4x)^{n-1} = \frac{x}{1 - 4x}（前提是 |4x| < 1）
• 代回G(x)的表达式并整理：
  G(x) - 1 = 2xG(x) + \frac{x}{1 - 4x}
  最终得到 G(x) = \frac{1 - 3x}{(1 - 2x)(1 - 4x)}，同样可以拆分部分分式得到通项。

核心区分点总结 #

你之前没抓住的关键信息就是递推关系的齐次/非齐次属性：

• 齐次递推：只需要利用生成函数的移位性质，把所有项转化为G(x)的表达式即可求解
• 非齐次递推：除了移位性质，还需要单独计算非齐次项的生成函数（比如等比数列、多项式的生成函数公式），再合并求解G(x)

内容的提问来源于stack exchange，提问作者B.Li