# If $2 \mid F_n$, then $4 \mid F_{n+1}^2-F_{n-1}^2$, where $F_n$ is $n$-th Fibonacci number

I want to show that

• If $$2 \mid F_n$$, then $$4 \mid F_{n+1}^2-F_{n-1}^2$$
• If $$3 \mid F_n$$, then $$9 \mid F_{n+1}^3-F_{n-1}^3$$

where $$F_n$$ is the $$n$$-th Fibonacci number.

I have tried the following so far:

Since $$F_1=F_2=1$$, we suppose that $$n \geq 3$$.

\begin{align} F_{n+1}&=F_n+F_{n-1} \\ F_{n+1}^2&=(F_n+F_{n-1})^2=F_n^2+2F_n F_{n-1}+F_{n-1}^2 \end{align}

\begin{align} F_{n-1} &=F_{n-2}+F_{n-3} \\ F_{n-1}^2&=(F_{n-2}+F_{n-3})^2=F_{n-2}^2+2F_{n-2}F_{n-3}+F_{n-3}^2 \end{align} so that $$F_{n+1}^2-F_{n-1}^2=F_n^2+2F_n F_{n-1}+F_{n-1}^2-F_{n-2}^2-2 F_{n-2} F_{n-3}-F_{n-3}^2$$

How can we deduce that the latter is divisible by $$4$$?

Or do we show it somehow else, for example by induction?

• If $F_n$ is even, then both $F_{n+1}$ and $F_{n-1}$ are odd because two consecutive terms of the Fibonacci sequence cannot be both even (as $\gcd(F_n,F_{n+1})=1$ for all integers $n$), so in fact, $8\mid F_{n+1}^2-F_{n-1}^2$. – Batominovski Oct 28 '18 at 20:47

$$F_{n+1}^2-F_{n-1}^2=(F_{n+1}-F_{n-1})(F_{n+1}+F_{n-1}) =F_n(F_{n+1}+F_{n-1}).$$ Also $$F_{n+1}=F_n+F_{n-1}\equiv F_{n-1}\pmod{F_n}$$, so $$F_{n+1}+F_{n-1}\equiv 2F_{n-1}\pmod{F_n}$$. If $$F_n$$ is even, then so is $$F_{n+1}+F_{n-1}$$.

Similarly $$F_{n+1}^3-F_{n-1}^3=F_n(F_{n+1}^2+F_{n+1}F_{n-1}+F_{n-1}^2)$$ and $$F_{n+1}^2+F_{n+1}F_{n-1}+F_{n-1}^2\equiv 3F_{n-1}^2\pmod{F_n}$$ etc.

Note that$$F_{n+1}^2-F_{n-1}^2=(F_{n+1}-F_{n-1})(F_{n+1}+F_{n-1})=F_n(F_n+2F_{n-1}).$$And if $$2\mid F_n$$, $$4\mid F_n(F_n+2F_{n-1})$$.

On the other hand\begin{align}F_{n+1}^3-F_{n-1}^3&=(F_{n+1}-F_{n-1})(F_{n+1}^2+F_{n+1}F_{n-1}+F_{n-1}^2)\\&=F_n\bigl((F_n+F_{n-1})^2+F_n+F_{n-1}+F_{n-1}^2+F_{n-1}^2\bigr)\\&=F_n(F_n^2+3F_nF_{n-1}+3F_{n-1}^2).\end{align}And if $$3\mid F_n$$, $$9\mid F_n(F_n^2+3F_nF_{n-1}+3F_{n-1}^2)$$.

If $$k\mid a-b$$ then $$k^2\mid a^k-b^k$$
Proof: Write $$a-b=km$$ for some integer $$m$$. Then we have $$a^k-b^k=(a-b)(\underbrace{a^{k-1}+a^{k-2}b+a^{k-3}b^2+...+b^{k-1}}_E)$$
$$\begin{eqnarray}E&\equiv_k& b^{k-1}+b^{k-2}b+b^{k-3}b^2+...+b^{k-1}\\ &\equiv_k&k\cdot b^{k-1} \\ &\equiv_k&0 \\ \end{eqnarray}$$ so $$E = k\cdot p$$ for some interger $$p$$, so we have $$k^2\mid a^k-b^k$$
Modulo two the Fibonacci sequence cyclically repeats the pattern of length three $$0,1,1,0,1,1,0,1,1,\ldots$$. So if $$F_n$$ is even then both $$F_{n-1}$$ and $$F_{n+1}$$ are odd. Therefore both $$F_{n-1}^2$$ and $$F_{n+1}^2$$ are congruent to $$1\pmod 4$$ (mod eight actually!). Therefore their difference is a multiple of eight.
Modulo three the cyclically repeating pattern has length eight: $$0,1,1,2,0,2,2,1,0,1,1,2,0,2,2,1,\ldots.$$ Again, we see that if $$F_n$$ is divisible by three, then $$F_{n-1}$$ and $$F_{n+1}$$ are either both $$\equiv1\pmod 3$$ or both $$\equiv-1\pmod3$$.
In the former case their cubes are both $$\equiv 1\pmod 9$$ (check that $$1^3\equiv4^3\equiv7^3\pmod9$$. In the latter case both cubes are $$\equiv -1\pmod9$$ ($$2^3\equiv5^3\equiv8^3$$). Both these facts actually also follow from the fact that the group $$\Bbb{Z}_9^*$$ is cyclic of order six.