前缀和消元、耦合递推与双指标递推

当递推里同时出现多个序列时，可以选择整体组合，也可以消元。两种方法都要保留足够的初值与原关系。

消去前缀和

设 $S_n=\sum_{k=1}^n a_k$ ，且对所有 $n\ge1$ 有 $S_n=2a_n-1$ 。在 $n=1$ 处先得 $a_1=1$ 。对 $n\ge2$ ，将相邻两式相减，得到 $a_n=2a_n-2a_{n-1}$ ，故 $a_n=2a_{n-1}$ 。

于是 $a_n=2^{n-1}$ 。反代有限等比和得 $S_n=2^n-1=2a_n-1$ ，成立。相邻相减通常只在 $n\ge2$ 有效；初值须单独由原式取得。

两数列用和差解耦

设 $a_{n+1}=2a_n+b_n$ 、 $b_{n+1}=a_n+2b_n$ ， $a_1=1,b_1=0$ 。令 $u_n=a_n+b_n,v_n=a_n-b_n$ ，则 $u_{n+1}=3u_n$ 、 $v_{n+1}=v_n$ 。因此

a_n=\frac{3^{n-1}+1}{2},\qquad b_n=\frac{3^{n-1}-1}{2}.

还原公式来自 $a_n=(u_n+v_n)/2,b_n=(u_n-v_n)/2$ 。这里不需要矩阵理论。

一般二元线性耦合的消元

若 $a_{n+1}=pa_n+qb_n$ 、 $b_{n+1}=ra_n+sb_n$ ，则

a_{n+2}=(p+s)a_{n+1}+(qr-ps)a_n.

证明：展开下一步，得 $a_{n+2}=(p^2+qr)a_n+q(p+s)b_n$ ，再用 $qb_n=a_{n+1}-pa_n$ 代入。推导没有除以 $q$ ，故 $q=0$ 时等式仍成立。

若要从 $a_n$ 恢复 $b_n$ ， $q\ne0$ 时用 $b_n=(a_{n+1}-pa_n)/q$ ； $q=0$ 时必须回到第二条一阶递推另求。消元后的二阶方程要使用原式算出的 $a_2$ ，不能任意选两个初值。

双指标递推的边界与归纳顺序

设 $F(m,n)$ 为从 $(0,0)$ 走到 $(m,n)$ 、每步只向右或向上的路径数， $m,n$ 为非负整数。边界为 $F(0,n)=F(m,0)=1$ ，内部点按最后一步分类得

F(m,n)=F(m-1,n)+F(m,n-1)\quad(m,n\ge1).

按 $m+n$ 归纳，或选择全部 $m+n$ 步中哪 $m$ 步向右，均得 $F(m,n)=\binom{m+n}{m}$ 。例如 $F(2,3)=10$ 。

没有边界值，内部递推不能唯一确定数表；递推涉及两个指标时，须说明为什么所依赖的位置已经确定。

前缀和平方关系中的正项条件

设正项数列满足 $4S_n=(a_n+1)^2$ 。首项由 $4a_1=(a_1+1)^2$ 得 $a_1=1$ 。当 $n\ge2$ ，相邻两式相减，整理为

4a_n=(a_n-a_{n-1})(a_n+a_{n-1}+2),

(a_n+a_{n-1})(a_n-a_{n-1}-2)=0.

因为两项均为正，第一因子非零，所以 $a_n-a_{n-1}=2$ ，得到 $a_n=2n-1$ 。回代 $S_n=n^2$ ，原等式确实成立。

如果删掉正项条件，约去第一因子便不合法。例如 $a_n=(-1)^{n-1}$ 时，奇数下标的 $S_n=1$ 、偶数下标的 $S_n=0$ ，同样满足 $4S_n=(a_n+1)^2$ ，却不是上述等差数列。这个反例解释了正项条件实际排除了哪个分支。

关联阅读

一般二元线性耦合的消元

若

a_{n+1}=pa_n+qb_n

、

b_{n+1}=ra_n+sb_n

，则

a_{n+2}=(p+s)a_{n+1}+(qr-ps)a_n.

证明：展开下一步，得

a_{n+2}=(p^2+qr)a_n+q(p+s)b_n

，再用

qb_n=a_{n+1}-pa_n

代入。推导没有除以

q

，故

q=0

时等式仍成立。

若要从

a_n

恢复

b_n

，

q\ne0

时用

b_n=(a_{n+1}-pa_n)/q

；

q=0

时必须回到第二条一阶递推另求。消元后的二阶方程要使用原式算出的

a_2

，不能任意选两个初值。

双指标递推的边界与归纳顺序

设

F(m,n)

为从

(0,0)

走到

(m,n)

、每步只向右或向上的路径数，

m,n

为非负整数。边界为

F(0,n)=F(m,0)=1

，内部点按最后一步分类得

F(m,n)=F(m-1,n)+F(m,n-1)\quad(m,n\ge1).

按

m+n

归纳，或选择全部

m+n

步中哪

m

步向右，均得

F(m,n)=\binom{m+n}{m}

。例如

F(2,3)=10

。

没有边界值，内部递推不能唯一确定数表；递推涉及两个指标时，须说明为什么所依赖的位置已经确定。

前缀和平方关系中的正项条件

设正项数列满足

4S_n=(a_n+1)^2

。首项由

4a_1=(a_1+1)^2

得

a_1=1

。当

n\ge2

，相邻两式相减，整理为

4a_n=(a_n-a_{n-1})(a_n+a_{n-1}+2),

(a_n+a_{n-1})(a_n-a_{n-1}-2)=0.

因为两项均为正，第一因子非零，所以

a_n-a_{n-1}=2

，得到

a_n=2n-1

。回代

S_n=n^2

，原等式确实成立。

如果删掉正项条件，约去第一因子便不合法。例如

a_n=(-1)^{n-1}

时，奇数下标的

S_n=1

、偶数下标的

S_n=0

，同样满足

4S_n=(a_n+1)^2

，却不是上述等差数列。这个反例解释了正项条件实际排除了哪个分支。