一、定义
斐波那契数，又称黄金分割数列，是指数列:(0,1,1,2,3,5,8,……)。表示后一个数由前两个数的和组成，递归上定义为(f[0]=0,f[1]=1,f[i]=f[i-1]+f[i-2])。
二、通项公式
接下来用推导斐波那契数的通项公式：
假设常数s、r满足：
(f[n]-r*f[n-1]=s*(f[n-1]-r*f[n-2]))
再结合斐波那契数的定义，我们可以得到：
(r+s=1,rs=-1)
所以，对于(n≥3)时，有：
(f[n]-r*f[n-1]=s*(f[n-1]-r*f[n-2]))
(f[n-1]-r*f[n-2]=s*(f[n-2]-r*f[n-3]))
(……)
(f[3]-r*f[2]=s*(f[2]-r*f[1]))
我们联立这n-2个式子，可以得到：
(f[n]-r*f[n-1]=s^{n-2}*(f[2]-r*f[1]))
因为：
(s=1-r,f[1]=f[2]=1)
所以可以化简：
(f[n]=s^{n-1}+r*f[n-1])
(=s^{n-1}+r*s^{n-2}+r^2*f[n-2])
(=s^{n-1}+r*s^{n-2}+r^2*s^{n-3}+r^3*f[n-3])
(……)
(=s^{n-1}+r*s^{n-2}+r^2*s^{n-3}+……+r^{n-1})
这就是一个以(s^{n-1})为首项，(r^{n-1})为末项，(frac{r}{s})为公比的等比数列，直接运用等比数列求和公式：
[原式=frac{s^{n-1}-r^{n-1}*frac{r}{s}}{1-frac{r}{s}} ][=frac{s^n-r^n}{s-r} ]因为前文求出的两个关于(r、s)的式子其中一组解为：
[s=frac{1+sqrt{5}}{2},r=frac{1-sqrt{5}}{2} ]所以通项公式为：
[f[n]=frac{sqrt{5}}{5}*[(frac{1+sqrt{5}}{2})^n-(frac{1-sqrt{5}}{2})^n] ]
例1 普通递归关系
给出以下定义在非负整数n下的递归关系：
其中(a、b)是满足以下两个条件的常数：
(一)(a^2+4b>0)
(二)(|a-sqrt{a^2+4b}|≤2)
给出(f_0,f_1,a,b,n)，求(f[n])
我们考虑直接暴推公式，用类似斐波那契数的方法求得公式为：
其中：
直接快速幂求解就行了。
然而推完式子后发现这实际上是复杂度理论上和矩阵快速幂一样的，而且矩阵快速幂好写很多，然后就不想写代码了。
例2 数字迷阵
题面太长，懒得打了，自己去看吧。数字迷阵
我们考虑每一行都相当于是斐波那契数，只要求出前两项即可，所以我们考虑前两项的规律。
由于我们知道(A[i,2]=2A[i,1]-(i-1)),只要考虑找出(A[i,1])的规律即可。
对于(A[i,1])，我们分析它的差值可以知道：
(1sim2)行：(3)
(3sim4)行：(2-3)
(5sim7)行：(3-2-3)
(8sim12)行：(2-3-3-2-3)
所以每次的差值就是由前两项的差值拼接起来，接下来就是求通项公式;
但我们发现直接求通项公式很复杂，代码也难以在合适的时间复杂度内模拟，我们考虑求出它的前两项（(0)列和(-1)列）：
| 列数 | -1 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | |
| 1 | 3 | 4 | 7 | 11 | 18 | 29 | 47 | 76 | 123 | |
| 2 | 4 | 6 | 10 | 16 | 26 | 42 | 68 | 110 | 178 | |
| 3 | 6 | 9 | 15 | 24 | 39 | 63 | 102 | 165 | 267 | |
| 4 | 8 | 12 | 20 | 32 | 52 | 84 | 136 | 220 | 356 |
所以我们可以发现第(-1)列的规律是自然数依次递增，而这个第(0)列，看着十分眼熟，实际上这与(Wythoff)博弈有关，我们知道(Wythoff)博弈的必胜态为：
而Wythoff博弈后手必胜态的通项为：
定理：Wthyoff博弈的必胜态为序列(W)（即上述序列），通项公式为((lfloor nphi floor,lfloor nphi^2 floor))
证明：我们先证明序列W满足这三个性质：
(1、W无重复且不遗漏包含了所有整数)
(2、W中两数之差依次为1，2，3，4，……)
(3、W中的较小数依次递增)
性质1：
Beatty-Rayleigh 定理
对于任意两个正无理数满足(frac{1}{alpha}+frac{1}{eta}=1),那么数列(lflooralpha floor,lfloor2alpha floor,lfloor3alpha floor,……)和数列(lflooreta floor,lfloor2eta floor,lfloor3eta floor,……)既无重复有无遗漏的包含了所有的正整数而(phi)和(phi^2)恰好就是满足条件的两个正无理数(定理的具体证明就不写了)
性质(2)和(3)比较显然，我们可以直接由通项公式知道
由这三个性质我们可以知道三个关于W的条件
(1、W中的任意一个数对都无法一步变成终止状态(0,0))
(2、W中的任意一个数对都无法通过一步变成W中的另一个数)
(3、W外的任何一个数对都可以一步变成(0,0)或W中的数对)
所以显然W是满足要求的数对
不过关于(Fibonacci)数列和(Wthyoff)还有很多更深的联系，就不再赘述了，大家想了解可以看这位大佬的博客
所以我们从一道(Fibonacci)+矩阵快速幂题成功扯到了博弈，而事实关系远不止如此，题目中要我们求得表实际上就是(wthyoff)表，而这又和(Zeckendorf)表达有关，不得不感叹数学海洋的辽阔。
扯到这里，第(1)列的通项公式就出来了，由于第(-1)列的通项为(i-1)，第(0)列的通项为(lfloor iphi floor),所以第(1)列的通项就为(lfloor iphi+i-1 floor)
已知前两项的斐波那契数做法就很多了，我们可以直接代入之前的公式，也可以用矩阵快速幂求解。
代码就不贴了，知道结论挺好写的。