Fibonacci numbers solution to this recurrence relation

Question

Prove that the Fibonacci number's are the solutions the following recurrence relation, $$S_n=5S_{n-4}+3S_{n-5}$$ For all n greater than or equal to 5, where we have $$S_0=0$$ $$S_1=1$$ $$S_2=1$$ $$S_3=2$$ $$S_4=3$$ Then use the formula to show that the Fibonacci number's satisfy the condition that $f_n$ is divisible by 5 if and only if n is divisible by 5.

Answer 1

hint:characteristic equation$$x^5=5x+3\\x^5-5x-3=0$$ then $$x^2-x-1|x^5-5x-3\\ \to $$divide $x^5-5x-3$ by $x^2-x-1$ $$x^5-5x-3=(x^2-x-1)(x^3+x^2+2x+3)$$ and $x^2-x-1$ is the characteristic equation of $f_n=f_{n-1}+f_{n-2}\\----\\$

Another solving : $$f_{n+5}=f_{n+4}+f_{n+3}\\ =(f_{n+3}+f_{n+2})+f_{n+3}=\\2f_{n+3}+f_{n+2}$$ now put $f_{n+3}$ $$f_{n+5}=2f_{n+3}+f_{n+2}=\\2(f_{n+2}+f_{n+1})+f_{n+2}=\\3f_{n+2}+2f_{n+1}\\$$and now $$f_{n+5}=3f_{n+2}+2f_{n+1}=\\3(f_{n+1}+f_{n})+2f_{n+1}=\\5f_{n+1}+3f_n$$