数列通项公式：
F(1)=F(2)=1;
F(n)=F(n-1)+F(n-2), n>2.
通项公式的前一项是：
F(n-1)=F(n-2)+F(n-3)
前一项代入通项中，得：
F(n)=2*F(n-2)+F(n-3)
再把更前一项F(n-2)=F(n-3)+F(n-4)代入上式，得：
F(n)=3*F(n-3)+2*F(n-4)
...以此类推：
F(n)=5*F(n-4)+3*F(n-5)
F(n)=8*F(n-5)+5*F(n-6)
F(n)=13*F(n-6)+8*F(n-7)
......
等号右边的系数又分别都是斐波那契数列，
两个新数列的函数自变量刚好差1，
且F(7)=13,F(6)=8，F(5)=5...可得：
F(n)=F(m)F(n-m+1)+F(m-1)F(n-m) --公式①
先用m+n替换公式①中的n,得:
F(m+n)=F(m)*F(n+1)+F(m-1)*F(n) --公式②
令m=n,代入公式②,得:
F(2n)=F(n)*F(n+1)+F(n-1)*F(n) --公式③
再令m=n+1,代入公式②,得:
F(2n+1)=F(n+1)*F(n+1)+F(n)*F(n)
表示成平方和形式：
F(2n+1)=F²(n+1)+F²(n) --公式④
公式④自变量减一，得：
F(2n-1)=F²(n)+F²(n-1) --公式④'
公式④自变量增一，得：
F(2n+3)=F²(n+2)+F²(n+1)
上式与公式④相减：
F²(n+2)-F²(n)=F(2n+3)-F(2n+1)
而 F(2n+3)=F(2n+2)+F(2n+1)，所以：
F(2n+2)=F²(n+2)-F²(n) --公式⑤
还有一个公式：
F(n+1)*F(n-1)-F²(n)=(-1)ⁿ --公式⑥
这个公式是1680年法国人卡尼发现的，看似蛮神奇的。
但现如今基本初中学生都会，就用内比公式计算即可。
内比公式是其实是法国数学家棣莫弗发现的(1730年)。
是由另一个法国数学家内比证明的(19世纪初)。
内比公式：
为方便书写，设：
分别计算 5 * F(n+1) * F(n-1) 和 5 * F²(n)：
5F(n+1)*F(n-1)
= (Pⁿ * P-Qⁿ * Q)(Pⁿ / P-Qⁿ / Q)
= P²ⁿ + Q²ⁿ - PⁿQⁿ(P/Q) - PⁿQⁿ(Q/P)
= P²ⁿ + Q²ⁿ - (PQ)ⁿ(P/Q+Q/P)
= P²ⁿ + Q²ⁿ + 3 * (-1)ⁿ
5F²(n)
= P²ⁿ + Q²ⁿ - 2 * PⁿQⁿ
= P²ⁿ + Q²ⁿ - 2 * (-1)ⁿ
两式相减后，两边都除以5，得：F_{n+1} * F_{n-1} - F{_{n}}^{2} = (-1)^{n}，得证。
也可写成：
应用以下这些公式计算斐波那契数列：
F(m+n)=F(m)*F(n+1)+F(m-1)*F(n)
F(2n-1)=F²(n)+F²(n-1)
F(2n)=F(n)*F(n+1)+F(n-1)*F(n)
F(2n+1)=F²(n+1)+F²(n)
自变量即数列的项数成倍成倍地下降，在C++编程中可以减少循环次数提高效率，比如计算第20000项，只要先求第10000项和前或后一项就能求得结果，前提是要解决大整数相乘精确求解。
先用项数小于94的整数来测试一下这些公式：
#include <iostream> #include <array> using namespace std; array<size_t,3>fib(int n) { if (n<2) return {0,1,1}; array<size_t,3>s={1,1,2}; for (auto i=3; i<=n; ++i){ s[2] = s[0]+s[1]; s[0] = s[1]; s[1] = s[2]; } s[2] = s[0]+s[1]; return s; } int main(void) { array<size_t,3>s; for (int i=1;i<94;i++){ s=fib(i); cout<<i<<'\t'<<s[0]<<"\t "<<s[1]<<"\t "<<s[2]<<endl; } int n=45; s=fib(n); cout<<"\nF"<<n<<"="<<s[1]<<endl; //F(2n-1)=F2(n)*F2(n)+F2(n-1)*F2(n-1) cout<<"F"<<2*n-1<<"="<<s[1]*s[1]+s[0]*s[0]<<endl; //F(2n)=F(n)*F(n+1)+F(n-1)*F(n) cout<<"F"<<2*n<<"="<<s[1]*(s[2]+s[0])<<endl; //F(2n+1)=F2(n+1)*F2(n+1)+F2(n)*F2(n) cout<<"F"<<2*n+1<<"="<<s[2]*s[2]+s[1]*s[1]<<endl; //F(m+n)=F(m)*F(n+1)+F(m-1)*F(n); m=5时:F(5)=5,F(4)=3 int m=5; cout<<"F"<<n+m<<"="<<5*s[2]+3*s[1]<<endl; return 0; }
测试结果如下，其中fib()函数返回一个数组，包含了F(n-1)、F(n)、F(n+1)三项便于下一步的运算，如有大数相乘函数的配合：如此计算10次，项数就能扩大1024倍。
1 0 1 1 2 1 1 2 3 1 2 3 4 2 3 5 5 3 5 8 6 5 8 13 7 8 13 21 8 13 21 34 9 21 34 55 10 34 55 89 11 55 89 144 12 89 144 233 13 144 233 377 14 233 377 610 15 377 610 987 16 610 987 1597 17 987 1597 2584 18 1597 2584 4181 19 2584 4181 6765 20 4181 6765 10946 21 6765 10946 17711 22 10946 17711 28657 23 17711 28657 46368 24 28657 46368 75025 25 46368 75025 121393 26 75025 121393 196418 27 121393 196418 317811 28 196418 317811 514229 29 317811 514229 832040 30 514229 832040 1346269 31 832040 1346269 2178309 32 1346269 2178309 3524578 33 2178309 3524578 5702887 34 3524578 5702887 9227465 35 5702887 9227465 14930352 36 9227465 14930352 24157817 37 14930352 24157817 39088169 38 24157817 39088169 63245986 39 39088169 63245986 102334155 40 63245986 102334155 165580141 41 102334155 165580141 267914296 42 165580141 267914296 433494437 43 267914296 433494437 701408733 44 433494437 701408733 1134903170 45 701408733 1134903170 1836311903 46 1134903170 1836311903 2971215073 47 1836311903 2971215073 4807526976 48 2971215073 4807526976 7778742049 49 4807526976 7778742049 12586269025 50 7778742049 12586269025 20365011074 51 12586269025 20365011074 32951280099 52 20365011074 32951280099 53316291173 53 32951280099 53316291173 86267571272 54 53316291173 86267571272 139583862445 55 86267571272 139583862445 225851433717 56 139583862445 225851433717 365435296162 57 225851433717 365435296162 591286729879 58 365435296162 591286729879 956722026041 59 591286729879 956722026041 1548008755920 60 956722026041 1548008755920 2504730781961 61 1548008755920 2504730781961 4052739537881 62 2504730781961 4052739537881 6557470319842 63 4052739537881 6557470319842 10610209857723 64 6557470319842 10610209857723 17167680177565 65 10610209857723 17167680177565 27777890035288 66 17167680177565 27777890035288 44945570212853 67 27777890035288 44945570212853 72723460248141 68 44945570212853 72723460248141 117669030460994 69 72723460248141 117669030460994 190392490709135 70 117669030460994 190392490709135 308061521170129 71 190392490709135 308061521170129 498454011879264 72 308061521170129 498454011879264 806515533049393 73 498454011879264 806515533049393 1304969544928657 74 806515533049393 1304969544928657 2111485077978050 75 1304969544928657 2111485077978050 3416454622906707 76 2111485077978050 3416454622906707 5527939700884757 77 3416454622906707 5527939700884757 8944394323791464 78 5527939700884757 8944394323791464 14472334024676221 79 8944394323791464 14472334024676221 23416728348467685 80 14472334024676221 23416728348467685 37889062373143906 81 23416728348467685 37889062373143906 61305790721611591 82 37889062373143906 61305790721611591 99194853094755497 83 61305790721611591 99194853094755497 160500643816367088 84 99194853094755497 160500643816367088 259695496911122585 85 160500643816367088 259695496911122585 420196140727489673 86 259695496911122585 420196140727489673 679891637638612258 87 420196140727489673 679891637638612258 1100087778366101931 88 679891637638612258 1100087778366101931 1779979416004714189 89 1100087778366101931 1779979416004714189 2880067194370816120 90 1779979416004714189 2880067194370816120 4660046610375530309 91 2880067194370816120 4660046610375530309 7540113804746346429 92 4660046610375530309 7540113804746346429 12200160415121876738 93 7540113804746346429 12200160415121876738 1293530146158671551 F45=1134903170 F89=1779979416004714189 F90=2880067194370816120 F91=4660046610375530309 F50=12586269025 -------------------------------- Process exited after 0.1388 seconds with return value 0 请按任意键继续. . .
