Do best lower approximations of a quadratic irrational always form a linear recurrence sequence? Let $\theta$ be an irrational number and let 
$$
{\cal L}= \bigg\lbrace (a,b) \in {\mathbb Z} \times {\mathbb N}^{*} \bigg| \frac{a}{b} \leq \theta \bigg\rbrace
$$
and
$$
{\cal B}= \bigg\lbrace (a,b) \in {\cal L} \bigg| \forall (a',b') \in {\cal L}, \ b'\leq b \Rightarrow \frac{a'}{b'} \leq \frac{a}{b} \bigg\rbrace
$$
so that $\cal B$ corresponds to the best lower approximations of $\theta$. The elements of $\cal B$ can be arranged in an increasing sequence with increasing denominators,
$\frac{a_1}{b_1}<\frac{a_2}{b_2}<\frac{a_3}{b_3} < \ldots $ with
$b_1<b_2<b_3< \ldots $.
For example, when $\theta=\sqrt{5}$, the sequence is $\frac{2}{1}<\frac{11}{5}<\frac{20}{9}< \ldots $. The sequences $(a_n)$ and $(b_n)$ are linear recurrent sequences of degree $8$,
with characteristic polynomial $X^8-18X^4+1=(X^4-4X^2-1)(X^4+4X^2-1)$.
Note that contrary to what might be excepted, this degree 8 has nothing to do with the period of the standard continued fraction for $\theta$, which equals $1$ (we have
$\sqrt{5}=2+\frac{1}{\phi}$ with $\phi=4+\frac{1}{\phi}$) .
My question is, are the sequences $(a_n)$ and $(b_n)$ always evantually linear recurrent if $\theta$ is a quadratic irrational ? 
 A: I finally found a complete answer to my question. My sequence is not the same thing as the convergents of the standard continued fraction of $\theta$ ; indeed, many terms in my sequence are not convergents and many convergents are not in my sequence. However, the two sequences share near-identical properties as we are going to see.
For any $m\geq 1$, enote by $l_m$ ($u_m$, respectively) the largest (smallest) fraction with denominator $\leq m$ that is smaller (larger) than $\theta$. Thus the set 
$\lbrace l_m | m \geq 1\rbrace$ is the same thing as the set $\lbrace \frac{a_n}{b_n} | n \geq 1\rbrace$, and for every $n$ we have $\frac{a_n}{b_n}=l_{b_n}$. On the other side of $\theta$, $u_{b_n}$ can be written as a reduced fraction $\frac{c_n}{d_n}$. It is well-known that
$b_nc_n-a_nd_n=1$. To find the next term $\frac{a_{n+1}}{b_{n+1}}$, we use mediants : let $v_0=\frac{c_n}{d_n}$, and for $k \geq 1$ let $v_{k}$ be the mediant of $v_{k-1}$ and $\frac{a_n}{b_n}$. Then one has $v_k=\frac{c_n+ka_n}{d_n+kb_n}$ for all $k$, and there is a unique $k_n$ such that $v_{k_n} > \theta > v_{k_n+1}$. Then the next pair of near-values around $\theta$, $(\frac{a_{n+1}}{b_{n+1}},\frac{c_{n+1}}{d_{n+1}})$ is exactly $(v_{k_{n+1}},v_{k_n})$. We deduce the recurrence formulas
$$
a_{n+1}=c_n+(k_{n}+1)a_n \\
b_{n+1}=d_n+(k_{n}+1)b_n \\
c_{n+1}=c_n+k_{n}a_n \\
d_{n+1}=d_n+k_{n}b_n \\
$$
which can be rewritten more elegantly as a matrix equality : if we put
$$
K_n=
\left(
\begin{matrix}
k_n+1 & 1  \\
k_n & 1
\end{matrix}
\right),
M_n=
\left(
\begin{matrix}
a_{n} & b_{n}  \\
c_{n} & d_{n}
\end{matrix}
\right)
$$
then we have $M_{n+1}=K_nM_n$ for all $n\geq 1$. Also, $k_n$ can be written as $\lfloor \rho_n \rfloor$, where $\rho_n=\frac{c_n-d_n\theta}{b_n\theta-a_n}$.  If we put 
$$
\left(
\begin{matrix}
a & b  \\
c & d
\end{matrix}
\right)
\star x=\frac{cx-d}{bx-a},
$$
then this defines a group action of $GL_2({\mathbb Q})$ on $\mathbb Q$ : 
$A \star (B \star x)=(AB) \star x$ for any matrices $A,B$ and any $x\in {\mathbb Q}$. 
We deduce
$$
\rho_{n+1}=M_{n+1}\star\theta=K_nM_n \star \theta=K_n \star \rho_n
$$
In other words, the sequence $(\rho_n)$ satisfies the recurrence relation
$$
\rho_{n+1}=f(\rho_n), \ {\rm with} \ f(x)=\frac{x-\lfloor x \rfloor}{\lceil x\rceil-x}
$$
If $\theta$ is a quadratic irrational, it can be written in the familiar "Legendre" form
$\frac{p+\sqrt{D}}{q}$ where $p,q,D$ are integers with $D$ a nonsquare, and $q$ divides
$D-p^2$. Then, by induction, each $\rho_n$ is again of the form
$\frac{p_n+\sqrt{D}}{q_n}$ where $p_n$ and $q_n$ are integers and  $q_n$ divides
$D-p_n^2$. So $r_n=\frac{D-p_n^2}{q_n}$ is an integer, and we have
$|q_nr_n| \leq |D|$, $|q_n| \leq D, |r_n| \leq |D|, |p_n^2| \leq |D|+|q_nr_n| \leq |D|+|D|^2$. So there are only finitely many possible values for the pair $(p,q)$, so the sequence $(\rho_n)$
takes its values in a finite set. Since it also satisfies $\rho_{n+1}=f(\rho_n)$, it is eventually periodic.  Then $(k_n)$ is also eventually periodic, and it is easily deduced that the vector $(a_n,b_n,c_n,d_n)$ satisfies a linear recurrence relation (for more details see the article linked by Aryabhata in the comments).
