## Can the difference of two distinct Fibonacci numbers be a square infinitely often?

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

Can the difference of two distinct Fibonacci numbers be a square infinitely often?

There are few solutions with indices $<10^{4}$ the largest two being $F_{14}-F_{13}=12^2$ and $F_{13}-F_{11}=12^2$

Probably this means there are no identities between near neighbours.

Since Fibonacci numbers are the only integral points on some genus 0 curves the problem is equivalent to finding integral points on one of few varieties. Fixing $F_j$ leads to finding integral points on a quartic model of an elliptic curve.

Are there other solutions besides the small ones?

[Added later] Here is a link to elliptic curves per François Brunault's comment.

According to DIOPHANTINE EQUATIONS, FIBONACCI HYPERBOLAS,. AND QUADRATIC FORMS. Keith Brandt and John Koelzer.

Fibonacci numbers with consecutive odd indices are the only solutions to $$x^2-3xy+y^2 = -1 \qquad (1)$$

Fibonacci numbers with consecutive even indices are the only solutions to $$x^2-3xy+y^2 = 1 \qquad (2)$$

Given $F_n$ and $F_{n+2}$ one can compute $F_{n+k}$ using the linear Fibonacci recurrence and $F_{n+k}$ will be a linear combination $l(x,y)$ of $x,y$. Adding $l(x,y)-x=z^2$ to (1) or (2) gives a genus 1 curve. (Or just solve $l(x,y)-x=z^2$ and substitute in (1) or (2) to get a genus 1 quartic).

The closed form of $l(x,y)$ might be of interest, can't find the identity at the moment.

Probably a genus 0 curve with integral points $F_{2n},F_{2n+1}$ will be better.

Added much later

Does some generalization of the $abc$ conjecture predict something?

For 3 Fibonacci numbers identities are much easier:

$$F_{4n+1}+F_{4n+3}-F_3 = L_{2n+1}^2$$

-

2
Another note: for differences of consecutive Fibonacci's, or gaps of $2$ (i.e. F_{n+2}-F_n) the answer is that the only square values are $1$ and $144$. This follows from a result of J. Cohn, On square Fibonacci numbers, J. London Math. Soc. 39 1964. – Alan Haynes Jan 3 2012 at 12:01

4
Using Cohn's characterization of when $F_n = 2x^2$ (it's true only when n = 0, 3, or 6), and simplifying $F_{n+3} - F_n = 2F_{n+1}$, the only examples separated by 3 are $F_5 - F_2 = 4$, and $F_8 - F_5 = 16$. Similarly, to find all pairs separated by 4, simplify $F_{n+2} - F_{n-2} = F_{n+1} + F_{n-1} = L_n$ to get that the Lucas number $L_n$ must be a square, so n = 1 or 3, giving $F_5 - F_1 = 4$ as the only solution. Both characterizations come from J. Cohn's paper "Square Fibonacci Numbers, Etc." Fibonacci Quarterly 2 1964, pp. 109-113. – Zack Wolske Jan 3 2012 at 13:48

3
In a similar fashion, you can show that there is a solution (and exactly one) separated by 6 terms: $F_{15} - F_9 = 576 = 24^2$. But this example relies on the Lucas number $L_3$ being a square, so there's no hope that it produces an infinite family. – Zack Wolske Jan 3 2012 at 14:54

3
Shorey and Stewart proved that in any non-trivial second-order linear recurrence sequence, there are only finitely many perfect powers. (See Bugeaud-Mignotte-Siksek www-irma.u-strasbg.fr/~bugeaud/travaux/fibo.pdf) So after fixing the gap, there are only finitely many squares. I don't know whether this can be made effective. – François Brunault Jan 3 2012 at 19:35

3
The result of Shorey and Stewart is effective (though rather non-explicit!). For fixed $j$ with $F_k-F_j=x^2$, the link to elliptic curves comes from the fact that Fibonacci numbers are the $y$-values satisfying $x^2-5 y^2 = \pm 4$. I don't see how to prove finiteness for the general problem, ineffectively or otherwise (but 10 hours as department head has undeniably left my brain enfeebled). – Mike Bennett Jan 4 2012 at 3:28
show 16 more comments

## 4 Answers

