0

Given $F_m$ be the $m^\text{th}$ number in the Fibonacci sequence. Prove that for all natural $n$, $$ F_{2n - 1}^2 \equiv -1 \pmod {F_{2n + 1}} \text{ and } F_{2n + 1}^2 \equiv -1 \text{ (mod }F_{2n - 1})$$

It is sufficient to prove that

\begin{align} & F_{2n - 1}^2 + F_{2n + 1}^2 + 1 = 3F_{2n - 1} \cdot F_{2n + 1} \\[8pt] \impliedby {} & F_{2n}^2 = F_{2n - 1} \cdot F_{2n + 1} - 1 \end{align}

but I don't know how to prove that.

And it would be greatly appreciated if there are any other solutions to this problem.

Lê Thành Đạt
  • 4,228

2 Answers2

3

There is a stronger statement, that $F_{n}^2 = F_{n-2}F_{n+2} + (-1)^n$.

For $n = 1$, $F_1^2= 1= F_{-1}F_{3}+(-1)$.

Assume that for some $n=k$, $F_{k}^2 = F_{k-2}F_{k+2} + (-1)^k$.

For $n=k+1$,

$$\begin{align*} F_{k+1}^2 - F_{k-1}F_{k+3} &= (F_{k-1}+F_{k})F_{k+1}-F_{k-1}(F_{k+1}+F_{k+2})\\ &= F_kF_{k+1}-F_{k-1}F_{k+2}\\ &= F_k(F_{k+2}-F_k)-(F_k-F_{k-2})F_{k+2}\\ &= -F_{k}^2+F_{k-2}F_{k+2}\\ &= -(-1)^k\\ F_{k+1}^2&= F_{k-1}F_{k+3} + (-1)^{k+1} \end{align*}$$

Alternatively, like the matrix proof in Cassini's identity,

$$\begin{align*} F_{k+1}^2 - F_{k-1}F_{k+3} &= \det\pmatrix{F_{k+1}&F_{k+3}\\F_{k-1}&F_{k+1}}\\ &= \det\pmatrix{F_{k+1}&F_{k+2}\\F_{k-1}&F_{k}}\pmatrix{1&1\\0&1}\\ &= \det\pmatrix{F_{k}&F_{k+2}\\F_{k-2}&F_{k}}\pmatrix{-1&0\\1&1}\pmatrix{1&1\\0&1}\\ &= (F_k^2 - F_{k+2}F_{k-2}) (-1)(1)\\ F_{k+1}^2&= F_{k-1}F_{k+3} + (-1)^{k+1} \end{align*}$$

So $F_{n}^2 = F_{n-2}F_{n+2} + (-1)^n$ is true by induction.

Substituting special cases $2n-1$ and $2n+1$ respectively,

$$\begin{align*} F_{2n-1}^2 &= F_{2n-3}F_{2n+1} -1 \equiv -1 \pmod{F_{2n+1}}\\ F_{2n+1}^2 &= F_{2n-1}F_{2n+3} -1 \equiv -1 \pmod{F_{2n-1}}\\ \end{align*}$$

peterwhy
  • 22,256
2

Hint:

To prove Cassini's identity $F_{2n}^2=F_{2n-1}\cdot F_{2n+1}-1$,

you could use Binet's formula $F_n=\dfrac{\phi^n-\left(\dfrac{-1}{\phi}\right)^n}{\sqrt5},$

where $\phi$ is the golden ratio, which satisfies $\phi-\dfrac1\phi=1$.

J. W. Tanner
  • 60,406