Prove that for $n\ge1$, $\xi-\frac{h_n}{k_n}=(-1)^nk_n^{-2}\left(\xi_{n+1}+\langle 0,a_n,a_{n-1},...,a_2,a_1\rangle\right)^{-1}$

178 Views Asked by At

Prove that for $n\ge1$, $$\xi-\frac{h_n}{k_n}=(-1)^nk_n^{-2}\left(\xi_{n+1}+\langle 0,a_n,a_{n-1},...,a_2,a_1\rangle\right)^{-1}$$

In addition, show that $$k_n|k_{n-1}\xi-h_{n-1}|+k_{n-1}|k_n\xi-h_n|=1$$


Here, $\frac{h_n}{k_n}$ is the $n$th convergent in the continued fraction expansion of $\xi$, and $a_i$ and $\xi_i$ are defined as follow:

Let $\xi_0=\xi$ and $a_i=\lfloor{\xi_i}\rfloor$, with $\xi_{i+1} = \frac1{\xi_i-a_i}$ for $i\ge0$

Also $\xi$ is assumed to be irrational. I think it's true that $$\xi_n=\langle a_n,a_{n+1},...,\rangle$$

1

There are 1 best solutions below

1
On BEST ANSWER

This follows from standard properties of convergents/continued fractions, and a fair bit of induction sprinkled throughout. We start by proving some standard properties of convergents/continued fractions; you may wish to skip straight to the main proof below.


Lemma 1: $$\xi=<a_0, a_1, \ldots , a_{n-1}, \xi_n>$$

Proof: We proceed by induction.

When $n=0$, clearly $\xi=<\xi>=<\xi_0>$.

Suppose that the statement holds for $n=m$, then

\begin{align} \xi=<a_0, a_1, \ldots , a_{m-1}, \xi_m>& =<a_0, a_1, \ldots , a_{m-1}, a_m+\frac{1}{\xi_{m+1}}> \\ &=<a_0, a_1, \ldots , a_m, \xi_{m+1}> \end{align}

We are thus done by induction.


Define $h'_n, k'_n$ using the following recurrence:

$$h'_{-2}=0, h'_{-1}=1, h'_n=a_nh'_{n-1}+h'_{n-2}$$ $$k'_{-2}=1, k'_{-1}=0, k'_n=a_nk'_{n-1}+k'_{n-2}$$

Lemma 2: $$k'_nh'_{n-1}-h'_nk'_{n-1}=(-1)^n$$.

Proof: We proceed by induction.

When $n=-1$ we have $k'_{-2}h'_{-1}-h'_{-1}k'_{-2}=-1=(-1)^{-1}$.

Suppose that the statement holds for $n=m$, i.e.

$$k'_mh'_{m-1}-h'_mk'_{m-1}=(-1)^m$$

Then

\begin{align} k'_{m+1}h'_m-h'_{m+1}k'_m& =(a_{m+1}k'_m+k'_{m-1})h'_m-(a_{m+1}h'_m+h'_{m-1})k'_m \\ &=-(k'_mh'_{m-1}-h'_mk'_{m-1}) \\ & =(-1)^{m+1} \end{align}

We are thus done by induction.


Lemma 3: For any $x$, we have $$<a_0, a_1, \ldots , a_{n-1}, x>=\frac{xh'_{n-1}+h'_{n-2}}{xk'_{n-1}+k'_{n-2}}$$

Proof: We proceed by induction.

When $n=1$, $$<a_0, x>=a_0+\frac{1}{x}=\frac{xa_0+1}{x}=\frac{xh'_{0}+h'_{-1}}{xk'_{0}+k'_{-1}}$$

so indeed the statement holds.

Suppose that the statement holds for $n=m$, i.e.

$$<a_0, a_1, \ldots , a_{m-1}, x>=\frac{xh'_{m-1}+h'_{m-2}}{xk'_{m-1}+k'_{m-2}}$$

Now we have

\begin{align} <a_0, a_1, \ldots , a_m, x>& =<a_0, a_1, \ldots , a_{m-1}, <a_m, x>>\\ & =\frac{<a_m, x>h'_{m-1}+h'_{m-2}}{<a_m, x>k'_{m-1}+k'_{m-2}} \\ & =\frac{(a_m+\frac{1}{x})h'_{m-1}+h'_{m-2}}{(a_m+\frac{1}{x})k'_{m-1}+k'_{m-2}} \\ & =\frac{x(a_mh'_{m-1}+h'_{m-2})+h'_{m-1}}{x(a_mk'_{m-1}+k'_{m-2})+k'_{m-1}} \\ &=\frac{xh'_m+h'_{m-1}}{xk'_m+k'_{m-1}} \end{align}

We are thus done by induction.


Theorem: The convergents $\frac{h_n}{k_n}$ satisfy the following properties:

\begin{align} (1) & h_n=a_nh_{n-1}+h_{n-2}, k_n=a_nk_{n-1}+k_{n-2}\\ (2) & k_nh_{n-1}-h_nk_{n-1}=(-1)^n \\ (3) & <a_0, a_1, \ldots , a_{n-1}, x>=\frac{xh_{n-1}+h_{n-2}}{xk_{n-1}+k_{n-2}} \\ (4) & sgn(\xi-\frac{h_n}{k_n})=(-1)^n \, \text{if} \, \xi \not =\frac{h_n}{k_n} \end{align}