All of the solutions for $F_{n + 4m} - F_n$ are the ones listed, barring the cases $m=2$ and $m=12$ where I still have some kinks to work out.

Following Will Sawin's suggestion, we write $F_{n + m} - F_n$ as a reccurence, with some initial terms. Taking $n=0$ tells us that $F_m$ is one term, and $F_{m+1} - 1$ is the next. Extrapolating backwards, we have the general term $F_{m-i} + (-1)^i F_i$. So we see that if $m=4k+2$, then the term $i = 2k+1$ gives us $0$, and the next term gives us $F_{2k} + F_{2k+2} = L_{2k+1}$, so we have a copy of the Fibonacci numbers, multiplied by $L_{2k+1}$. That is, $F_{n + 4k+2} - F_n = L_{2k+1}F_{n + 2k+1}$. If $m = 4k$, then the term $i=2k$ gives us $2F_{2k}$, and the next term gives us $F_{2k+1} - F_{2k-1}=F_{2k}$, so we have a copy of the Lucas numbers, multiplied by $F_{2k}$. That is, $F_{n + 4k} - F_n = F_{2k}L_{n + 2k}$. This is useful, because there are certain primes which never divide Lucas numbers (see http://oeis.org/A053028), so if $F_{2k}$ contains one of these primes (exactly one is easiest, but any odd multiple will do), then the product cannot be a square.

Agol gave a link to a paper in the comments (http://www.fq.math.ca/Scanned/7-1/ferns.pdf) which also contains this result.

Let's find all squares where $m = 2^k$. The cases $k=0, 1$ were given by AH in the comments, and the case $k=2$ is also included there. We need two facts about Lucas numbers, both of which are easy to show. First, $3 | L_m$ iff $m \equiv 2 \pmod{4}$ and second, $7 | L_m$ iff $m \equiv 4 \pmod{8}$.

Since $4 | 2^k$, we can write $F_{n + 2^k} - F_n = F_{2^{k-1}}L_{n + 2^{k-1}}$. I have not resolved the case $k = 3$ (this gap has been fixed, see 2nd edit below), it is equivalent to finding Lucas numbers $x$ in the Diophantine equation $x^2 + 2 = 3y^2$. For now assume $k > 3$. By the facts above, we know that $3$ and $7$ cannot both divide a Lucas number, so we want to show that each of them divide $F_{2^{k-1}}$, and that neither $3^2$ nor $7^2$ do so. That both 3 and 7 divide follows from $F_8=21$ and $F_n | F_{2n}$. That both 9 and 49 don't divide follows by induction: the base case is $F_8$; and we have $F_{2^{k+1}} = F_{2^k}L_{2^k}$, and neither 3 nor 7 can divide $L_{2^k}$ when $k>2$. Then by induction the squares do not divide $F_{2^k}$ for $k \geq 3$, and neither $3$ nor $7$ divide $L_{2^k}$, since $2^k \equiv 0 \pmod{8}$. Hence there are no squares when $m = 2^k$ and $k > 3$.

For the general case of $m=4k$, we write $F_{n + 4k} - F_n = F_{2k}L_{n + 2k} = F_{k}L_{k}L_{n + 2k}$ and invoke Carmichael's theorem: for each $n>3$, there is at least one prime $p | F_n$ which divides no previous Fibonacci number. Such a prime is called a primitive. Further - this is not part of the theorem - $p^2 \nmid F_n$ (after trying to work out a proof of this, I went to the literature and found that this is a conjecture in P. Ribenboim "Square classes of Fibonacci and Lucas numbers" Port. Math 46 (1989), 159-175. I'm not sure if it's been proven or falsified since then). Taking $n$ to be odd, we exploit the fact that $p$ does not divide any Lucas number, since its Fibonacci entry point is odd (see C. Ballot and M. Elia, "Rank and period of primes in the Fibonacci sequence; a trichotomy," Fib. Quart., 45 (No. 1, 2007), 56-63). If the odd part of $k$ is greater than $3$, we are done, since we can continue splitting $F_{k} = F_{k/2}L_{k/2}$ until we have an odd indexed Fibonacci number, and use a primitive for it. So we now have only $k = 3\cdot2^i$ left to consider. $i = 0$ and $i=1$ are easy to deal with: $F_{n + 12} - F_n = F_{6}L_{n + 6} = 8L_{n+6}$ and we know $L_{n+6} = 2x^2$ only if $n=0$ or negative (from J. Cohn's paper "Square Fibonacci Numbers, Etc." Fibonacci Quarterly 2 1964, pp. 109-113). $F_{n + 24} - F_n = F_{12}L_{n + 12} = 12^2L_{n+6}$ and we know $L_{n+12} = x^2$ has no solutions (again barring negative Fibonacci numbers - in these cases no solutions are distinct from the positive ones). $i=2$ causes me some trouble, and led to the negative solution $F_{36} - F_{-12} = 3864^2$. I also leave this unresolved.

