To which $\alpha\in\mathbb{R}$ can $\frac{p}{q}$ be a convergent of its (alpha's) continued fractions?

Question

I read that for any to consecutive convergents of a number $\alpha$, at least one of them must be distance at most $\frac{1}{2q^2}$ from $\alpha$. I don't see how this helps me into determining in what interval $\alpha$ can lie when you know $\frac{p}{q}$ is a convergent of its continued fractions. I would say that $\alpha$ is in $\left(\frac{p}{q}-\frac{1}{2q^2},\frac{p}{q}+\frac{1}{2q^2}\right)$, but I'm not sure and I don't see whether I can used the mentioned theorem for this. Any suggestions?

To state the problem a bit more clear: given $\frac{p}{q}=[a_0,\ldots,a_n]$, to what $[a_0,\ldots,a_n,a_{n+1},\ldots]=\alpha\in\mathbb{R}$ can this fraction be a convergent of its continued fraction? I would say that these $\alpha$ lie in some interval.

Answer 1

EDIT: This answer is incorrect, but since it has been accepted, I can't delete it. See the answer by @dennis.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

I think I understand the question now, and the answer is this:

Let $p_n/q_n=[a_0;a_1,\dots,a_n]$, and let $p_{n-1}/q_{n-1}=[a_0;a_1,\dots,a_{n-1}]$. Then $p_n/q_n$ is a convergent to the continued fraction of $\alpha$ if and only if $\alpha$ is between $p_n/q_n$ and ${p_n\over q_n}+{(-1)^n\over q_n(q_n+q_{n-1})}$. Note that $\alpha$ must be bigger than $p_n/q_n$ if $n$ is even, and smaller if $n$ is odd. Note also that $q_n(q_n+q_{n-1})$ is between $q_n^2$ and $2q_n^2$, but exactly where in between depends on $q_{n-1}$.

Answer 2

(The previous answer only gave one of the two bounds correctly, the other bound was the fraction itself. Here is a corrected version:)

Let $$ \frac{p_n}{q_n} = [a_0; a_1, \ldots, a_{n-1}, a_n] \\ \frac{p_{n-1}}{q_{n-1}} = [a_0; a_1, \ldots, a_{n-1}]\:\qquad \\ $$ Then $\frac{p_n}{q_n}$ is a convergent of a real number $\alpha\in\mathbb R$ if and only if $$ \alpha\text{ is strictly between }\frac{p_n+p_{n-1}}{q_n+q_{n-1}}\text{ and }\frac{2p_n-p_{n-1}}{2q_n-q_{n-1}} \tag{1}\label{bounds} $$

Proof: Note that $$ \frac{p_n}{q_n} = [a_0; a_1, \ldots, a_n] = [a_0; a_1, \ldots, a_n-1, 1] $$ so we can assume $a_n>1$ w.l.o.g. For the first bound, note that any $\alpha = [a_0; a_1, \ldots, a_n, \beta]$ will have $a_0; a_1, \ldots, a_n$ as its first quotients (and thus $\frac{p_n}{q_n}$ as its $n^{\text{th}}$ convergent) as long as $\beta > 1$. As $\beta$ grows to $\infty$, we will approach $\frac{p_n}{q_n}$, so the furthest we can get away from $\frac{p_n}{q_n}$ is with $\beta=1$. Here, $$ \lim_{\beta\searrow1}[a_0; a_1, \ldots, a_n, \beta] = [a_0; a_1, \ldots, a_n, 1] = \frac{p_n+p_{n-1}}{q_n+q_{n-1}} \tag{2}\label{bound1} $$ is the first number that will not have $\frac{p_n}{q_n}$ as convergent anymore, because $[a_0; a_1, \ldots, a_n, 1] = [a_0; a_1, \ldots, a_n+1]$ has a different list of first quotients (this is the bound that was correct in the previous answer).

For the other bound, we have to go in the other direction, which we do by starting from $\frac{p_n}{q_n}=[a_0; a_1, \ldots, a_n-1, 1]$. Here, any $\alpha = [a_0; a_1, \ldots, a_n-1, 1, \beta]$ will have $a_0; a_1, \ldots, a_n-1, 1$ as its first quotients (and thus $\frac{p_n}{q_n}$ as its $(n+1)^{\text{th}}$ convergent!) as long as $\beta>1$. As $\beta$ grows to $\infty$, we will approach $\frac{p_n}{q_n}$, so the furthest we can get away from $\frac{p_n}{q_n}$ is with $\beta=1$. Here, $$ \lim_{\beta\searrow1}[a_0; a_1, \ldots, a_n-1, 1, \beta]=[a_0; a_1, \ldots, a_n-1, 1, 1] = [a_0; a_1, \ldots, a_n-1, 2] = \frac{2p_n-p_{n-1}}{2q_n-q_{n-1}} \tag{3}\label{bound2} $$ is the first number that will not have $\frac{p_n}{q_n}$ as convergent anymore (this is the bound that was wrong in the previous answer, because it only considered numbers $\alpha$ that have $\frac{p_n}{q_n}$ as their $n^{\text{th}}$ convergent and not those that have $\frac{p_n}{q_n}$ as their $(n+1)^{\text{th}}$ convergent towards the bound in the other direction).

Example: We try to find all $\alpha\in\mathbb R$ that have $$ \frac{4}{9} = 0+\frac1{2+\frac1 4} = [0;2,4] = [0;2,3,1] \tag{4}\label{example} $$ as convergent. Computing the above bounds and a few numbers in between:

Number	Continued fraction	List of convergents	Eq.
$\frac{7}{16}=0.4375$	$[0; 2, 3, 2]$	$0, \frac1 2, \frac3 7, \frac7 {16}$	\eqref{bound2}
$\frac{11}{25}=0.44$	$[0; 2, 3, 1, 2]$	$0, \frac1 2, \frac3 7, \frac4 9, \frac{11}{25}$
$\frac{15}{34}=0.44176...$	$[0; 2, 3, 1, 3]$	$0, \frac1 2, \frac3 7, \frac4 9, \frac{15}{34}$
$\frac{4}{9}=0.44444...$	$[0; 2, 4]$	$0, \frac1 2, \frac4 9$	\eqref{example}
$\frac{9}{20}=0.45$	$[0; 2, 4, 2]$	$0, \frac1 2, \frac4 9, \frac9 {20}$
$\frac{5}{11}=0.45454...$	$[0; 2, 5]$	$0, \frac1 2, \frac5 {11}$	\eqref{bound1}

The first line is the exclusive (lower) bound \eqref{bound2}, and the last line is the exclusive (upper) bound \eqref{bound1}. All $\alpha\in(\frac 7 {16},\frac 5 {11})$ will have $\frac 4 9$ as convergent. Note that it can either be the second or the third convergent.

Remarks:

1. If $n$ is even, the first bound in \eqref{bounds} will be an upper bound and the second will be a lower bound. If $n$ is odd, this is reversed.
2. This statement can also be found on Wikipedia, although in a slightly different representation (at the time this answer was written) where $a_n$ is defined as $a_k+1$.

Answer 3

An equivalent but more compact statement is given is Theorem 2 of https://hal.archives-ouvertes.fr/hal-02272389 (paper written in french).

Let $p$ and $q \ge 2$ be two relatively prime integers. Call $(u,v)$ the unique solution of the Bezout equation $up-vq=1$, with $0 \le u \le q-1$ (then $u \ge 1$). Let $\theta \in \mathbb{R}$. Then:

$\bullet$ $p/q$ is a convergent or a semi-convergent of $\theta$ if an only if $\frac{v}{u} < \theta < \frac{p-v}{q-u}$.

$\bullet$ $p/q$ is a convergent of $\theta$ if an only if $\frac{p+v}{q+u} < \theta < \frac{2p-v}{2q-u}$.

For example, if $p=3$ and $q=10$, then $u=7$ and $v=2$. Hence:

$\bullet$ $3/10$ is a convergent or a semi-convergent of $\theta$ if an only if $2/7 < \theta < 1/3$.

$\bullet$ $3/10$ is a convergent of $\theta$ if an only if $5/17 < \theta < 4/13$.

Remark: when $p>0$, the fractions $v/u$ and $(p-v)/(q-u)$ are the two fractions providing the fraction $p/q$ in the Stern-Brocot tree. And the fractions $(p+v)/(q+u)$ and $(2p-v)/(2q-u)$ are the two chidren of the fraction $p/q$ in the Stern-Brocot tree.

https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree