斐波那契数列是一个很神奇的东西，今天我们就来谈一谈它。
前言：本篇博客中会有大量的公式，每一个公式都会给出严谨的证明（证明方法都是最严谨的数学归纳法）
1.从特征方程说起
前言：事实上，特征方程所求得的通项公式在实际应用中几乎不用。但是至少要了解，并会由递推式计算通项式。
特征方程：特征方程可以理解为求通项公式的一个工具。
对于一阶递推式，形如：f[i]=p*f[i-1]+x
设q，满足f[i]+q=p(f[i-1]+q)
展开得到f[i]=p*f[i-1]+q*(p-1)
\therefore$ $x=q*(p-1)
q=\frac{x}{p-1}
令g[i]=f[i]+q
易知{g[i]}为等比数列，公比为p
所以g[i]=(f[1]+q)*p^{i-1}
f[i]=(f[1]+\frac{x}{p-1})*p^{i-1}-\frac{x}{p-1}
对于二阶递推式，形如：f[i]=p*f[i-1]+q*f[i-2]
设u,v，满足f[i]-u*f[i-1]=v*(f[i-1]-u*f[i-2])
f[i]=(u+v)*f[i-1]+u*v*f[i-2]
展开得到q=-u*v
u^{2}=p*u+q
这就是特征方程。
可以看到{f[i]-u*f[i-1]}是一个公比为v的等比数列
\frac{f[i]-u*f[i-1]}{f[i-1]-u*f[i-2]}=v
设f[1]-u*f[0]=a
f[2]-u*f[1]=a*v
……
f[n]-u*f[n-1]=a*v^{n-1}
通过计算得到
f[n]-u^{n}*f[0]=a*\sum^{n}_{i=1}(u^{n-1}*(\frac{v}{u})^{i-1})
对于u,v的大小关系分两类讨论，就可以得到：
当两根不相同时，f[n]可以表示成A*u^{n}+B*v^{n}的形式
我们对于斐波那契数列递推式进行一遍上述操作
注意：这里是广义的斐波那契数列
即：a[1]=m,a[2]=k,a[n]=p*a[n-1]+q*a[n-2]
注：p^2+4*q>0,p,q\neq0,n>2
令a[n]=A*\alpha^{n}+B*\beta^{n}
其中有\alpha,\beta为方程x^{2}=p*x+q（特征方程）的两根
前文保证（p^{2}+4*q>0，即\Delta>0）
不妨设\alpha=\frac{p-\sqrt{p^{2}+4*q}}{2}
\beta=\frac{p+\sqrt{p^{2}+4*q}}{2}
所以a[n]=A*\alpha^{n}+B*\beta^{n}=A*(\frac{p-\sqrt{p^{2}+4*q}}{2})^{n}+B*(\frac{p+\sqrt{p^{2}+4*q}}{2})^{n}
上式对a[1],a[2]同样成立
将a[1],a[2]代入得
m=\frac{p-\sqrt{p^{2}+4*q}}{2}*A+\frac{p+\sqrt{p^{2}+4*q}}{2}*B
k=(\frac{p-\sqrt{p^{2}+4*q}}{2})^{2}*A+(\frac{p+\sqrt{p^{2}+4*q}}{2})^{2}*B
令\sqrt{p^{2}+4*q}=y，则原方程为
m=\frac{p-y}{2}*A+\frac{p+y}{2}*B
k=(\frac{p-y}{2})^{2}*A+(\frac{p+y}{2})^{2}*B
令\frac{p-y}{2}=s,\frac{p+y}{2}=t,s+t=p,t-s=y
m=s*A+t*B
k=s^{2}*A+t^{2}*B
A=\frac{(p+y)*m-2*k}{(p-y)*y}
B=\frac{2*k-(p-y)*m}{(p+y)*y}
所以a[n]=\frac{(p+y)*m-2*k}{(p-y)*y}*(\frac{p-y}{2})^{n}+\frac{2*k-(p-y)*m}{(p+y)*y}*(\frac{p+y}{2})^{n}
读者可以把m=k=p=q=1代入上式，就可以得到斐波那契的通项公式
f[n]=\frac{1}{\sqrt{5}}*[(\frac{1+\sqrt{5}}{2})^{n}-(\frac{1-\sqrt{5}}{2})^{n}]
当p^{2}-4*q<=0时，读者可以自行思考一下，通项公式又会变成什么样
2.矩阵乘法
在具体实现中，如果题目要求数据范围过大，特征方程所求的通项公式不容易实现，暴力递推会TLE。
因此，我们采用矩阵乘法。
由于f[i]=f[i-1]+f[i-2]是一个很简单的递推式，它的矩阵也很简单
\begin{bmatrix}1&1\\1&0\end{bmatrix}
关于矩阵乘法的其他内容本文不再阐述，推荐洛谷日报：从零开始的矩阵乘法
时间复杂度：O(log(n))
模板题：P1962 斐波那契数列
这是一道关于斐波那契数列的模板题
观察数据范围得到，朴素的O(n)算法显然会TLE。显然用矩阵乘法。
同理，P1349也是同样的方法，但是递推矩阵不一样
\begin{bmatrix}p&1\\q&0\end{bmatrix}
这里贴一下P1962的代码
#include<bits/stdc++.h>
#define LL long long
using namespace std;
LL n;
const LL mod=1000000007;
struct matrix{
LL a[5][5];
}ans;//矩阵
void print(matrix a)
{
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
printf("%lld ",a.a[i][j]);
printf("\n");
}
}//打印矩阵
matrix init()
{
matrix ret;
ret.a[1][1]=1,ret.a[1][2]=1;
ret.a[2][1]=1,ret.a[2][2]=0;
return ret;
}//递推矩阵
matrix mul(matrix a,matrix b)
{
matrix ret;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
ret.a[i][j]=0;
for(int k=1;k<=2;k++)
ret.a[i][j]+=(a.a[i][k]*b.a[k][j])%mod,ret.a[i][j]%=mod;
}
}
//print(ret);
return ret;
}//矩阵相乘
matrix fast_power(matrix a,LL x)
{
matrix ret;
for(int i=1;i<=2;i++)
{
for(int j=1;j<=2;j++)
{
if(i==j)ret.a[i][j]=1;
else ret.a[i][j]=0;
}
}//初始矩阵
while(x)
{
if(x&1)ret=mul(ret,a);
a=mul(a,a);
x>>=1;
}
return ret;
}//矩阵快速幂
int main()
{
scanf("%lld",&n);
ans=fast_power(init(),n-1);
printf("%lld\n",ans.a[1][1]);
return 0;
}
3.斐波那契数列的一个性质
同时，我们可以采用另外一种做法：
f[2*n]=f[n+1]^{2}-f[n-1]^{2}=(2*f[n-1]+f[n])*f[n]
f[2*n+1]=f[n+1]^{2}+f[n]^{2}
在这里，我们证明一下这两个定理。
证明1：
直接采用通项公式(通项公式还是有用的)
设s=\frac{1+\sqrt{5}}{2},t=\frac{1-\sqrt{5}}{2}
引理：
s^{n}-t^{n}=\frac{(1+\sqrt{5})^{n}-(1-\sqrt{5})^{n}}{2^{n}}
把(1+\sqrt{5})^{n}和(1-\sqrt{5})^{n}进行多项式展开
……
这样的证明过于繁琐，读者可以亲自尝试一下。
证明2：
采用数学归纳法
设1至2*n都满足上述公式 （两个公式同时满足）
f[2*n+1]=f[2*n]+f[2*n-1]=f[n+1]^{2}-f[n-1]^{2}+f[n]^{2}+f[n-1]^{2}=f[n+1]^{2}+f[n]^{2}
f[2*n+2]=f[2*n+1]+f[2*n]
=f[n+1]^{2}+f[n]^{2}+f[n+1]^{2}-f[n-1]^{2}
=f[n+1]^{2}+f[n+1]^{2}+f[n]^{2}-f[n-1]^{2}
=f[n+1]^{2}+f[n+1]^{2}-2*f[n+1]*f[n]+f[n]^{2}-f[n-1]^{2}+2*f[n+1]*f[n]
=f[n+1]^{2}+f[n-1]^{2}-f[n-1]^{2}+2*f[n+1]*f[n]
=f[n+1]^{2}+2*f[n+1]*f[n]
=f[n+1]*(2*f[n]+f[n+1])
=f[n+2]^{2}-f[n]^{2}
所以原命题成立
证明3：
f[2*n]=f[n+1]^{2}-f[n-1]^{2}
f[2*n+1]=f[n+1]^{2}+f[n]^{2}
只需证明：
f[n+m]=f[m-1]*f[n]+f[m]*f[n+1]
若上式成立
f[2*n]=f[n+n]
=f[n-1]*f[n]+f[n]*f[n+1]
=f[n]*(f[n+1]+f[n-1])
=f[n+1]^{2}-f[n-1]^{2}
f[2*n+1]=f[n+(n+1)]
=f[n-1]*f[n+1]+f[n]*f[n+2]
=f[n+1]^{2}-f[n]*f[n+1]+f[n]^2+f[n]*f[n+1]
=f[n+1]^{2}+f[n]^{2}
那怎么证明上面这个式子呢？
还是可以通过数学归纳法（只是这里提供了一个新的思路，后期也要用到这个定理）
设1至x-1都两两满足f[n+m]=f[m-1]*f[n]+f[m]*f[n+1]
下证
f[1+x]=f[x-1]*f[1]+f[x]*f[2]
f[2+x]=f[x-1]*f[2]+f[x]*f[3]
……
f[x-1+x]=f[x-1]*f[x-1]+f[x]*f[x]
对于任意的f[p+x]
都有f[p+x]=f[(p-1)+x]+f[(p-2)+x]
=f[p+(x-1)]+f[(p-1)+(x-1)]
=f[x-2]*f[p]+f[x-1]*f[p+1]+f[x-2]*f[p-1]+f[x-1]*f[p]
=f[x-2]*f[p+1]+f[x-1]*f[p+2]
=f[x]*f[p+1]-f[x-1]*f[p+1]+f[x-1]*f[p]+f[x-1]*f[p+1]
=f[x]*f[p+1]+f[x-1]*f[p]
所以原命题成立
利用减半递推+记忆化，便可以AC
代码：
#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")//强行优化
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n;
const ll mod=1e9+7;
map<ll,ll>f;
ll solve(ll x)
{
if(x==0)return 0;
if(x==1)return 1;
if(x==2)return 1;//边界条件
ll y=(x>>1),f1=f[y-1]?f[y-1]:solve(y-1),f2=f[y]?f[y]:solve(y),f3=f[y+1]?f[y+1]:solve(y+1);//处理f[y-1],f[y],f[y+1]
if(x&1)return (f[x]=(f3*f3+f2*f2+mod)%mod);//如果为奇数
else return (f[x]=(f3*f3-f1*f1+mod)%mod);//如果为偶数
//套用公式+记忆化，把答案丢进map里
}
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch>'9'||ch<'0') { if(ch=='-') f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') { x=x*10+ch-'0';ch=getchar();}
return x*f;
}
int main()
{
scanf("%lld",&n);
printf("%lld\n",(solve(n)+mod)%mod);//疯狂取模
return 0;
}
时间复杂度：递归O(log(n)),mapO(log(n))总时间复杂度为O(log^{2}(n))
这里提到了这两个公式，顺便再拓展一个：
f[3*n]=f[n+1]^{3}+f[n]^{3}-f[n-1]^{3}
有兴趣的读者可以亲自证明一下。
当然啦，它对应的也有两个公式。
上述的数学归纳法的证明必须有几个公式互相依靠。
4.另外一个性质
我们先来看一道题目
P1306 斐波那契公约数
题目描述：
对于Fibonacci数列：1,1,2,3,5,8,13......大家应该很熟悉吧~~~
但是现在有一个很“简单”问题：第n项和第m项的最大公约数是多少？(n\leqslant1e9)
本题要求gcd(f[n],f[m])
我们可以用矩阵乘法把f[n],f[m]都算出来
题目要求对1e8取模，所以做gcd的时候就会遇到问题。
斐波那契数列中还有一个性质：
gcd(f[n],f[m])=f[gcd(n,m)]
证明：
若证gcd(f[n],f[m])=f[gcd(n,m)]
即证gcd(f[n+m],f[n])=gcd(f[m],f[n])
gcd(f[n+m],f[n])
=gcd(f[n+1]f[m]+f[n]f[m-1],f[n])
=gcd(f[n+1]f[m],f[n])
=gcd(f[n+1],f[n])*gcd(f[m],f[n])
=gcd(f[m],f[n])
得证
有了这个性质之后
题目<==>求f[gcd(n,m)] mod 1e8
矩阵乘法即可
5.又一个性质
先看一道题P3986
题目描述：
定义一个数列：
f(0) = a, f(1) = b, f(n) = f(n - 1) + f(n - 2)
其中 a, b 均为正整数，n≥2。
问有多少种 (a, b)，使得k出现在这个数列里，且不是前两项。
由于答案可能很大，你只需要输出答案模10^{9}+7的结果即可。
数据范围：
1≤k≤10^{9}
简单分析得：
设g[0]=1,g[1]=1,g[n]=g[n-1]+g[n-2](n≥2)(就是斐波那契数列)
显然有f[n]=g[n-1]*a+g[n-2]*b(n≥2)
问f[n]=k的情况数
由于1≤k≤10^{9}，所以n的取值范围也很小，只要暴力枚举g[n-1],g[n-2]，然后对于每一种情况用exgcd解一个不定方程即可
这里介绍另一种方法
先介绍一个性质
f[i]f[i-1]-f[i+1]f[i-2]=(-1)^{i}
(f[0]=0,f[-1]=1)
还是用数学归纳法
另g[i]=f[i]f[i-1]-f[i+1]f[i-2]
当i=0时，原式显然成立
g[i]=(f[i-1]+f[i-2])f[i-1]-(f[i]+f[i-1])f[i-2]
=f[i-1]^{2}-f[i]f[i-2]
设i=k时，原命题成立
g[k]=f[k-1]^{2}-f[k]f[k-2]
g[k+1]=f[k]^{2}-f[k+1]f[k-1]
g[k]+g[k+1]=0
\because g[k]=-1^{k}
\therefore g[k+1]=-1^{k+1}
两式相加得0
所以原命题成立
根据上式
方程g[n-1]*a+g[n-2]*b=k就有通解x=k*-1^{n-2}f[n-3]
求得一个解之后，其余的就好求了
6.线段树
众所周知，线段树可以处理很多关于区间的问题
（如果对线段树没有了解的，推荐洛谷日报浅谈线段树或者我的博客线段树1，线段树2，线段树3）
这是关于数列操作的一个表格。
注意到13操作：区间加斐波那契数列
这就是我们接下来要研究的
例题：
CF446C
题意翻译:
题面大意：给出一个数列，每次可以选取一个区间，按顺序加上第i个Fibonacci Numbers(斐波那契数)进行更新，也可以查询某一个区间的总和。
这题虽然是黑题，其实并不难
我们只要思考几件事：
1.线段树的标记下传（pushdown）能不能在O(1)内完成
2.线段树更新sum能不能在O(1)内完成
对于1，前文提到f[n]=g[n-1]*a+g[n-2]*b
对于2，这里再提一个性质：
令s[i]=\sum_{i=1}^{n}f[i]
s[i]=f[n+2]-f[2]
这个定理的证明
还是用数学归纳法。。。
显然当i=1时，原命题成立
设i=k时，原命题成立。
s[k+1]=s[k]+f[k+1]=f[k+2]-f[2]+f[k+1]=f[k+3]-f[2]
便能实现再$O(1)$内完成更新$sum$了
代码：
```
#include<bits/stdc++.h>
#define rd(x) x=read()
#define N 300005
#define ls rt<<1
#define rs rt<<1|1
using namespace std;
typedef long long ll;
ll n,m;
struct T{
ll f1,f2,v;
}t[N*20];
ll a[N],f[N],sum[N];
const ll mod=1e9+9;
inline ll read()
{
ll f=1,x=0;char s=getchar();
while(s<'0'||s>'9'){if(s=='-')f=-1;s=getchar();}
while(s>='0'&&s<='9'){x=x*10+s-'0';s=getchar();}
return x*f;
}
void init()
{
f[1]=1,f[2]=1;
for(ll i=3;i<=n+1;i++)f[i]=(f[i-2]+f[i-1])%mod;
}//预处理斐波那契
void pushup(ll rt,ll pos)
{
t[rt].f1%=mod,t[rt].f2%=mod;
t[rt].v=t[ls].v+t[rs].v+(t[rt].f1*f[pos]+t[rt].f2*f[pos+1]-t[rt].f2),t[rt].v%=mod;
}//更新rt
void pushdown(ll rt,ll l,ll r)
{
if(t[rt].f1==0&&t[rt].f2==0)return ;
ll mid=(l+r)>>1;
t[ls].f1+=t[rt].f1,t[rs].f1+=t[rt].f1*f[mid-l]+t[rt].f2*f[mid-l+1];
t[ls].f2+=t[rt].f2,t[rs].f2+=t[rt].f1*f[mid-l+1]+t[rt].f2*f[mid-l+2];
t[rt].f1=t[rt].f2=0;
pushup(ls,mid-l+1),pushup(rs,r-mid);
} //标记下传
void update(ll rt,ll l,ll r,ll L,ll R)
{
if(L<=l&&r<=R)//边界条件
{
t[rt].f1+=f[l-L+1];
t[rt].f2+=f[l-L+2];
t[rt].f1%=mod,t[rt].f2%=mod;
pushup(rt,r-l+1);
return ;
}
pushdown(rt,l,r);
ll mid=(l+r)>>1;
if(L<=mid)update(ls,l,mid,L,R);
if(mid<R)update(rs,mid+1,r,L,R);
pushup(rt,r-l+1);
}//区间加斐波那契数列
ll query(ll rt,ll l,ll r,ll L,ll R)
{
if(L<=l&&r<=R)return t[rt].v;
pushdown(rt,l,r);
ll res=0;
ll mid=(l+r)>>1;
if(L<=mid)res+=query(ls,l,mid,L,R);
if(mid<R)res+=query(rs,mid+1,r,L,R);
return res%mod;
}//查询和
int main()
{
rd(n),rd(m);
init();
for(ll i=1;i<=n;i++)rd(a[i]),sum[i]=sum[i-1]+a[i];//预处理前缀和
while(m--)
{
ll opt,l,r;
rd(opt),rd(l),rd(r);
if(opt==1)update(1,1,n,l,r);
else printf("%lld\n",(query(1,1,n,l,r)+sum[r]-sum[l-1]+mod)%mod);
}
return 0;
}
```
---
#### 7.$\sum_{i=1}^{n}f[i]*i
\sum_{i=1}^{n}f[i]*i=n*f[n+2]-f[n+3]+2
命运驱使着我用数学归纳法。。。
当n=1时，原命题显然成立
设n=k时，原命题成立
令s[i]=\sum_{i=1}^{n}f[i]*i
s[k+1]=s[k]+f[k+1]*(k+1)
=k*f[k+2]-f[k+3]+2+f[k+1]*(k+1)
=k*f[k+3]-f[k+3]+2+f[k+1]
=k*f[k+3]-f[k+2]+2
所以原命题成立
然后用矩阵乘法计算即可。
参考文献
衷心的感谢以上的文献
推荐文献
完结撒花！
后记：
在翻阅洛谷日报的时候，我发现很多的算法都已经介绍了，
唯独没有神奇的斐波那契数列，于是心血来潮，写下了这篇文章。