Let $(F_n)_{n \in \mathbb{N}}$ be a Fibonacci sequence , then $(4 \mid n \Leftrightarrow 3 \mid F_n)$ for all $n \in \mathbb{N}$

Question

I would like to ask if my below proof is fine or if it has any error! Furthermore, I feel that my approach is a bit long, so please suggest any faster or nice approach. Thank you for your help!

Theorem:

Let $(F_n)_{n \in \mathbb{N}}$ be a Fibonacci sequence such that $F_0=0,F_1=1$ and $F_{n+2}=F_{n+1}+F_{n}$ for all $n \in \mathbb{N}$. Then $(4 \mid n \Leftrightarrow 3 \mid F_n)$ for all $n \in \mathbb{N}$.

Proof:

Let $P(n)$ is the statement $(4 \mid n \Leftrightarrow 3 \mid F_n)$.

$F_0=0 \implies (4 \mid 0 \wedge 3 \mid F_0) \implies P(0)$ is true.

Assuming $P(k)$ is true for $k \leq n$. There are 4 possible cases in total.

1. $n+1 = 4x+4$

$4 \mid 4x \implies 3 \mid F_{4x} \implies F_{4x}=3r$.

$4 \not \mid 4x+1 \implies 3 \not \mid F_{4x+1} \implies F_{4x+1}=3s+p$ where $p \in \{1,2\}$.

We have:

$F_{4x+2}=F_{4x+1}+F_{4x}=3r+3s+p$

$F_{4x+3}=F_{4x+2}+F_{4x+1}=3r+6s+2p$

$F_{4x+4}=F_{4x+3}+F_{4x+2}=6r+9s+3p$

$\implies F_{n+1}=F_{4x+4}=6r+9s+3p \implies 3 \mid F_{n+1}$

As a result, $(4 \mid n+1 \wedge 3 \mid F_{n+1})$. This implies $P(n+1)$ is true.

2. $n+1 = 4x+3$

$4 \mid 4x \implies 3 \mid F_{4x} \implies F_{4x}=3r$.

$4 \not \mid 4x+1 \implies 3 \not \mid F_{4x+1} \implies F_{4x+1}=3s+p$ where $p \in \{1,2\}$.

We have:

$F_{4x+2}=F_{4x+1}+F_{4x}=3r+3s+p$

$F_{4x+3}=F_{4x+2}+F_{4x+1}=3r+6s+2p$

$\implies F_{n+1}=F_{4x+3}=3r+6s+2p \implies 3 \not \mid F_{n+1}$

As a result, $(4 \not \mid n+1 \wedge 3 \not \mid F_{n+1})$. This implies $P(n+1)$ is true.

3. $n+1 = 4x+2$

$4 \mid 4x \implies 3 \mid F_{4x} \implies F_{4x}=3r$.

$4 \not \mid 4x+1 \implies 3 \not \mid F_{4x+1} \implies F_{4x+1}=3s+p$ where $p \in \{1,2\}$.

We have:

$F_{4x+2}=F_{4x+1}+F_{4x}=3r+3s+p$

$\implies F_{n+1}=F_{4x+2}=3r+3s+p \implies 3 \not \mid F_{n+1}$

As a result, $(4 \not \mid n+1 \wedge 3 \not \mid F_{n+1})$. This implies $P(n+1)$ is true.

4. $n+1 = 4x+1$

$4 \not \mid 4x-1 \implies 3 \not \mid F_{4x-1} \implies F_{4x-1}=3s+p$ where $p \in \{1,2\}$.

$4 \mid 4x \implies 3 \mid F_{4x} \implies F_{4x}=3r$.

We have:

$F_{4x+1}=F_{4x}+F_{4x-1}=3r+3s+p$

$\implies F_{n+1}=F_{4x+1}=3r+3s+p \implies 3 \not \mid F_{n+1}$

As a result, $(4 \not \mid n+1 \wedge 3 \not \mid F_{n+1})$. This implies $P(n+1)$ is true.

To sum up 1, 2, and 3: $P(n+1)$ is true.

By principle of strong induction, $P(n+1)$ is true for all $n \in \mathbb{N}$.

Answer 1

Base case

$F_1=1,F_2 = 1, F_3=2, F_4 = 3$

Our position is true for all $n\le 4$

Suppose our proposition is true for all all $n\le 4k$

3 does not divide $F_{4k-1}$

$3|F_{4k}$

3 does not divide $F_{4k-1}$

3 does not divide $F_{4k+1} = F_{4k} + F_{4_k-1}$

3 does not divide $F_{4k+2} = F_{4k+1} + F_{4_k}$

3 does not divide $F_{4k+3} = F_{4k+2}+ f_{4k+1} = 2F_{4k+1} + F_{4k}$

$3|F_{4k+4} = 3F_{4k+1}+2f_{4k}$

More generally $n|m \iff F_n|F_m$ but that will take a little bit more work.

Answer 2

The sequence mod (3) is

$$\{0,1,1,2,0,2,2,1,0,1,1,2,0,1.....\}$$ Which is periodic and $ a_n=0$ iff $n=4k.$

Similarly you can prove other relations such as $$ m|n \iff F_m|F_n$$