show that Fibonacci numbers satisfy the recurrence relation

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整除.

与最初一起表示，斐波纳契数字满足递归关系fn=5f (n-4) +3f (n-5) n=5,6,7的…，适应f0=0， f1=1， f2=1， f3=2， f4=3.use这个递归关系为n=1,2,3表示， f5n由5是可分的，…
注：fibonacci number满足fn=f (n-1) +f (N2)