For $i > 2$, we proceed as in the argument for powers of $2$. Both $7$ and $47$ divide $F_{3\cdot2^{i+1}}$ exactly once, with the base case being $F_{48}$, and they cannot both divide $L_{n + 3\cdot2^{i+1}}$, since $47 | L_m$ iff $m \equiv 8 \pmod{16}$.

The other even differences should fall the same way, although the formula for those fixes a Lucas number and varies the Fibonacci numbers, we can still find a primitive for the odd part of the Fibonacci index, but I'll have to patch up some pieces where the odd part is 3 or 1.

I've had some success with the odd differences using J. Cohn's trick: $L_m | (F_{n+2m} + F_n)$ when $3 \nmid m$ and $2|m$, and the fact that $L_m \equiv 3 \pmod{4}$ for such $m$, but no arguments covering infinitely many differences.

EDIT: The other even numbers are easier. Writing $F_{n + 4k+2} - F_n = L_{2k+1}F_{n + 2k+1}$ and considering $F_{n + 2k+1}$, the primitive argument removes all indices $n+2k+1$ with an odd part greater than $3$. The same argument as above works for all powers of $2$, since $3$ never divides $L_{2k+1}$. Finally, when the odd part is $3$, it's easier than before, since $7$ divides $F_{3\cdot2^i}$ for $i > 2$, $7^2$ never does, and $7$ and cannot divide the Lucas numbers since they have odd index. $i= 0, 1$ and $2$ are solved by finding all Lucas numbers which are squares, or $2$ times a square.

EDIT 2: For $m=2^3$, we want to know if $F_4L_{n+4} = 3L_{n+4}$ is a square. This is solved in M. Goldman. "On Lucas Numbers of the Form $px^2$ where $p=3,7,47,2207$". Math. Reports Canada Acad. Sci. (June 1988). The only example is n+4 = 2, which either does or doesn't happen according to your taste.

-

There is a gap here where my argument assumes that no higher powers of a primitive divides its Fibonacci number. As far as I know, it's not resolved. – Zack Wolske Jan 5 2012 at 11:49
Something similar to yours is: warwick.ac.uk/~maseap/papers/fnpm.pdf FIBONACCI NUMBERS AT MOST ONE AWAY FROM A PERFECT POWER YANN BUGEAUD, FLORIAN LUCA, MAURICE MIGNOTTE, SAMIR SIKSEK  – joro Jan 7 2012 at 7:27
@joro: It looks like their decomposition works because 1 appears with both even and odd index in the sequence, so they can apply the argument for even differences (or sums) twice. That's why the same argument won't work for $F_n + 2 = y^p$. – Zack Wolske Jan 7 2012 at 15:02
The gap can be resolved as follows: If $p$ is an odd prime dividing a Fibonacci number with odd index (it need not be a primitive factor), then it does not divide any Lucas number. This follows from $\gcd(F_a, F_b) = F_{\gcd(a,b)}$. We can always find such a prime with odd exponent in the factorization of $F_q$ for q >3 and odd, since otherwise we get $F_q = x^2$ or $F_q = 2x^2$.  – Zack Wolske Jan 7 2012 at 15:08
@Zack With "the squares do not divide $F_{2^k}$ " you mean $F_{2^k}$ is squarefree? – joro Jan 4 at 9:40
show 1 more comment

### You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.

Reporting on some computations: the only solutions to $F_k - F_j = x^2$ with $0\leq j < k$ and $1 \leq x \leq 10^6$ are these:

{0,1,1}, {0,2,1}, {1,3,1}, {2,3,1}, {3,4,1},
{1,5,2}, {2,5,2}, {5,8,4}, {6,11,9}, {0,12,12},
{11,13,12}, {13,14,12}, {6,13,15}, {9,15,24}

