求递推序列生成函数的显式公式及后续推导步骤咨询

我现在有这么一个递推关系：
$$a_0 = 3, a_n = 2a_{n-1} - 7 \quad (n \ge 1)$$

我尝试用生成函数的方法来解，已经做了以下步骤：

1. 定义生成函数：
   $$A(x) = \sum_{n=0}^\infty a_nx^n$$
2. 对递推式两边同时从$n=1$开始求和：
   $$\sum_{n=1}^\infty a_nx^n = 2\sum_{n=1}^\infty a_{n-1}x^n - 7\sum_{n=1}^\infty x^n$$
3. 左边可以转化为$A(x) - a_0$，不过我不确定右边接下来该怎么处理。另外我觉得$7\sum_{n=1}^\infty x^n = 7 \cdot (\frac{1}{1-x} - 1)$，这个是对的吗？

我的后续尝试（编辑内容） #

后来我又推了几步：
$$A(x) - 3 = 2xA(x) + 7 - \frac{7}{1-x}$$
$$A(x) - 10 + \frac{7}{1-x} = 2xA(x)$$
不过这一步我后来发现写错了，重新推导后得到：
$$(2x-1)A(x) = \frac{7}{1-x}-10$$
$$A(x) = \frac{10x-3}{(1-x)(2x-1)}$$
$$A(x) = \frac{10x-3}{1-x} \cdot \frac{1}{2x-1}$$

现在我需要求$a_n$的显式公式，是不是必须用部分分式分解？接下来具体该怎么做呢？

解答步骤 #

没错，部分分式分解是这一步的标准方法，咱们来一步步做：

首先先把$A(x)$的分母调整一下，让它更方便分解：
$$A(x) = \frac{10x - 3}{(1-x)(2x-1)} = \frac{10x - 3}{(1-x)(-(1-2x))} = \frac{3 - 10x}{(1-x)(1-2x)}$$

接下来设部分分式分解的形式：
$$\frac{3 - 10x}{(1-x)(1-2x)} = \frac{C}{1-x} + \frac{D}{1-2x}$$

两边同乘$(1-x)(1-2x)$消去分母：
$$3 - 10x = C(1-2x) + D(1-x)$$

现在我们可以用代入特殊值的方法求$C$和$D$：

1. 令$x=1$：左边$=3-10\times1=-7$，右边$=C(1-2\times1)+D(0)=-C$，所以$-C=-7 \implies C=7$
2. 令$x=\frac{1}{2}$：左边$=3-10\times\frac{1}{2}=3-5=-2$，右边$=C(0)+D(1-\frac{1}{2})=\frac{D}{2}$，所以$\frac{D}{2}=-2 \implies D=-4$

所以分解后得到：
$$A(x) = \frac{7}{1-x} - \frac{4}{1-2x}$$

现在我们可以利用已知的生成函数展开式：

• $\frac{1}{1-x} = \sum_{n=0}^\infty x^n$
• $\frac{1}{1-2x} = \sum_{n=0}^\infty (2x)^n = \sum_{n=0}^\infty 2^n x^n$

把这两个代入$A(x)$：
$$A(x) = 7\sum_{n=0}^\infty x^n - 4\sum_{n=0}^\infty 2^n x^n = \sum_{n=0}^\infty \left(7 - 4\times2^n\right)xn$$

而根据生成函数的定义，$A(x) = \sum_{n=0}^\infty a_n x^n$，所以对应系数相等，得到显式公式：
$$a_n = 7 - 4\times2^n = 7 - 2^{n+2}$$

我们可以验证一下这个公式是否符合初始条件和递推：

• 当$n=0$时，$a_0=7-2^{2}=7-4=3$，符合给定的初始值
• 假设$a_{n-1}=7-2^{{n+1}$，那么$2a_{n-1}-7=2(7-2}{n+1})-7=14-2^{n+2}-7=7-2{n+2}=a_n$，完全符合递推关系，说明结果是对的！

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