# Show that $\{p/q:|\frac{\sqrt5+1}{2}-p/q|<\frac{1}{\sqrt{5}q^2}\}=\{\frac{F_{2n+1}}{F_{2n}}:n\in\mathbb N\}$

Show that $\{p/q:|\frac{\sqrt5+1}{2}-p/q|<\frac{1}{\sqrt{5}q^2}\}=\{\frac{F_{2n+1}}{F_{2n}}:n\in\mathbb N\}$, where $F_n$ is the $n$-th Fibonacci number

$2$ things to show

$1$st, $\frac{F_{2n+1}}{F_{2n}}$ satisfies the inequation

My question: Is the Farey sequence defined only between $0$ and $1$, otherwise I can use this,

$2$nd; there's no other solution, this is a bit difficult

• A Farey sequence $S$ can be extended to all of $Q.$ Let $S'=\{s+z: s\in S, \;z\in Z\}$. For the purposes of this Q ,the useful properties of $S$ still hold for $S'$. – DanielWainfleet Mar 8 '16 at 3:57
• Please see my comment to my A before reading my A. – DanielWainfleet Mar 8 '16 at 6:58
• Farey series are useful in proving that for any irrational real $x,$ there are infinitely many $(p,q)\in Z^2$ such that $|x-p/q|<1/q^2\sqrt 5.$ The Golden Ratio $g=(1+\sqrt 5)/2$ is the "worst case", in the sense that if $k>\sqrt 5,$ then there are only finitely many $(p,q)$ with $|g-p/q|<1/q^2k.$ – DanielWainfleet Mar 8 '16 at 22:08

Notation : $p$ and $q$ are any positive integers.

1. If $|p^2-p q-q^2|=1$ then $p=F_{n+1}$ and $q=F_n$ for some $n\in N.$ Proof:

(i). $p-q\leq q$ because $p\geq 2 q+1\to q\leq (p-1)/2 \to 1\geq p^2- p q -q^2\geq p^2-p(p-1)/2-((p-1)/2)^2=(p^2-1)/4\to p^2\leq 5,$ but $p\geq 2 q+1\geq 3.$

(ii). Let $r_1=p,\; r_2=q,$ and let $\bullet$ $r_{j+1}=r_{j-1}-r_j.$ We have $|r_j^2-r_j r_{j+1}-r_{j+1}^2|=1$ by induction on $j.$ By (i), if $r_j>r_{j+1}>0$ then $r_{j+1}>r_{j+2}>0.$ So for some $j$ we have $r_j=r_{j+1}>0,$ otherwise $(r_j)_{j\in N}$ is a strictly descending infinite sequence in $N.$

(iii) $r_j=r_{j+1}>0\to 1=|r_j^2-r_j r_{j+1}=r_{j+1}^2|=r_j^2\to$ $r_j=r_{j+1}=1$ $\to [r_j=F_2\land r_{j+1}=F_1].$

Working back up to q, p by $\bullet$ we have $q=F_k$ and $p=F_{k+1}$.

1. We have $|p^2-p q-q^2|\geq 1$ because $p^2-p q-q^2=0\to$ $(p/q)^2-(p/q)-1=0\to p/q\in \{(1+\sqrt 5)/2, (1-\sqrt 5)/2\}.$

3.Let $g=(1+\sqrt 5)/2.$ Let $H(x)=x^2-x-1$ for $x\in R.$ Let $d=p/q-g.$

We have $1\leq |p^2-p q-q^2|=q^2|H(p/q)|=$ $q^2|H(g)+H'(g)d +H''(g)d^2/2|=$ $q^2|d\sqrt 5+d^2|.$

Now $|d|<1/q^2\sqrt 5\to |p^2- p q -q^2|=1$ because otherwise $2/q^2\leq |p^2-p q-q^2|/q^2=|H(p/q)|=|d\sqrt 5 +d^2|\leq |d|\sqrt 5 +d^2<$ $1/q^2+d^2 \implies 2/q^2<1/q^2+d^2$ $\implies 1/q<|d|<1/q^2\sqrt 5$ $\implies q^2\sqrt 5<q.$

4 . So $|(\sqrt 5+1)/2-p/q|\geq 1/q^2\sqrt 5$ if $p,q$ are not consecutive Fibonacci numbers with $p\geq q.$

1. With $d_n=F_{n+1}/F_n-g$ we have $H(F_{n+1}/F_n)=d_n\sqrt 5+d_n^2.$ By induction on $n$ we have $H(F_{n+1}/F_n)=(-1)^n/F_n^2.$ The rest is up to you.
• For reasons unknown I cannot edit Section 1.(i) . The word "but" should appear only after " $p^2\leq 5$ " . – DanielWainfleet Mar 8 '16 at 6:34