求解给定非齐次线性递推关系的显式公式

我完全懂你现在的感受——刚学完齐次线性递推就碰到非齐次的，确实有点懵。别慌，我们一步步拆解这个问题，把它转化成你熟悉的思路来解决。

首先先把给定的递推式整理得更清晰些：

初始条件：$a_0 = 1$
递推关系：$a_n = 2^{2(5-n)+1} \cdot a_{n-1} + 1$

先简化指数部分：$2^{2(5-n)+1} = 2^{11-2n}$，所以递推式可以写成更直观的形式：
a_n = 2^(11-2n) * a_{n-1} + 1

这类形如 $a_n = f(n)a_{n-1} + g(n)$ 的非齐次线性递推，可以用「累加因子法」来解——这其实是微分方程里积分因子的离散版本，思路是把递推式转化为可累加的形式，具体步骤如下：

步骤1：先求对应的齐次递推通解 #

齐次部分是去掉非齐次项（也就是这里的+1）后的式子：$a_n^{(h)} = 2^{11-2n} \cdot a_{n-1}^{(h)}$

齐次递推的通解是累乘系数得到的：
$a_n^{(h)} = C \cdot \prod_{k=1}^n 2^{11-2k}$，其中$C$是任意常数。

我们来计算这个乘积：根据指数运算法则，乘积的指数等于各指数的和，所以先算指数的总和：
$$
\sum_{k=1}^n (11-2k) = 11n - 2\sum_{k=1}^n k = 11n - 2 \cdot \frac{n(n+1)}{2} = 10n - n^2
$$
因此乘积结果是 $2^{10n - n^2}$，齐次通解就变成：
$a_n^{(h)} = C \cdot 2^{10n - n^2}$

步骤2：构造非齐次的一个特解 #

对于这种递推形式，特解可以用累加因子构造，公式是：
$$
a_n^{(p)} = \left( a_0 + \sum_{k=1}^n \frac{g(k)}{\prod_{i=1}^k f(i)} \right) \cdot \prod_{i=1}^n f(i)
$$
这里我们的$g(k)=1$，$\prod_{i=1}^k f(i)=2^{10k -k^{2}$（就是把步骤1里的n换成k），所以$\frac{1}{\prod_{i=1}}k f(i)} = 2^{k2 -10k}$

代入初始条件$a_0=1$，特解就变成：
$$
a_n^{(p)} = 2^{10n -n^2} \cdot \left( 1 + \sum_{k=1}^n 2^{k2 -10k} \right)
$$

步骤3：结合初始条件得到最终通解 #

非齐次递推的通解是齐次通解加特解：$a_n = a_n^{(h)} + a_n^{(p)}$，但我们代入初始条件$a_0=1$验证会发现，当n=0时，齐次项的常数$C$必须为0才能满足初始条件，所以最终的显式公式就是：
$$
a_n = 2^{10n -n^2} \cdot \left( 1 + \sum_{k=1}^n 2^{k2 -10k} \right)
$$

验证一下正确性（拿小n值测试） #

• 当n=1时：
  递推式计算：$a_1=2^{11-21}1 +1=512+1=513$
  显式公式计算：$2^{101 -1}(1+2^{1-10})=512*(1+1/512)=513$，结果一致。
• 当n=2时：
  递推式计算：$a_2=2^{11-4}513 +1=128513+1=65665$
  显式公式计算：$2^{20-4}*(1+2{1-10}+2^{4-20})=65536*(1+1/512+1/65536)=65665$，结果也一致。

这样你就能确认这个解法是对的啦，本质上就是把非齐次的递推转化为累加运算，而累加因子帮我们完成了这个转化~

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