10
31
2016
0

线性递推数列特征方程相关存档

被51nod1653干翻

存个档省的自己忘掉。

对于一个线性递推数列$x_{n}=a*x_{n-1}+b*x_{n-2}$

我们设一个y,$x_{n}-y*x_{n-1}=(a-y)(x_{n-1}-b/(y-a)*x_{n-2})$

当$y=b/(y-a)$时$x_{n}-yx_{n-1}$会是一个等比数列,公比为$a-y$

设$y^{2}=ay+b$的解为r和s

当$r\neq s$时

$F(n)=x_{n}-r*x_{n-1}=F(1)*(a-r)^{n-1}=(x_{1}-r*x_{0})*(a-r)^{n-1}$

$G(n)=x_{n}-s*x_{n-1}=F(1)*(a-s)^{n-1}=(x_{1}-s*x_{0})*(a-s)^{n-1}$

$F(n)-G(n)=(s-r)*x_{n-1}$

根据韦达定理$r+s=a,rs=-b$

$x_{n-1}=(x_{1}-r*x_{0})*(a-r)^{n-1}/(s-r)-(x_{1}-s*x_{0})*(a-s)^{n-1}/(s-r)$

$x_{n-1}=(x_{1}-r*x_{0})*s^{n-1}/(s+b/s)+(x_{1}+s*x_{0})*r^{n-1}/(r+b/r)$

$x_{n}=c_{1}*s^n+c_{2}*r^n$

高斯消元解出$c_{1}$和$c_{2}$即可

以下是我自己的口胡

当$s=r$时$a=-2r$

$x_{1}-x_{0}=s*p$①

$x_{2}-x_{1}=s^2*p$②..

那么把①*s^n+②*s^(n-1)...加起来,就可以得到$x_{n}-s^n*x_{0}=p*n*s^{n}$就可以求解了

Category: 存档 | Tags: 数论 存档 | Read Count: 360

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter

Host by is-Programmer.com | Power by Chito 1.3.3 beta | Theme: Aeros 2.0 by TheBuckmaker.com