Interesting continued fraction problem $|r_i-u_0/u_1|\le\frac1{k_ik_{i+1}}$

46 Views Asked by At

Let $u_0/u_1$ be a rational number in lowest terms, and write $u_0/u_1=\langle a_0, a_1,...,a_n\rangle$ in standard continued fraction notation. Show that if $0\le i<n$, then $|r_i-u_0/u_1|\le\frac1{k_ik_{i+1}}$ with equality iff $i=n-1$.


Here we have $h_{-2}=0,h_{-1}=1,h_i=a_ih_{i-1}+h_{i-2}$ for $i\ge 0$.

$k_{-2}=1,k_{-1}=0$, $k_i=a_ik_{i-1}+k_{i-2}$ for $i\ge 0$.

And $r_i=\frac{h_i}{k_i}$ for all integers $i\ge0$.

In fact, we have $\langle a_0,a_1,...,a_{n-1},x\rangle=\frac{xh_{n-1}+h_{n-2}}{xk_{n-1}+k_{n-2}}$. We can prove this via induction. The base cases are obvious. Using this fact, we see that $r_i=\langle a_0,a_1,...,a_i\rangle$ for all integer $i\ge0$.

1

There are 1 best solutions below

0
On

From the little book by Khinchin, theorems 9 and 13, if the target number is $x,$ which in your case is $x= u_0/u_1,$ then $$ \frac{1}{k_i \, (k_i + k_{i+1})} < \left| x - \frac{h_i}{k_i}\right| < \frac{1}{k_i \, k_{i+1}}. $$ This was written for irrational $x$ but applies, of course, for rational $x$ by switching to $\leq$ signs and stopping before the final step.