Question

Show that the Fibonacci numbers satisfy the recurrence relation fn = 5fn−4 + 3fn−5 for n = 5, 6, 7, . . . , together 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, . . . .

Answer 1

Answer with step-by-step explanation:

We are given that the recurrence relation

$f_n=5f_{n-4}+3f_{n-5}$

for n=5,6,7,..

Initial condition

$f_0=0,f_1=1,f_2=1,f_3=2,f_4=3$

We have to show that Fibonacci numbers satisfies the recurrence relation.

The recurrence relation of Fibonacci numbers

$f_n=f_{n-1}+f_{n-2}$,$f_0=0,f_1=1$

Apply this

$f_n=(f_{n-2}+f_{n-3})+f_{n-2}=2f_{n-2}+f_{n-3}$

$f_n=2(f_{n-3}+f_{n-4})+f_{n-3}=3f_{n-3}+2f_{n-4}$

$f_n=3(f_{n-4}+f_{n-5})+2f_{n-4}=5f_{n-4}+3f_{n-5}$

Substitute n=2

$f_2=f_1+f_0=1+0=1$

$f_3=f_2+f_1=1+1=2$

$f_4=f_3+f_2=2+1=3$

Hence, the Fibonacci numbers satisfied the given recurrence relation .

Now, we have to show that $f_{5n}$ is divisible by 5 for n=1,2,3,..

Now replace n by 5n

$f_{5n}=5f_{5n-4}+3f_{5n-5}$

Apply induction

Substitute n=1

$f_5=5f_1+3f_0=5+0=5$

It is true for n=1

Suppose it is true for n=k

$f_{5k}=5f_{5k-4}+3f_{5k-5}$ is divisible 5

Let $f_{5k}=5q$

Now, we shall prove that for n=k+1 is true

$f_{5k+5}=5f_{5k+5-4}+3f_{5k+5-5}=5f_{5k+1}+3f_{5k}=5f_{5k+1}+3(5q)$

$f_{5k+5}=5(f_{5k+1}+3q)$

It is multiple of 5 .Therefore, it is divisible by 5.

It is true for n=k+1

Hence, the $f_{5n}$ is divisible by 5 for n=1,2,3,..