特征根方程-求解递推数列通项的工具

Kevin327 · 2019-02-24 21:52:43 · 题解

特征方程，实际上就是为研究相应的数学对象而引入的一些等式，它因数学对象不同而不同，包括数列特征方程，矩阵特征方程，微分方程特征方程，积分方程特征方程等等。

特征根方程是数学竞赛中常用的一种解题技巧，可以处理形如

A(x+2)=pA(x+1)+qA(x)

这样的数列通项。

一个这样的递推数列的特征根方程就是x^2=px+q

有没有很熟悉的感觉？

我们令p=1,q=1，得出A(x+2)=A(x+1)+A(x)

正是我们最熟悉的fibnacci数列！是不是很令人激动呢？

先放结论

我们定义特征根方程的根为特征根。

特征根与数列通项的关系

① 有两个不等特征根，设为x_1,x_2

a_n=Mx_1^n+Nx_2^n

② 有两个相等特征根，设为x

a_n=(Px+Q)x^n

## 如何证明？一般使用数学归纳法证明，但是较为繁琐。这里提供一种比较简洁的证明方法，根据为恒等变换。我们令$s,r$满足 $a(n+2)-r*a(n+1)=s[a(n+1)-r*a(n)]

那么

a(n+2)=(s+r)*a(n+1)-sr*a(n)

根据韦达定理，原特征根方程的两根x_1,x_2满足x1+x2=p,x1x2=-q

那么这里的s,r又是什么呢？把s,r的定义式和原式对比一下，发现s+r=p,sr=q....

根据韦达定理的逆定理，这里的s,r就是刚才的特征根。

我们同样分刚才的两种情况考虑。

①s=r

根据一元二次方程的求根公式，△=p^2+4q=0

解得p^2=-4q。

我们设p=2t,那么q=t^2

我们代入原来的递推式中。那么A(n+2)-2t·A(n+1)+t^2·A(n)=0

A(n+2)-t·A(n+1)=t·A(n+1)-t^2·A(n)

A(n+2)-t·A(n+1)=t·[A(n+1)-t·A(n)]

看出什么了吗？

令数列F(n)=A(n+1)-t·A(n),那么F(n)为一个等比数列，首项为A(2)-A(1),公比为t。

那么

A(n+1)-t·A(n)$=$[A(2)-rA(1)]*t^(n-1)

A(n+1)/t^(n+1)-A(n)/t^n=[A(2)/r^2-A(1)/r]

等式右边为常数，并且我们观察到等式左边两项结构相同，均为A(n)/t^n，那么数列F_2(n)=A(n)/t^n为等差数列。

根据等差数列性质：

a(n)/t^n=a(1)/t+(n-1)*[a(2)/t^2-a(1)/t]

a(n)=a(1)t*t^n+(n-1)*[a(2)/t^2-a(1)/t]*t^n

$p=2t$,$q=t^2

因为两根相等，根据韦达定理，x_1+x_2=2x=-p

x_1x_2=x^2=q

那么，2x=-2t，t就是-x。

我们设

再设 $2A(1)/r-A(2)/r^2=P

代回原式，a_n=(Px+Q)x^n

② s≠r

其实和刚才类似。

根据韦达定理，我们可以求得

a(n+2)-r*a(n+1)=s[a(n+1)-r*a(n)]

a(n+2)-s*a(n+1)=r[a(n+1)-s*a(n)]

根据等比数列公式，

a(n+1)-r*a(n)=[a(2)-r*a(1)]s^(n-1)

a(n+1)-s*a(n)=[a(2)-s*a(1)]r^(n-1)

相减得a(n)=([a(2)-r*a(1)]/[s(s-r)])*s^n-([a(2)-s*a(1)]/[r(s-r)])*r^n

换元即得

a_n=Mx_1^n+Nx_2^n

证毕！

例题

求fibonacci数列的通项公式

特征方程为：

X^2=X+1

解得

X_1=\frac{1+\sqrt5}{2}

X_2=\frac{1-\sqrt5}{2}

则F(n)=M*X_1^n+N*X_2^n

∵F(1)=F(2)=1

代入这两个值

解得

M=\frac{\sqrt{5}+5}{10}

N=\frac{5-\sqrt{5}}{10}

∴F(n)=\frac{\sqrt{5}+5}{10}*{(\frac{1+\sqrt5}{2})^n}-\frac{5-\sqrt{5}}{10}*{(\frac{1-\sqrt5}{2})^n}

怎么转换为代码？使用结构体存储一个数的sqrt(5)项系数和整数系数,快速幂计算平方。

分数怎么办？

我们只需要除以2和10。由于原题答案要模1e9+7，我们预处理出：

10$的乘法逆元为$700000005

2$的乘法逆元为$500000004

就可以愉快的打代码了！

是不是比什么矩阵乘法简单多了？（逃

#include<cstdio>
#include<cstring>
#define ll long long
ll mod=1000000007;
long long mo(ll x){
    return ((x%mod)+mod)%mod;
}
struct num{
    ll s5,z;//sqrt(5)项,整项
};
num mul(num x,num y)
{
    num ans;
    ans.z=mo(mo(x.z*y.z)+mo(5ll*x.s5)*y.s5);
    ans.s5=mo(mo(x.s5*y.z)+mo(x.z*y.s5));
    return ans;
}
num qpow(num x,ll y)
{
    num ans;
    ans.s5=0;ans.z=1;
    while (y){
        if (y&1) ans=mul(x,ans);
        x=mul(x,x);
        y>>=1;
    }
    return ans;
}
int main()
{
    ll n;
    scanf("%lld",&n);
    n--;
    num a,b,c,d,e,f;
    a.s5=700000005;
    c.z=a.z=b.z=b.s5=d.z=500000004;
    d.s5=mo(-500000004);
    c.s5=mo(-700000005);
    e=mul(a,qpow(b,n));
    f=mul(c,qpow(d,n));
    printf("%lld\n",mo(e.z+f.z));
    return 0;
}

完结撒花！

参考资料：数列通项特征根法的证明https://wenku.baidu.com/view/71b1a7bcf90f76c661371ab6.html

特别鸣谢数学竞赛大佬CYX提供了巨大的帮助！