斐波那契数列重要恒等式的简单推导及应用（非严格证明）
数列通项公式：
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(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 #include using namespace std;arrayfib(int n){if (n<2) return {0,1,1};arrays={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){arrays;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)=3int 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倍。
10 1121 1231 2342 3553 5865 81378 13 2181321 3492134 5510 3455 8911 5589 14412 89144 23313 144 233 37714 233 377 61015 377 610 98716 610 987 159717 987 1597 258418 1597 2584 418119 2584 4181 676520 4181 6765 1094621 6765 10946 1771122 10946 17711 2865723 17711 28657 4636824 28657 46368 7502525 46368 75025 12139326 75025 121393 19641827 121393 196418 31781128 196418 317811 51422929 317811 514229 83204030 514229 832040 134626931 832040 1346269 217830932 1346269 2178309 352457833 2178309 3524578 570288734 3524578 5702887 922746535 5702887 9227465 1493035236 9227465 14930352 2415781737 14930352 24157817 3908816938 24157817 39088169 6324598639 39088169 63245986 10233415540 63245986 10233415516558014141 102334155 16558014126791429642 165580141 26791429643349443743 267914296 43349443770140873344 433494437 701408733113490317045 701408733 1134903170 183631190346 11349031701836311903 297121507347 18363119032971215073 480752697648 29712150734807526976 777874204949 48075269767778742049 1258626902550 777874204912586269025 2036501107451 12586269025 20365011074 3295128009952 20365011074 32951280099 5331629117353 32951280099 53316291173 8626757127254 53316291173 86267571272 13958386244555 86267571272 139583862445 22585143371756 139583862445 225851433717 36543529616257 225851433717 365435296162 59128672987958 365435296162 591286729879 95672202604159 591286729879 956722026041 154800875592060 956722026041 1548008755920 250473078196161 1548008755920 2504730781961 405273953788162 2504730781961 4052739537881 655747031984263 4052739537881 6557470319842 1061020985772364 6557470319842 10610209857723 1716768017756565 10610209857723 17167680177565 2777789003528866 17167680177565 27777890035288 4494557021285367 27777890035288 44945570212853 7272346024814168 44945570212853 72723460248141 11766903046099469 72723460248141 117669030460994 19039249070913570 117669030460994 190392490709135 30806152117012971 190392490709135 308061521170129 49845401187926472 308061521170129 498454011879264 80651553304939373 498454011879264 806515533049393 130496954492865774 806515533049393 1304969544928657 211148507797805075 1304969544928657 2111485077978050 341645462290670776 2111485077978050 3416454622906707 552793970088475777 3416454622906707 5527939700884757 894439432379146478 5527939700884757 8944394323791464 1447233402467622179 8944394323791464 144723340246762212341672834846768580 14472334024676221 234167283484676853788906237314390681 23416728348467685 378890623731439066130579072161159182 37889062373143906 613057907216115919919485309475549783 61305790721611591 9919485309475549716050064381636708884 99194853094755497 160500643816367088 25969549691112258585 160500643816367088259695496911122585 42019614072748967386 259695496911122585420196140727489673 67989163763861225887 420196140727489673679891637638612258 110008777836610193188 6798916376386122581100087778366101931 177997941600471418989 1100087778366101931 1779979416004714189 288006719437081612090 1779979416004714189 2880067194370816120 466004661037553030991 2880067194370816120 4660046610375530309 754011380474634642992 4660046610375530309 7540113804746346429 1220016041512187673893 7540113804746346429 12200160415121876738 1293530146158671551F45=1134903170F89=1779979416004714189F90=2880067194370816120F91=4660046610375530309F50=12586269025--------------------------------Process exited after 0.1388 seconds with return value 0请按任意键继续. . .