引理1
结论：F(n)=F(m)F(n−m+1)+F(m−1)F(n−m)
推导：
F(n)
=F(n−1)+F(n−2)
=2F(n−2)+F(n−3)
=3F(n−3)+2F(n−4)
=5F(n−4)+3F(n−5)
=⋯
=F(m)F(n−m+1)+F(m−1)F(n−m)
看出系数的规律了，2=1+1，3=2+1，5=3+2，……
用数学归纳法严谨证明一下：
1）当m=2时，F(n)=F(2)F(n−2+1)+F(2−1)F(n−2)=F(n−1)+F(n−2)成立。
2）设当m=k(2≤k≤n−2)时，F(n)=F(k)F(n−k+1)+F(k−1)F(n−k)成立。
又∵F(k−1)=F(k+1)−F(k)
∴F(n)=F(k)F(n−k+1)+[F(k+1)−F(k)]F(n−k)
即F(n)=F(k+1)F(n−k)+F(k)[F(n−k+1)−F(n−k)]
又∵F(n−k+1)−F(n−k)=F(n−k−1)
∴F(n)=F(k+1)F(n−k)+F(k)F(n−k−1)，说明当m=k+1时等式也成立。
综上，F(n)=F(m)F(n−m+1)+F(m−1)F(n−m)对于[2,n−1]内的任意一个整数m都成立。
引理2
gcd(F(n),F(n−1))=1
根据gcd更相减损性质：gcd(a,b)=gcd(b,a−b)(a>b)
得gcd(F(n),F(n−1))=gcd(F(n−1),F(n)−F(n−1))=gcd(F(n−1),F(n−2))
不断套用上式得到gcd(F(n),F(n−1))=gcd(F(2),F(1))=1
证明gcd(F(n),F(m))=F(gcd(n,m))
由引理1可知gcd(F(n),F(m))=gcd(F(m)F(n−m+1)+F(m−1)F(n−m),F(m))(n>m)
而F(m)F(n−m+1)为F(m)的倍数，故gcd(F(n),F(m))=gcd(F(m−1)F(n−m),F(m)) （gcd的更相减损，可以消掉F(m)的倍数）
因为F(m),F(m−1)互质，于是gcd(F(n),F(m))=gcd(F(n−m),F(m))
递归上式，
gcd(F(n),F(m))=gcd(F(n−m),F(m))=gcd(F(n−m−m),F(m))=⋯=gcd(F(nmodm),F(m))
再递归上式，我们需要比较nmodm与m谁更大，用大的数mod小的数。这不就是辗转相除法求最大公约数吗？
于是gcd(F(n),F(m))=gcd(F(gcd(n,m)),F(gcd(n,m)))=F(gcd(n,m))
证毕。
如未声明转载，本文作者为 1024th（https://www.cnblogs.com/1024th/p/10897313.html）
版权：原创文章采用「署名-非商业性使用-相同方式共享 4.0 国际」协议进行许可，转载文章另行声明许可证
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/103305.html
