# 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 $\displaystyle \frac{p_k}{q_k}$ is the kth convergent of $\displaystyle [a_0;a_1,...,a_n]$, show that for $\displaystyle 0 \leq k\leq n$, $\displaystyle q_k \geq 2^{\frac {k-1}{2}}$

I use that fact that
$\displaystyle q_k = a_kq_{k-1}+q_{k-2} \geq 2q_{k-2} \geq 2$, and
$\displaystyle 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 $\displaystyle q_k$ is decreasing in $\displaystyle 2n$ steps.

But why $\displaystyle q_k \geq 2^{\frac {k-1}{2}}$ instead of $\displaystyle 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 $\displaystyle q_1$. If $\displaystyle q_k\geq 2^{k/2}$ was true then $\displaystyle q_1\geq 2^{1/2} = \sqrt{2}$. But this is false because consider $\displaystyle [1;1,...]$ then $\displaystyle p_1/q_1 = 1 + \frac{1}{1} = \frac{2}{1}$.