# 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?

• "Do we use the definion in order to get to the desired result?" Of course we do. Clearly this result doesn't hold for all sequences, so in order to prove it, we have to use the fact that our sequence is the Fibonacci sequence and not some other arbitrary sequence. That means we absolutely can't avoid using the definition, either directly or implicitly. – Arthur Oct 28 '18 at 9:56

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

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}

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