若${a_n}$为一个无限的整数数列，且其满足常系数齐次线性递推，本文试图证明$\lim\limits_{n\to \infty}\dfrac{a_{n+1}}{a_{n}}\ne \sqrt{2}$（若存在极限）。考虑到$2,1+\sqrt{2}$之类的数都可以取到，并且特征根为$\sqrt{2}$是可行的，这个结论并不显然。这里的$\sqrt{2}$可以换成$\sqrt{3}$等，不改变问题的本质。

一些浅显的观察

首先考虑BM算法在${a_n}$上的执行过程，显然此算法必定从某时刻起会不再更新递推式。所以此时的递推式就是${a_n}$满足的线性递推。这样我们就证明到了（最短）线性递推式的系数一定都是有理数。记此线性递推的阶数为$k$。

考虑什么情况下此极限才会等于$\sqrt{2}$。一个显然的必要条件是$\sqrt{2}$必为此线性递推的特征根之一。这也是我的切入口。

一个直观的想法是$\sqrt{2}$为有理系数多项式的根，所以$-\sqrt{2}$也必为一根。这其实很好证，记特征方程为$P(x)=0$，则显然$P(\sqrt{2})=A+B\sqrt{2},P(-\sqrt{2})=A-B\sqrt{2}\left(A,B\in\mathbb{Q}\right)$，而$A+B\sqrt{2}=0$，这意味着$A=B=0$，所以$P(-\sqrt{2})=0$。所以可知$x^2-2$为$P(x)$的一个因式。现在把$P(x)$做多项式除法，除掉$x^2-2$，剩下的仍然是一个有理多项式。反复使用前面的结论，可以进一步发现$\sqrt{2}$和$-\sqrt{2}$的重数一定是一样的。所以记$P(x)=(x^2-2)^{m}Q(x)$，使得$Q(\sqrt{2})\ne 0$。

证明

考虑对$P(x)$的这个因式分解在原序列上做的是什么事。举个例子：$P(x)=x^4+x^3-2x-4,Q(x)=x^2+x+2$

因式分解：

原序列上的整理：

两种操作显然是一模一样的，所以如果我们令$b_n=\sum\limits_{i=0}^{k-2}[x^i]Q(x)a_{n-k+2+i}$（比如说对于上面的例子，$b_n=a_n+a_{n-1}+2a_{n-2}$），下面的式子对任意有意义的$n$成立：

所以说现在${b_n}$也是一个线性递推。显然$b$需要分奇偶讨论，两者互不相干。如$n$为偶数时，记$c_n=b_{2n}$，就有$\sum\limits_{i=0}^{m}c_{n-i}[x^{m-i}](x-2)^{m}=0$ ，对应的特征方程即为$(x-2)^m=0$。根据大家所熟知的结论，$b_{2n}=c_n=2^{n}\sum\limits_{i=0}^{m}coef_{even,i}n^i$。奇数时同理，$b_{2n+1}=d_n=2^{n}\sum\limits_{i=0}^{m}coef_{odd,i}n^i$，这里的$coef$是有理数（有理性可以从初始条件中得出）。

下面考虑一下$\lim\limits_{n\to\infty}\dfrac{b_{2n+1}}{b_{2n}}$。$\dfrac{b_{2n+1}}{b_{2n}}=\dfrac{\sum\limits_{i=0}^{m}coef_{odd,i}n^i}{\sum\limits_{i=0}^{m}coef_{even,i}n^i}$，分类讨论一下：

• 如果奇偶两种系数的最高非零次项次数不同，那么极限不是$0$就是$\pm \infty$；
• 如果最高非零次项次数相同，假设此次数为$k$，自然也有$\lim\limits_{n\to\infty}\dfrac{b_{2n+1}}{b_{2n}}=\dfrac{coef_{odd,k}}{coef_{even,k}}\in \mathbb{Q}$

总之，这个极限不可能为$\sqrt{2}$。那么这是否会造成任何的矛盾呢？

导出矛盾

所以，我们想要证明$\lim\limits_{n\to \infty}\dfrac{b_{n+1}}{b_n}=\lim\limits_{n\to \infty}\dfrac{a_{n+1}}{a_{n}}=\sqrt{2}$，从而导出矛盾。但这不是显然的，虽然$b_{n+1}$和$b_n$都是一系列$a_n$的线性组合，并且每一对$a_n$都恰好差$\sqrt{2}$倍，貌似根据“糖水等式”，两边相等是很自然的？但是考虑下面的反例：

