Answer with step-by-step explanation:
We are given that the recurrence relation
[tex]f_n=5f_{n-4}+3f_{n-5}[/tex]
for n=5,6,7,..
Initial condition
[tex]f_0=0,f_1=1,f_2=1,f_3=2,f_4=3[/tex]
We have to show that Fibonacci numbers satisfies the recurrence relation.
The recurrence relation of Fibonacci numbers
[tex]f_n=f_{n-1}+f_{n-2}[/tex],[tex]f_0=0,f_1=1[/tex]
Apply this
[tex]f_n=(f_{n-2}+f_{n-3})+f_{n-2}=2f_{n-2}+f_{n-3}[/tex]
[tex]f_n=2(f_{n-3}+f_{n-4})+f_{n-3}=3f_{n-3}+2f_{n-4}[/tex]
[tex]f_n=3(f_{n-4}+f_{n-5})+2f_{n-4}=5f_{n-4}+3f_{n-5}[/tex]
Substitute n=2
[tex]f_2=f_1+f_0=1+0=1[/tex]
[tex]f_3=f_2+f_1=1+1=2[/tex]
[tex]f_4=f_3+f_2=2+1=3[/tex]
Hence, the Fibonacci numbers satisfied the given recurrence relation .
Now, we have to show that [tex]f_{5n}[/tex] is divisible by 5 for n=1,2,3,..
Now replace n by 5n
[tex]f_{5n}=5f_{5n-4}+3f_{5n-5}[/tex]
Apply induction
Substitute n=1
[tex]f_5=5f_1+3f_0=5+0=5[/tex]
It is true for n=1
Suppose it is true for n=k
[tex]f_{5k}=5f_{5k-4}+3f_{5k-5}[/tex] is divisible 5
Let [tex]f_{5k}=5q[/tex]
Now, we shall prove that for n=k+1 is true
[tex]f_{5k+5}=5f_{5k+5-4}+3f_{5k+5-5}=5f_{5k+1}+3f_{5k}=5f_{5k+1}+3(5q)[/tex]
[tex]f_{5k+5}=5(f_{5k+1}+3q)[/tex]
It is multiple of 5 .Therefore, it is divisible by 5.
It is true for n=k+1
Hence, the [tex]f_{5n}[/tex] is divisible by 5 for n=1,2,3,..
