showthatFibonaccinumberssatisfytherecurrencerelationfn=5f(n-4)+3f(n-5)forn=5,6,7...,togetherwiththeinitialconditionsf0=0,f1=1,f2=1,f3=2,f4=3.usethisrecurrencerelationtoshowthatf5nisdivisibleby5,forn=1,2,3...注：fibonacci

Question

show that Fibonacci numbers satisfy the recurrence relation fn=5f(n-4)+3f(n-5) for n=5,6,7...,together with the initial conditions f0=0,f1=1,f2=1,f3=2,f4=3.use this recurrence relation to show that f5n is divisible by 5,for n=1,2,3...
注：fibonacci number满足fn=f(n-1)+f(n-2)

Answer 1

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