Show that the Fibonacci numbers satisfy the recurrence
relation fn = 5fn−4 + 3fn−5 for n = 5, 6, 7,..., to-
gether with the initial conditions f0 = 0, f1 = 1, f2 = 1,
f3 = 2, and f4 = 3. Use this recurrence relation to show
that f5n is divisible by 5, for n = 1, 2, 3,... .

Question

Show that the Fibonacci numbers satisfy the recurrence
relation fn = 5fn−4 + 3fn−5 for n = 5, 6, 7,..., to-
gether with the initial conditions f0 = 0, f1 = 1, f2 = 1,
f3 = 2, and f4 = 3. Use this recurrence relation to show
that f5n is divisible by 5, for n = 1, 2, 3,... .

perl · Answer

by 'show' do you mean try some examples

perl · Answer

or we can prove it rigorously

perl · Answer

the fibonacci sequence is defined as 

f(n) = f(n-1) + f(n-2) , for n > 1

perl · Answer

5 f(n-4) + 3* f(n-5)
 =5* [f(n-5) + f(n-6) ] + 3 [ f (n-6) + f(n-7) ]

perl · Answer

5 * f(n-5) + 5* f(n-6) + 3* f(n-6) + 3* f(n-7)

anonymous · Answer

thanks Perl