可惜我很笨，完全不会关于极限的任何处理办法，只会从定义开始暴力入手。下面我记$q=\sqrt{2}$。

显然${a_n}$从某一项开始不再变号。不妨设最后的符号是正的，显然就有$\lim\limits_{n\to \infty}a_n=\infty$。

考虑到极限是可以相乘的，容易归纳得出$\lim\limits_{n\to \infty}\dfrac{a_{n+k}}{a_n}=q^k$。根据极限的定义，$\forall \epsilon\gt0$，$\exists m$使得$\forall n\ge m,\vert\dfrac{a_{n+k}}{a_n}-q^k\vert\lt \epsilon$，即$\vert a_{n+k}-a_nq^k\vert\lt a_n\epsilon$。现在$b_n=\sum\limits_{i=0}^{t}c_ia_{n-i}$，$\forall x>0$，根据$c_i$我们当然可以恰当地分配各个$\epsilon$，从而决定出一个足够大的$m$使得$\forall n\ge m$，$\sum\limits_{i=0}^{t}c_ia_{n-i}\in\left[\sum\limits_{i=0}^{t}c_ia_{n-t}q^{t}-xa_{n-t},\sum\limits_{i=0}^{t}c_ia_{n-t}q^{t}+xa_{n-t}\right]$，说白了就是$\dfrac{b_n}{a_{n-t}}\in \left[Q(q)-x,Q(q)+x\right]$。

所以$\dfrac{b_{n+1}}{b_n}\in \dfrac{a_{n+1-t}}{a_{n-t}}\dfrac{Q(q)\pm x}{Q(q)\pm x}$。由于$Q(q)=Q(\sqrt{2})\ne 0$，且其为常数，显然我们可以使$x$变得任意小，令$\lim\limits_{x\to 0}\dfrac{Q(q)\pm x}{Q(q)\pm x}=1$。$n-t$也可以任意大，使得$\lim\limits_{n\to \infty}\dfrac{a_{n+1-t}}{a_{n-t}}=q$。这里其实说得不太严谨，但是想要严谨说明应该不难。所以说此时$\lim\limits_{n\to \infty}\dfrac{b_{n+1}}{b_n}=q\times 1=\sqrt{2}$，成功导出矛盾。

严谨说明

我向来是讨厌这些无趣的具体取值的，比如说高中数学导数大题的取点，我就从来都不取，毕竟没有意义：这样的值大家明明都知道是一定可以取出来的，但谁会真的无聊到去认真构造一个呢？况且这些取值导致证明失去了普适性：把极限从$\sqrt{2}$换成任何一个别的数都要从头开始重新试取值，严重地破坏了证明的美感和简洁。

取值1

令$\epsilon_i=\begin{cases}\dfrac{c_i^{-1}}{cnt}x,&c_i\ne 0\\19260817 ,&c_i=0\end{cases}$，$cnt$为非零的$c_i$个数。$m=\max\limits_{i=0}^{t}n_i(\epsilon_i)$，$n_i(\epsilon_i)$表示通过$\epsilon_i$决定出的$n_i$的下界。

取值2(仅对q=sqrt(2)成立)

不妨设$Q(q)\gt 0$，令$x=\min\left\{\dfrac{\epsilon Q(q)}{\epsilon+4},\dfrac{\epsilon Q(q)}{4-\epsilon}\right\}$，显然有$\left\vert \dfrac{Q(q)\pm x}{Q(q)\pm x}-1\right\vert \le \dfrac{\epsilon}{2}$，此时取$\epsilon_1=\min\left\{\dfrac{(2-\sqrt{2})\epsilon}{2+\epsilon},\dfrac{(2-\sqrt{2})\epsilon}{2-\epsilon}\right\}$，取一个足够大的$n-t$使得$\forall m\ge n-t,\left\vert \dfrac{a_{m+1}}{a_m}-\sqrt{2}\right\vert\le \epsilon_1$，令$n_0=\max \left\{n,n(x)\right\}$，$n(x)$指通过$x$决定出的$n$的下界。于是显然我们有$\forall n\ge n_0,\left\vert \dfrac{a_{n+1-t}}{a_{n-t}}\dfrac{Q(q)\pm x}{Q(q)\pm x}-\sqrt{2}\right\vert\le \epsilon$。

• Previous
  高三文化课学习周记 Part 4
• Next
  NMSL，汉语也死了