物理

[论坛资料室]《数列世界》附录

[附录1]关于不动点方法的一些解释

求数列通项的时候，我们常常会看到所谓的“不动点方法”（如例9、10、12）。有的老师喜欢把这一种方法作为结论直接推给学生，这样就导致很多人（包括我）第一次看到时并不清楚其中原理，更不要说熟练运用于做题。这里，我们就来详细谈一下不动点方法的原理。

首先，我们给出不动点的定义：

在一个只与${a_n}$有关的递推公式中，若存在${x \in \mathbb{C}，使a_n=x时，a_{n+1}=a_n}$，则称${x}$为{${a_n}$}的不动点。

在求解数列通项中，“不动点方法”一般是把两边同时减去不动点，进而寻求规律。

我们可以考虑令${a_n=x}$，则等式左、右同时为0。一般的分式递推中，右侧必然能拆出一项${a_n-x}$，而左侧为${a_{n+1}-x}$，

一般就是这一点经常被用于构造等比或等差数列。

例如，在例8中，由于有两个不动点，减去不动点后再相除，就可以消去分母上的部分，从而构造出等比数列。

而在例9中，由于只有一个不动点，式中各数必须满足一定的关系，在这样的关系下，取倒数后恰好可以构成等差数列。

例12与例8类似。从这里可以看出，以上所举三题的做法并非空穴来风，而是“向熟悉的数列（等差或等比）转化”思想的具体体现。

实际上，本身不属于不动点方法，但是却运用到这一转化思想的例子十分广泛，在附录2中将可以看到。

[附录2]特征方程的严谨证明（纯初等）

提到特征方程，大多数同学应该是不会在乎它的证明的。部分竞赛学得较为深入的同学可能会听过“母函数”，但这一证法用到了某些高等数学以及线性代数的内容，远超正常理解。所以，在我班数学老师的启发以及$\sout{四场会考}$的努力下，我完成了特征方程的数学语言表述与初等证明，具体内容见下：

已知：数列{${a_n}$}满足${a_{n+k}=\sum_{i=0}^{k-1}A_ia_{n+i}，其中A_0 \ne 0}$，记${P(x)=x^n-\sum_{i=0}^{n-1}A_ix^i=\prod_{i=1}^s(x-x_i)^{α_i}，\sum_{i=1}^sα_i=k}$，

则${ \exists P_i \in \mathbb{C}[n]，degP_i}$≤${α_i-1，a_n=\sum_{i=1}^sx_i^nP_i(n)}$

（这里规定零多项式的次数为-1）

证明：当${k=1时，该数列为等比数列，显然成立}$

假设k-1时（k≥2）成立，下证k成立：

对0≤s≤k-2，我们用如下方式定义${B_s}$：

${令B_{k-1}=A_{k-1}-x_1，B_s=A_s+x_1B_{s+1}}$

易知${B_0=-P(x_1)=0}$

则${a_{n+k}-x_1a_{n+k-1}=\sum_{i=1}^{k-1}B_i(a_{n+i}-x_1a_{n+i-1})+B_0=\sum_{i=1}^{k-1}B_i(a_{n+i}-x_1a_{n+i-1})}$

而${(x-x_1)(x^{k-1}-\sum_{i=0}^{k-2}B_{i+1}x^i)=P(x)=\prod_{i=1}^s(x-x_i)^{α_i}}$

①若s≥2：

则${x^{k-1}-\sum_{i=0}^{k-2}B_{i+1}x^i=(x-x_1)^{(α_1-1)}\prod_{i=2}^s(x-x_i)^{α_i}}$，

由归纳假设，${ \exists Q_i \in \mathbb{C}[n]，degQ_i}$≤${α_i-1，a_{n+1}-x_1a_n=\sum_{i=1}^sx_i^nQ_i(n)}$，

同理${ \exists R_i \in \mathbb{C}[n]，degR_i}$≤${α_i-1，a_{n+1}-x_2a_n=\sum_{i=1}^sx_i^nR_i(n)}$

联立以上两式，由${x_1 \ne x_2}$，即证。

②若s=1：

则由归纳假设，${a_{n+1}-x_1a_n=x_1^nQ_1(n)}$，

其中${degQ_1}$≤k-2

由${x_1 \ne 0}$，故${\frac{a_{n+1}}{x_1^{n+1}}-\frac{a_n}{x_1^n}=\frac{Q_1(n)}{x_1}}$，

熟知${deg(\sum_{i=1}^{n-1}Q_1(n))}$≤${degQ_1+1}$，

从而由等差数列性质，原命题也得证。

综上，我们完成了从k-1到k的归纳，即原命题对任意正整数k成立。证毕。