Show that for each $n \geq 1$ it holds that $2^{n-1} F_n \equiv n \pmod{5}$ I want to show that for each $n \geq 1$ it holds that:
$$2^{n-1} F_n \equiv n \pmod{5}$$
where $F_n$ is the $n$-th Fibonacci number.
Could you give a hint how we can show this?
The sequence $F_n$ of Fibonacci numbers is defined by the recurrence relation:
$$F_n=F_{n-1}+F_{n-2} \\ F_1=1, F_2=1.$$
Right? Do we use the definion in order to get to the desired result?

Use the general term formula:
$$2^{n-1} F_n \equiv 2^{n-1}\cdot \frac{\phi^n-\psi^n}{\sqrt{5}} \equiv \frac{(1+\sqrt{5})^n-(1-\sqrt{5})^n}{2\sqrt{5}} \equiv\\
\frac{2{n\choose 1}\sqrt{5}+2{n\choose 3}(\sqrt{5})^3+2{n\choose 5}(\sqrt{5})^5+\cdots +2{n\choose 2\lfloor{\frac{n-1}{2}\rfloor}+1}(\sqrt{5})^{2\lfloor{\frac{n-1}{2}\rfloor}+1}}{2\sqrt{5}}\equiv\\
n+{n\choose 3}\cdot 5+{n\choose 5}\cdot 5^2+\cdots +{n\choose 2\lfloor{\frac{n-1}{2}\rfloor}+1}\cdot 5^{\lfloor{\frac{n-1}{2}\rfloor}}\equiv
n \pmod{5}.$$
