线性递推式的一个结论

本篇内容是我发现的一个线性递推式的一个结论：令\(x_n=(a_{n+k-1},a_{n+k-2},\dots.,a_{n})^T\)对线性递推式\(a_{n}=c_1a_{n-1}+c_2a_{n-2}+\dots+c_ka_{n-k}\)，一定存在一个非奇异对称矩阵\(B\)，使得\(x_p^TBx_q=x_r^TBx_s\)，若\(p+q=r+s\)。特殊地，存在一个非奇异对称矩阵\(C\)，使得\(x_{n+m}=x_n^TCx_m\)。

这个结论是我在看见Fibonacci数列有恒等式\(F_{n+m}=F_nF_m+F_{n-1}F_m+F_nF_{m-1}\)时，尝试推到一般的线性递推式时发现的。一开始我尝试了好几个二阶线性递推数列，发现了矩阵都是一个对称矩阵，然后用初等方法证明了二阶的情况。第二天重新尝试了一下，发现能用代数方法很快推广到高阶情形，且能得到更一般的形式和快速求初这个矩阵的方法。下面给出初等方法求二阶形式和代数方法求高阶形式。

二阶形式

对二阶线性递推式\(F_n=pF_{n-1}+qF_{n-2}(F_1,F_2,p,q\neq0)\)，考虑方程 \[ F_{n+m}=(F_m,F_{m-1})\begin{pmatrix} a&b\\ b&c\\ \end{pmatrix}\begin{pmatrix}F_n\\ F_{n-1}\\ \end{pmatrix},\tag{1}\label{1} \] 即\(F_{n+m}=aF_nF_m+bF_{n-1}F_m+bF_nF_{m-1}+cF_{n-1}F_{m-1}\)，对\(F_{n+m-1}\)和\(F_{n+m-2}\)，有 \[ \begin{align*} F_{n+m-1}&=aF_nF_{m-1}+bF_{n-1}F_{m-1}+bF_nF_{m-2}+cF_{n-1}F_{m-2}\\ F_{n+m-2}&=aF_{n-1}F_{m-1}+bF_{n-2}F_{m-1}+bF_{n-1}F_{m-2}+cF_{n-2}F_{m-2}, \end{align*} \] 将两式代入\(\eqref{1}\)，对\(pF_{n+m-1}+qF_{n+m-2}\)，有 \[ \begin{align*} pF_{n+m-1}+qF_{n+m-2}&=paF_nF_{m-1}+(pb+qa)F_{n-1}F_{m-1}+pbF_nF_{m-2}\\ &~~~~+(pc+qb)F_{n-1}F_{m-2}+qbF_{n-2}F_{m-1}+qcF_{n-2}F_{m-2}\\ &=(p^2a+pb+qa)F_{n-1}F_{m-1}+(pqa+qb)F_{n-2}F_{m-1}\\ &~~~~+(p^2b+pc+qb)F_{n-1}F_{m-2}+(pqb+qc)F_{n-2}F_{m-2}. \end{align*} \] 比较 \[ F_{n+m}=(ap^2+2bp+c)F_{n-1}F_{m-1}+(apq+bq)F_{n-1}F_{m-2}+(apq+bq)F_{n-2}F_{m-1}+apqF_{n-2}F_{m-2}, \] 可以得到\(qa=pb+c\)，再取\(n+m=4,5\)，可列方程 \[ \begin{cases} qa-pb-c=0\\ F_2^2a+2F_1F_2b+F_1^2c=F_4\\ F_2F_3a+(F_1F_3+F_2^2)b+F_1F_2c=F_5 \end{cases}\tag{2}\label2 \] 令\(A\)为系数矩阵，计算行列式得 \[ \begin{align*} |A|&=qF_1^2F_2^2-pF_1^2F_2F_3+F_1F_2^2F_3-F_2^4-qF_1^3F_3+pF_1F_2^3\\ &=F_1F_2^2(pF_2+qF_1)-F_1^2F_3(pF_2+qF_1)+F_1F_2^2F_3-F_2^4\\ &=-(F_2^2-F_1F_3)^2 \end{align*} \] 从而\(|A|=0\)当且仅当\(F_2^2=F_1F_3\)。\(|A|\neq0\)时显然方程有唯一解，而\(|A|=0\)时由于\(p,q\neq0\)（这是二阶线性递推式的前提），消元可以得到系数矩阵和增广矩阵的秩都为\(2\)，因此方程有无穷多组解。另外，\(F_2^2=F_1F_3\)时，\(\{F_n\}\)同时还是等比数列。

再考虑Fibonacci数列的那个恒等式，我们来考虑是否一定有\(c=0\)的解。

令\(c=0\)，解得当且仅当\(F_2=pF_1\)时， \[ a=\frac{p^2}{F_2},b=\frac{pq}{F_2} \] 是一组解，注意到分母恒非零，因此一定有一组\(c=0\)的解。

很容易证明，当\(F_{n+m-1}\)和\(F_{n+m-2}\)满足式\(\eqref1\)时，\(F_{n+m}\)也满足\(\eqref{1}\)，因此由数学归纳法，只要解出\(\eqref2\)，式\(\eqref1\)就对成立。

高阶形式

Lemma([1]) 域\(K\)上，一定存在一个非奇异对称矩阵\(B\)是矩阵\(A\)相似于\(A^T\)的变换矩阵，即\(B^{-1}AB=A^T\)。当且仅当\(A\)的特征多项式等于最小多项式，即\(A\)相似于\(A\)的伴随矩阵时，所有\(A\)到\(A^T\)的相似变换矩阵都是对称的。

取

\[ A=\begin{pmatrix} a_{1}&a_2&\cdots&a_k\\ 1&&&\\ &\ddots\\ &&1 \end{pmatrix}, \] 设\(C\)是\(A\)到\(A^T\)的一个相似变换矩阵，即\(C^{-1}AC=A^T\)，有\(CA=A^TC\)。

对线性递推方程，有\(x_p=A^{p-r}x_r\)，两边同左乘\(C\)，得到\(Cx_p=CA^{p-r}x_r\)，再同左乘\(x_q^T\)，有 \[ \begin{align*} x_q^TCx_p&=x_q^TCA^{p-r}x_r\\ &=x_q^T(A^{p-r})^TCx_r\\ &=(A^{p-r}x_q)^TCx_r\\ &=x_s^TCx_r, \end{align*} \] 其中\(p+q=r+s\)。

[1] O. Taussky, H. Zassenhaus, On the similarity transformation between a matrix and its transpose, Pacific J. Math. 9 (1959) 893–896.