Show that for each $n \geq 1$ it holds that $2^{n-1} F_n \equiv n \pmod{5}$

Question

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?

Answer 1

$$2^{n-1}F_n=2^{n-1}(F_{n-1}+F_{n-2})=2(2^{n-2}F_{n-1})+4(2^{n-3}F_{n-2}) \\\equiv 2(n-1)+4(n-2) \equiv 6n-10\equiv n\mod5.$$

Also,

$$2^{1-1}F_1=1\equiv 1$$ and

$$2^{2-1}F_2=2\equiv 2.$$

Answer 2

By induction over $n$, the base cases $n=1,2$ are trivial.

$$\begin{align} 2^{k} F_{k+1} &= 2^k(F_k+F_{k-1})\\ &= 2^kF_k+2^kF_{k-1} \\ &\equiv 2k+4(k-1) \pmod{5}\\ &\equiv k+1 \pmod{5} \end{align}$$

Answer 3

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}.$$