where the format is {j,k,x}.

-

7
It's easy enough to search well past $x = 10^6$. The following gp code takes little only ~10 minutes here to try $F_k-F_j$ for all $j < k \leq 10^4$, and thus all $x$ up to $\sqrt{F_{9998}} > 10^{1000}$. Not too surprisingly, though, it finds no further solutions other than the spurious $(j,k,x)=(1,2,0)$. for(j=0,10^4,for(k=j+1,10^4,if(issquare(fibonacci(k)-fibonacci(j),&x),print([j,k,x])))) – Noam D. Elkies Jan 4 2012 at 3:32
and I find no new ones up to $10^{200}$... – Mike Bennett Jan 4 2012 at 3:40

3
oops. sure wish I could take that back.... – Mike Bennett Jan 4 2012 at 3:41

2
@Noam Wouldn't your code be significantly faster if you precompute fibonacci(i) in f[i] and then check issquare(f[k]-f[i])? You need not compute fibonacci(i) many times. – joro Jan 4 2012 at 7:22

3
@joro Good question. I didn't do it that way because (i) A table vector(N+1,i,fibonacci(i-1)) takes about $N^2$ space, (ii) I thought the issquare test would take longer in any case (that turns out not to be the case, though $F_j$ takes only $O(\log(j))$ operations to compute), and (iii) Precomputing the table would make the code longer than one command ;-) – Noam D. Elkies Jan 4 2012 at 14:56
show 2 more comments

This is a slight elaboration on joro's comment; I was hoping that someone else would write a better version of this.

The integer points on $x^2-xy-y^2 = 1$ are precisely the pairs $(F_{2n+1}, F_{2n})$. So looking for solutions of the form $F_{2n+1} - F_{2m+1} = z^2$ is looking for integer points on $$x_1^2 - x_1 y_1 - y_1^2 = x_2^2 - x_2 y_2 - y_2^2 = 1,\ x_1 -x_2 = z^2.$$ The other three possibilities give similar equations.

Each of these is a $K3$ surface. Here is where a better answer would review the major results on integer points on $K3$ surfaces. But I don't know them, so I'm going to stop here and hope someone else fills it in.

-
Thank you. Is it possible $x^2-x y-y^2 = -1$ to be a typo?. I get $x^2-x y-y^2 = +1$ – joro Jan 6 2012 at 10:34
Right, thank you. – David Speyer Jan 6 2012 at 13:12
The package "desing" de-singularized the surface. If I have done it right I see no curves on it (and the remaining solutions must be quite large). – joro Jan 6 2012 at 13:22

1
AFAIK, there are no proven major results on integer points on affine pieces of K3 surfaces. However, Vojta's conjecture predicts that the set of such points lies on a finite union of curves. So assuming Vojta's conjecture, one might be able to make further progress. – Joe Silverman Jan 4 at 23:21
A finite union of genus zero curves (plus finitely many counterexamples), due to Siegel's theorem. I think that what joro was saying above was that there are no rational curves on this surface, but I may have misunderstood him. – David Speyer Jan 5 at 1:24

I get numerical support for the link with integral points on genus 1 curves.

For $x,y=F_n,F_{n+2}$ experimentally the closed form is $F_{n+k}=l(x,y)= F_{k} y -F_{k-2} x$ (probably provable by induction).

For a fixed gap $k$ solutions correspond to (positive?) integral points on: $$z^{4} + (2 {F_{k-2}} - 3 {F_{k}} + 2) x z^{2} + ({F_{k-2}}^{2} - 3 {F_{k-2}} {F_{k}} + {F_{k}}^{2} + 2 {F_{k-2}} - 3 {F_{k}} + 1) x^{2} + {F_{k}}^{2}=0$$ or $$z^{4} + (2 {F_{k-2}} - 3 {F_{k}} + 2) x z^{2} + ({F_{k-2}}^{2} - 3 {F_{k-2}} {F_{k}} + {F_{k}}^{2} + 2 {F_{k-2}} - 3 {F_{k}} + 1) x^{2} - {F_{k}}^{2}=0$$

Just noticed that if one accepts negative Fibonacci numbers (as described on wikipedia) $F_{-n}=(-1)^{n+1} F_n$ there are some more small solutions.

