fn=f(n-1)+f(n-2)=f(n-2)+2f(n-3)+f(n-4)
=f(n-3)+f(n-4)+2f(n-3)+f(n-4)=3f(n-3)+2f(n-4)=3(f(n-4)+f(n-5))+2f(n-4)=5f(n-4)+3f(n-5)
归纳法证明,当n=1时,f5=5,5整除f5,命题成立,假设命题对任意n成立,下面考虑n+1时的情况,利用上面等式有
f5(n+1)=f(5n+5)=5f(5n+1)+3f(5n)
由归纳法假设上式右边第2项被5整除,第1项含有因子5,故f5(n+1)也能被5整除,完成归纳法证明,故对任意n,fn能被5整除.