# Number TheoryK-th convergents of continued fraction

#### evinda

##### Well-known member
MHB Site Helper
Hello!!!

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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
Hello!!!

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?
Hey evinda !!

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?

#### evinda

##### Well-known member
MHB Site Helper
Hey evinda !!

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?
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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.

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

#### evinda

##### Well-known member
MHB Site Helper
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.

We have that $a_i \ge 1$ for $i>0$ don't we? [
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?

#### Klaas van Aarsen

##### MHB Seeker
Staff member
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$.
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$ ?

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}$ ?

#### DavidCampen

##### Member
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.