Welcome to our community

Be a part of something great, join today!

Number Theory K-th convergents of continued fraction

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,829
Hello!!! (Wave)

I want to show that if $c_k=\frac{p_k}{q_k}$ the $k$-th convergents of the continued fraction $[a_0; a_1, a_2, \dots, a_n]$, then $q_k \geq 2^{\frac{k-1}{2}} (1 \leq k \leq n)$.

Could you give me a hint how we could show this? (Thinking)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,265
Hello!!! (Wave)

I want to show that if $c_k=\frac{p_k}{q_k}$ the $k$-th convergents of the continued fraction $[a_0; a_1, a_2, \dots, a_n]$, then $q_k \geq 2^{\frac{k-1}{2}} (1 \leq k \leq n)$.

Could you give me a hint how we could show this? (Thinking)
Hey evinda !! (Smile)

Wiki says:
For a continued fraction $[a_0;a_1,a_2,a_3,...]$, the first four convergents (numbered 0 through 3) are
$$\frac{a_0}{1}, \frac{a_1 a_0 + 1}{a_1}, ...$$

If successive convergents are found, with numerators $h_1, h_2, …$ and denominators $k_1, k_2, …$ then the relevant recursive relation is:
$$h_n = a_nh_{n − 1} + h_{n − 2},\\
k_n = a_nk_{n − 1} + k_{n − 2}.$$

Can we use that?
If so, can we prove it by induction? (Wondering)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,829
Hey evinda !! (Smile)

Wiki says:
For a continued fraction $[a_0;a_1,a_2,a_3,...]$, the first four convergents (numbered 0 through 3) are
$$\frac{a_0}{1}, \frac{a_1 a_0 + 1}{a_1}, ...$$

If successive convergents are found, with numerators $h_1, h_2, …$ and denominators $k_1, k_2, …$ then the relevant recursive relation is:
$$h_n = a_nh_{n − 1} + h_{n − 2},\\
k_n = a_nk_{n − 1} + k_{n − 2}.$$

Can we use that?
If so, can we prove it by induction? (Wondering)
If we use this, then at the base case, do we pick $n=2$ ?

If so, then we have $k_2=a_2 k_1+k_0$.

But can we get somehow an inequality for the latter? (Thinking)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,265
If we use this, then at the base case, do we pick $n=2$ ?

If so, then we have $k_2=a_2 k_1+k_0$.
In the base case we should calculate $k_0$, and $k_1$.
Then in the induction hypothesis we assume it is true up to $n\ge 1$.
And in the induction step we have to prove it for $n+1$ for which we can now use that formula. (Thinking)

But can we get somehow an inequality for the latter?
We have that $a_i \ge 1$ for $i>0$ don't we? (Wondering)
 

evinda

Well-known member
MHB Site Helper
Apr 13, 2013
3,829
In the base case we should calculate $k_0$, and $k_1$.
Then in the induction hypothesis we assume it is true up to $n\ge 1$.
And in the induction step we have to prove it for $n+1$ for which we can now use that formula. (Thinking)

We have that $a_i \ge 1$ for $i>0$ don't we? (Wondering)[
We have that $k_0=1 \geq 2^{-\frac{1}{2}}=\frac{1}{\sqrt{2}}$ and $k_1=a_1$.

Why does it hold that $a_i \ge 1$ for $i>0$?


At the induction hypothesis we assume that $k_j \geq 2^{\frac{j-1}{2}}, \forall 1 \leq j \leq n$, or not?

Then, $k_{n+1}=a_n k_n+k_{n-1} \geq 1 \cdot 2^{\frac{n-1}{2}}+2^{\frac{n-2}{2}}=2^{\frac{n-2}{2}} (\sqrt{2}+1) \geq 1$. Right? (Thinking)
 

Klaas van Aarsen

MHB Seeker
Staff member
Mar 5, 2012
9,265
We have that $k_0=1 \geq 2^{-\frac{1}{2}}=\frac{1}{\sqrt{2}}$ and $k_1=a_1$.

Why does it hold that $a_i \ge 1$ for $i>0$?
Because:
  • It says so in wiki:
    In either case, all integers in the sequence, other than the first, must be positive.
  • If $a_n$ would be $0$, we'd be dividing by $0$.
  • If we pick $a_2=0$, we get $q_2=0\cdot a_1 + 1=1 \not\ge 2^{\frac{2-1}{2}}=\sqrt 2$. (Worried)
At the induction hypothesis we assume that $k_j \geq 2^{\frac{j-1}{2}}, \forall 1 \leq j \leq n$, or not?
Shouldn't that be $\forall 0 \leq j \leq n$ ? (Wondering)

Then, $k_{n+1}=a_n k_n+k_{n-1} \geq 1 \cdot 2^{\frac{n-1}{2}}+2^{\frac{n-2}{2}}=2^{\frac{n-2}{2}} (\sqrt{2}+1) \geq 1$. Right?
Don't we need to prove that $k_{n+1} \ge 2^{\frac n 2}$ ? (Thinking)
 

DavidCampen

Member
Apr 4, 2014
66
This is Theorem 12 in "Continued Fractions" by A. Ya. Khinchin (Dover publications). The proof uses repeated application of an inequality derived from Theorem 1 of the same book. If I can figure out how to use the Latex code I will post them.