Proof: As a consequence of Lemma $3$, we have $$\frac{h_n}{k_n}=<a_0, a_1, \ldots , a_{n-1}, a_n>=\frac{a_nh'_{n-1}+h'_{n-2}}{a_nk'_{n-1}+k'_{n-2}}=\frac{h'_n}{k'_n}$$

From Lemma $2$, we see that $(h'_n, k'_n)=1$, so we get $h_n=h'_n, k_n=k'_n$. Therefore $h_n, k_n$ satisfy the recurrence described above and the analogues of Lemma $2$ and $3$ hold with $h'_n, k'_n$ replaced by $h_n, k_n$ respectively. $(1), (2), (3)$ are thus proven.

To prove $(4)$, note that by Lemma $1$, and properties $(2), (3)$ proved above, we have

\begin{align} \xi-\frac{h_n}{k_n}& =<a_0, a_1, \ldots, a_{n-1}, \xi_n>-<a_0, a_1, \ldots , a_{n-1}, a_n> \\ & =\frac{\xi_nh_{n-1}+h_{n-2}}{\xi_nk_{n-1}+k_{n-2}}-\frac{a_nh_{n-1}+h_{n-2}}{a_nk_{n-1}+k_{n-2}} \\ & =\frac{(\xi_n-a_n)(h_{n-1}k_{n-2}-k_{n-1}h_{n-2})}{(\xi_nk_{n-1}+k_{n-2})(a_nk_{n-1}+k_{n-2})} \\ & =\frac{(\xi_n-a_n)(-1)^n}{(\xi_nk_{n-1}+k_{n-2})(a_nk_{n-1}+k_{n-2})} \end{align}

$(4)$ follows since $(\xi_nk_{n-1}+k_{n-2})(a_nk_{n-1}+k_{n-2})$ is clearly positive, $\xi_n-a_n=\xi_n-\lfloor \xi_n \rfloor \geq 0$ and $\xi_n \not =a_n$.


Well, that sets the stage for proving the results you want to prove. The above are all standard results in the theory of continued fractions.

Main proof:

In fact, we immediately have by property $(2)$ and $(4)$

\begin{align} k_n|k_{n-1}\xi-h_{n-1}|+k_{n-1}|k_n\xi-h_n|& =k_n(-1)^{n-1}(k_{n-1}\xi-h_{n-1})+k_{n-1}(-1)^n(k_n\xi-h_n) \\ & =(-1)^n(k_nh_{n-1}-k_{n-1}h_n) \\ & =(-1)^n(-1)^n \\ & =1 \end{align}


For the first equation, we first note that

$$\xi=<a_0, a_1, \ldots , \xi_n>=\frac{\xi_n h_{n-1}+h_{n-2}}{\xi_n k_{n-1}+k_{n-2}}$$

Cross multiplying and rearranging gives

$$\xi_n=-\frac{\xi k_{n-2}-h_{n-2}}{\xi k_{n-1}-h_{n-1}}$$

Now we do some rearranging of the desired identity:

\begin{align} &\xi-\frac{h_n}{k_n}=(-1)^nk_n^{-2}(\xi_{n+1}+<0, a_n, \ldots , a_1>)^{-1} \\ &\Leftrightarrow k_n(\xi k_n-h_n)(\xi_{n+1}+<0, a_n, \ldots , a_1>)=(-1)^n \\ &\Leftrightarrow k_n(\xi k_n-h_n)(-\frac{\xi k_{n-1}-h_{n-1}}{\xi k_n-h_n}+<0, a_n, \ldots , a_1>)=(-1)^n \\ &\Leftrightarrow k_n(\xi k_n-h_n)<0, a_n, \ldots , a_1>=(-1)^n+k_n(\xi k_{n-1}-h_{n-1}) \\ &\Leftrightarrow k_n(\xi k_n-h_n)<0, a_n, \ldots , a_1>=(k_nh_{n-1}-h_nk_{n-1})+k_n(\xi k_{n-1}-h_{n-1}) \\ &\Leftrightarrow k_n(\xi k_n-h_n)<0, a_n, \ldots , a_1>=\xi k_nk_{n-1}-h_nk_{n-1} \\ &\Leftrightarrow <0, a_n, \ldots , a_1>=\frac{k_{n-1}}{k_n} \\ &\Leftrightarrow <a_n, \ldots , a_1>=\frac{k_n}{k_{n-1}} \end{align}

It is now fairly straightforward to prove by induction on $n$ that $<a_n, \ldots , a_1>=\frac{k_n}{k_{n-1}}$.

When $n=1$, we clearly have $<a_1>=\frac{a_1}{1}=\frac{k_1}{k_0}$.

Suppose that the statement holds for $n=m$, i.e.

$$<a_m, \ldots , a_1>=\frac{k_m}{k_{m-1}}$$

Now

\begin{align} <a_{m+1},a_m, \ldots , a_1>=a_{m+1}+\frac{1}{<a_m, \ldots , a_1>}& =a_{m+1}+\frac{k_{m-1}}{k_m} \\ & =\frac{a_{m+1}k_m+k_{m-1}}{k_m} \\ &=\frac{k_{m+1}}{k_m} \end{align}

We are thus done by induction.