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

Question

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?

Answer 1

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

Answer 2

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

Answer 3

We have more general answer:

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$

Answer 4

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.