Let $(F_n)$ be the sequence defined recursively by $F_1=F_2=1$ and $F_{n+1}=F_n+F_{n-1}$ for $n\geq 2$. Find all pairs of positive integers $(x,y)$ such that $$5F_x-3F_y=1.$$
Problem
Source: 2019 Baltic Way P2
Tags: algebra
GeoMetrix
18.11.2019 15:07
Really nice . This lemma killed it.
2019 Baltic Way P2 wrote:
Let $(F_n)$ be the sequence defined recursively by $F_1=F_2=1$ and $F_{n+1}=F_n+F_{n-1}$ for $n\geq 2$. Find all pairs of positive integers $(x,y)$ such that
$$5F_x-3F_y=1.$$
Solution: Firstly we state a crucial lemma
Lemma: $F_{x+t}=F_{t+1}F_{x}+F_{t}F_{x-1}$
Proof: Trivial by induction.
Now back to the main problem. Clearly by solving this diophantine we have $F_x=3q+2$ and $F_y=5q+3$ for some positive integer $q \implies F_y>F_x$. Assume $y=x+m$ for some $m$. Clearly we have by using our lemma $5q+3=F_{x+m}=F_{m+1}F_x+F_mF_{x-1}=F_{m+1}(3q+2)+F_mF_{x-1} \implies F_{m+1}<2 \implies m \leq 2$ . Now just form cases to obtain the solutions as $(2,3);(5,8);(8,13)$or $(x,y)=(3,4),(5,6),(6,7)$ $\blacksquare$.
grupyorum
18.11.2019 20:29
You don't need this lemma. I'll prove by hand that $y\leqslant 7$ as follows. Suppose $y>7$. Note that, clearly $x<y$. Now I claim $x=y-1$. Suppose that $x\leqslant y-2$. Then, $F_y\geqslant F_{x+2}=F_{x+1}+F_x\geqslant 2F_x$. In particular, $5F_x-3F_y\leqslant 2.5F_y-3F_y = -\frac12 F_y<0$, a contradiction. Now, we have $x=y-1$. We then have $$ 1=5F_{y-1}-3(F_{y-1}+F_{y-2})=2F_{y-1}-3F_{y-2}=2F_{y-3}-F_{y-2} =F_{y-3}-F_{y-4}=F_{y-5}. $$Hence, $F_{y-5}=1$, and thus, $y-5\leqslant 2$. The rest is easy.
achen29
18.11.2019 23:07
$F_y = \frac{5F_x-1}{3}$ Another bounding idea that one may consider is the fact that $1.67 \approx 5/3 > \phi\approx1.61$ and so by considering the golden ratio of consecutive terms of the Fibonacci sequence one may prove (albeit very mechanically lol) that the terms must be consecutive, and using the same idea, bound $y<7$ or something similar.