MHB K-th convergents of continued fraction

  • Thread starter Thread starter evinda
  • Start date Start date
  • Tags Tags
    Fraction
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