3
$\begingroup$

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?

$\endgroup$
1
  • $\begingroup$ 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$. $\endgroup$ – Batominovski Oct 28 '18 at 20:47
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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$

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.