# Need help on continued farction

• May 12th 2008, 05:04 PM
kleenex
Need help on continued farction
I'm trying to show the following argument but have a problem

If $\frac{p_k}{q_k}$ is the kth convergent of $[a_0;a_1,...,a_n]$, show that for $0 \leq k\leq n$, $q_k \geq 2^{\frac {k-1}{2}}$

I use that fact that
$q_k = a_kq_{k-1}+q_{k-2} \geq 2q_{k-2} \geq 2$, and
$2q_{k-2} = a_{k-2}q_{k-3}+q_{k-4} \geq 2^2q_{k-4} \geq 2^2$ etc,
we can see that $q_k$ is decreasing in $2n$ steps.

But why $q_k \geq 2^{\frac {k-1}{2}}$ instead of $2^{\frac{k}{2}}$?

Can anyone explain it to me? Thank you.
• May 12th 2008, 06:41 PM
ThePerfectHacker
This comes down to the inductive case $q_1$. If $q_k\geq 2^{k/2}$ was true then $q_1\geq 2^{1/2} = \sqrt{2}$. But this is false because consider $[1;1,...]$ then $p_1/q_1 = 1 + \frac{1}{1} = \frac{2}{1}$.