Here are curves where $x$ corresponds to $F_{2n+1}$ on the first curve and $F_{2n}$ on the second curve.

1 (z^4 + x*z^2 - x^2 + 1, z^4 + x*z^2 - x^2 - 1)
2 (z^4 - x*z^2 - x^2 + 1, z^4 - x*z^2 - x^2 - 1)
3 (z^4 - 2*x*z^2 - 4*x^2 + 4, z^4 - 2*x*z^2 - 4*x^2 - 4)
4 (z^4 - 5*x*z^2 - 5*x^2 + 9, z^4 - 5*x*z^2 - 5*x^2 - 9)
5 (z^4 - 9*x*z^2 - 11*x^2 + 25, z^4 - 9*x*z^2 - 11*x^2 - 25)
6 (z^4 - 16*x*z^2 - 16*x^2 + 64, z^4 - 16*x*z^2 - 16*x^2 - 64)
7 (z^4 - 27*x*z^2 - 29*x^2 + 169, z^4 - 27*x*z^2 - 29*x^2 - 169)
8 (z^4 - 45*x*z^2 - 45*x^2 + 441, z^4 - 45*x*z^2 - 45*x^2 - 441)
9 (z^4 - 74*x*z^2 - 76*x^2 + 1156, z^4 - 74*x*z^2 - 76*x^2 - 1156)
10 (z^4 - 121*x*z^2 - 121*x^2 + 3025, z^4 - 121*x*z^2 - 121*x^2 - 3025)
11 (z^4 - 197*x*z^2 - 199*x^2 + 7921, z^4 - 197*x*z^2 - 199*x^2 - 7921)
12 (z^4 - 320*x*z^2 - 320*x^2 + 20736, z^4 - 320*x*z^2 - 320*x^2 - 20736)
13 (z^4 - 519*x*z^2 - 521*x^2 + 54289, z^4 - 519*x*z^2 - 521*x^2 - 54289)
14 (z^4 - 841*x*z^2 - 841*x^2 + 142129, z^4 - 841*x*z^2 - 841*x^2 - 142129)
15 (z^4 - 1362*x*z^2 - 1364*x^2 + 372100, z^4 - 1362*x*z^2 - 1364*x^2 - 372100)
16 (z^4 - 2205*x*z^2 - 2205*x^2 + 974169, z^4 - 2205*x*z^2 - 2205*x^2 - 974169)
17 (z^4 - 3569*x*z^2 - 3571*x^2 + 2550409, z^4 - 3569*x*z^2 - 3571*x^2 - 2550409)
18 (z^4 - 5776*x*z^2 - 5776*x^2 + 6677056, z^4 - 5776*x*z^2 - 5776*x^2 - 6677056)
19 (z^4 - 9347*x*z^2 - 9349*x^2 + 17480761, z^4 - 9347*x*z^2 - 9349*x^2 - 17480761)
20 (z^4 - 15125*x*z^2 - 15125*x^2 + 45765225, z^4 - 15125*x*z^2 - 15125*x^2 - 45765225)
21 (z^4 - 24474*x*z^2 - 24476*x^2 + 119814916, z^4 - 24474*x*z^2 - 24476*x^2 - 119814916)
22 (z^4 - 39601*x*z^2 - 39601*x^2 + 313679521, z^4 - 39601*x*z^2 - 39601*x^2 - 313679521)
23 (z^4 - 64077*x*z^2 - 64079*x^2 + 821223649, z^4 - 64077*x*z^2 - 64079*x^2 - 821223649)
24 (z^4 - 103680*x*z^2 - 103680*x^2 + 2149991424, z^4 - 103680*x*z^2 - 103680*x^2 - 2149991424)

Lack of integral points on both curves would mean no solution for the given gap.

-

You can definitely handle this kind of curves using Magma : magma.maths.usyd.edu.au/magma/handbook/text/… If you don't have access to Magma you can do limited computation at magma.maths.usyd.edu.au/calc – François Brunault Jan 4 2012 at 16:32
Treating $F_k,F_{k-2}$ as variables and using the curves described in the question appears to lead to a surface. – joro Jan 5 2012 at 13:37
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 174, "mathjax_display_tex": 6, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": false, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.8794791102409363, "perplexity_flag": "middle"}