给定非齐次线性递推关系：
$$c_{n} - 4c_{n-1} + 4c_{n-2} = 3$$
初始条件为 $c_{0} = c_{1} = 11$，需要推导生成函数 $C(x) = \sum_{n=0}^{\infty} c_{n}x^{n}$，同时用齐次化的方法求解该递推关系。

嗨，我来帮你一步步搞定这两种解法，先从生成函数法说起，再看齐次化的思路~

一、生成函数法求解 #

你提到的思路完全正确，我帮你把推导过程理得更清晰，顺便修正一下你写的式子中的小笔误：

• 首先对递推式两边乘以$x^n$，然后对$n\geq2$求和：
  $$\sum_{n=2}^{\infty}(c_n -4c_{n-1}+4c_{n-2})x^n = \sum_{n=2}^{\infty}3xn$$

• 拆分左侧求和项，同时计算右侧的等比数列和：
  左侧拆成三个独立求和式，右侧利用等比数列求和公式$\sum_{n=k}^{\infty}xn=\frac{x^k}{1-x}$（$|x|<1$），得到：
  $$\sum_{n=2}^{\infty}c_nxn -4\sum_{n=2}^{{\infty}c_{n-1}x}n +4\sum_{n=2}^{{\infty}c_{n-2}x}n = \frac{3x^2}{1-x}$$

• 用生成函数$C(x)$替换左侧的求和式：
  我们知道$C(x)=\sum_{n=0}^{\infty}c_nxn$，所以可以把每个求和式转化为$C(x)$的形式：

  • $\sum_{n=2}^{\infty}c_nxn = C(x) - c_0 - c_1x = C(x) -11 -11x$
  • $\sum_{n=2}^{{\infty}c_{n-1}x}n = x\sum_{k=1}^{\infty}c_kxk = x(C(x)-c_0)=x(C(x)-11)$
  • $\sum_{n=2}^{{\infty}c_{n-2}x}n = x^2\sum_{k=0}{\infty}c_kx^k=x2C(x)$

• 代入后整理方程：
  把上面的结果代入左侧，展开并合并同类项：
  $$(C(x)-11-11x) -4x(C(x)-11) +4x^2C(x) = \frac{3x^2}{1-x}$$
  化简后得到：
  $$C(x)(1-2x)^2 + (-11 + 33x) = \frac{3x^2}{1-x}$$

• 求解$C(x)$并拆成分部分式：
  把常数项移到右侧并通分计算，最终得到：
  $$C(x)=\frac{36x^{2-44x+11}{(1-x)(1-2x)}2}$$
  接下来将其拆成分部分式：
  $$C(x)=\frac{3}{1-x}+\frac{12}{1-2x}-\frac{4}{(1-2x)^2}$$

• 展开为幂级数得到通项：
  利用常见的幂级数展开公式：

  • $\frac{1}{1-x}=\sum_{n=0}^{\infty}xn$
  • $\frac{1}{1-2x}=\sum_{n=0}^{\infty}2nx^n$
  • $\frac{1}{(1-2x)^{2}=\sum_{n=0}}{\infty}(n+1)2^nxn$
    合并后得到通项公式：
    $$c_n=3 + (8-4n)2^n$$
    验证一下初始条件：$c_0=3+8=11$，$c_1=3+(8-4)*2=11$，完全符合。

二、齐次化方法求解 #

对于非齐次项是常数的递推，我们可以通过构造齐次递推来消去常数项，步骤如下：

• 写出原递推式和n-1时的递推式：
  原递推（n≥2）：$c_n -4c_{n-1}+4c_{n-2}=3$
  n-1时的递推（n≥3）：$c_{n-1}-4c_{n-2}+4c_{n-3}=3$

• 两式相减消去常数项，得到齐次递推：
  $$c_n -5c_{n-1}+8c_{n-2}-4c_{n-3}=0$$

• 求解特征方程：
  特征方程为$r^3-5r2+8r-4=0$，因式分解后得到$(r-1)(r-2)^2=0$，特征根为$r=1$（单根），$r=2$（二重根）。

• 写出齐次递推的通解：
  通解形式为：
  $$c_n=A + (B+Cn)2^n$$

• 利用初始条件求系数：
  先通过原递推式算出$c_2=4c_1-4c_0+3=3$，然后代入$c_0=11$、$c_1=11$、$c_2=3$，解方程组得到$A=3$，$B=8$，$C=-4$，最终通解为：
  $$c_n=3 + (8-4n)2^n$$
  和生成函数法的结果完全一致。

备注：内容来源于stack exchange，提问作者JLGL