K-th convergents of continued fraction

[evinda]

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)

 

[I like Serena]

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]

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)

 

[I like Serena]

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]

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)

 

[I like Serena]

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]

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.