0%

线性递推式的一个结论

本篇内容是我发现的一个线性递推式的一个结论:令\(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.