递推不变量、线性化与有限项估计

有些递推式看起来是非线性的，却保存一个不随下标变化的量。寻找这个量，可能把问题转为已经掌握的线性递推；无法求通项时也可以估计有限项。

恒定的相邻二项式导出二阶线性递推

设数列各项非零，并且对所有 $n\ge1$ 有

a_{n+1}^2-a_na_{n+2}=C,

其中 $C$ 为常数。令 $K_n=(a_n+a_{n+2})/a_{n+1}$ ，则

K_n-K_{n+1}= \frac{a_na_{n+2}+a_{n+2}^2-a_{n+1}^2-a_{n+1}a_{n+3}}{a_{n+1}a_{n+2}}=0.

最后一步分别用 $a_na_{n+2}=a_{n+1}^2-C$ 和 $a_{n+1}a_{n+3}=a_{n+2}^2-C$ 。故 $K_n=K$ 为常数，从而

a_{n+2}=Ka_{n+1}-a_n.

这是二阶常系数线性递推。非零条件确保相除有意义；若出现零项，应直接从原式分类，不能跳过。

例：保留初值核验线性化

若 $a_1=1,a_2=3$ ，数列为正项，且 $a_{n+1}^2-a_na_{n+2}=2$ ，先得 $a_3=7$ ，所以 $K=(1+7)/3=8/3$ 。于是

a_{n+2}=\frac83a_{n+1}-a_n, \qquad a_4=\frac{47}{3}.

特征根为 $(4\pm\sqrt7)/3$ ，可继续利用二阶递推求通项。这里初值为整数不意味着后续都为整数；第四项已给出反例。

非线性递推中的裂项和

设 $a_1=2$ ， $a_{n+1}=a_n^2-a_n+1$ 。归纳得 $a_n\ge2$ ，且

a_{n+1}-1=a_n(a_n-1),\qquad \frac1{a_n}=\frac1{a_n-1}-\frac1{a_{n+1}-1}.

因此

\sum_{k=1}^n\frac1{a_k}=1-\frac1{a_{n+1}-1}<1.

这是一条对每个有限正整数 $n$ 都成立的恒等式，无需先求通项或研究无穷求和。寻找裂项时，可以先比较原递推中 $a_{n+1}$ 与常数的差。

平方后累加得到增长界

设 $a_1=1$ ， $a_{n+1}=a_n+1/a_n$ 。数列正且严格递增，而

a_{n+1}^2-a_n^2=2+\frac1{a_n^2}.

于是

a_n^2=1+2(n-1)+\sum_{k=1}^{n-1}\frac1{a_k^2}.

$n\ge3$ 时，和中的第一项为 $1$ 且其后仍有正项，故 $a_n^2>2n$ 。又 $a_k\ge1$ ，所以 $a_n^2\le3n-2<3n$ 。从而 $\sqrt{2n}<a_n<\sqrt{3n}$ 。

此处粗上界已经足够；若目标需要更精确的估计，再把已获得的下界代入倒数平方和。

有限状态重复与最终周期

设递推的完整状态属于有限集 $S$ ，下一状态由当前状态唯一决定。观察前 $|S|+1$ 个状态，必有两个相同；从此以后后继状态逐一相同，所以数列最终进入周期。

“有界”本身不保证有限状态，例如区间 $[0,1]$ 有无限多个实数。对有理数递推，需要额外证明分母受固定整数控制，才能由有界推出只有有限多个可能值。二阶递推通常需用相邻两项组成状态；只重复一项不能保证未来重复。

二阶线性递推的相邻行列式

设 $a_{n+2}=pa_{n+1}+qa_n$ ，令 $D_n=a_na_{n+2}-a_{n+1}^2$ 。由递推直接计算

D_{n+1}=a_{n+1}(pa_{n+2}+qa_{n+1})-a_{n+2}^2=-qD_n.

故 $D_n=(-q)^{n-1}D_1$ ；当 $q=0$ 时按递推解释，从 $D_2$ 起全为零。这一恒等式不需要各项非零，也不要求各项为整数。若称某量为“完全平方数”，则还必须另外证明有关项为整数。

再将原递推代入 $D_n$ ，有

D_n=pa_na_{n+1}+qa_n^2-a_{n+1}^2,

故可写成一阶的二次关系

a_{n+1}^2-pa_na_{n+1}-qa_n^2+D_n=0,

a_{n+1}=\frac{pa_n\pm\sqrt{(p^2+4q)a_n^2-4D_n}}2.

根号中的量对原实数数列当然非负，但单独选取一个符号分支未必恢复原递推。另有

a_na_{n+2}-D_n=a_{n+1}^2.

右侧是实数平方；只有 $a_{n+1}$ 为整数时，才可称为整数意义的完全平方数。

当 $q=-1$ 时， $D_n=D$ 恒定，并且

(p+2)a_na_{n+1}-D=(a_n+a_{n+1})^2.

证明是把 $D=pa_na_{n+1}-a_n^2-a_{n+1}^2$ 代入左边。将 $a_{n+2}=pa_{n+1}-a_n$ 代入，得到

a_{n+1}^2-pa_na_{n+1}+a_n^2+D=0,

因而

a_{n+1}=\frac{pa_n\pm\sqrt{(p^2-4)a_n^2-4D}}2.

每一步的符号由原数列决定，不能一律选正号。例如 $p=0,a_1=a_2=1$ 时，数列为 $1,1,-1,-1,1,1,\ldots$ ，正根公式无法复现全部项。此处也校正原讲义根号内常数项的符号。

关联阅读