MHB K-th convergents of continued fraction

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Fraction
AI Thread Summary
The discussion centers on proving that the denominator \( q_k \) of the \( k \)-th convergent of a continued fraction satisfies the inequality \( q_k \geq 2^{\frac{k-1}{2}} \) for \( 1 \leq k \leq n \). Participants suggest using recursive relations for convergents and consider proving the statement by induction. The base case involves calculating \( k_0 \) and \( k_1 \), with the assumption that \( a_i \geq 1 \) for \( i > 0 \). The conversation also references a theorem from Khinchin's work on continued fractions, indicating that established inequalities may aid in the proof. The discussion emphasizes the need for clarity in the induction hypothesis and the conditions for the base case.
evinda
Gold Member
MHB
Messages
3,741
Reaction score
0
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)
 
Mathematics news on Phys.org
evinda said:
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)
 
Klaas van Aarsen said:
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)
 
evinda said:
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)

evinda said:
But can we get somehow an inequality for the latter?

We have that $a_i \ge 1$ for $i>0$ don't we? (Wondering)
 
Klaas van Aarsen said:
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)
 
evinda said:
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)

evinda said:
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)

evinda said:
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)
 
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.
 

Similar threads

Back
Top