# How to prove continued fraction convergents of a number

Let $x=1+\sqrt{3}$. Prove that in pairs the continued fraction convergents of $x$ are $a_n$/$b_n$ < x < $c_n$/$d_n$ where $a_1$ = 2, $b_1$ = 1, $c_1$ = 3, $d_1$ = 1, $a_{n+1}$ = 2$c_n$ + $a_n$, $b_{n+1}$ = 2$d_n$ + $b_n$, $c_{n+1}$ = 3$c_n$ + $a_n$, $d_{n+1}$ = 3$d_n$ + $b_n$.

EDIT:

I started in on an induction proof. I'm kinda stuck on the final portion.

Let $x=1+\sqrt{3}$. The continued fraction expansion is <2, 1, 2, 1, 2, 1, 2, 1, ...> and the first few convergents are 2, 3, 8/3, 11/4, 30/11, 41/15, 112/41. So we have 2 = 2/1 = $a_1$/$b_1$ because 2 < $1+\sqrt{3}$ and 3 = 3/1 = $c_1$/$d_1$ because 2 > $1+\sqrt{3}$, so we have $a_1$ = 2, $b_1$ = 1, $c_1$ = 3, $d_1$ = 1.

Base case: Let n=1. Then $a_2$ = 2$c_1$ + $a_1$ = 2(3) + 2 = 8, etc. and we get $a_2$/$b_2$ = 8/3 and $c_2$/$d_2$ = 11/4 which is true.

Assume true for n=k (the formulas for $a_n$, $b_n$, etc.)

Prove for n=k+1: $a_{n+1}$ = 2$c_n$ + $a_n$ so $a_{k+2}$ = 2$c_{k+1}$ + $a_{k+1}$ = 8$c_k$ + 3$a_k$

There is where I get stuck

Let $x = [a_0; a_1 ,a_2 , \ldots]$. Find the continued fraction using the common algorithm. You will get $x = [2;\overline{1,2}]$.

Sidenote: If you are confused about the inequalities $a_n/b_n < x < c_n/d_n$, remember that $C_{2k} < C_{2k+1}$, and $C_{2k} < C_{2(k+1)}$ so that $C_0 < C_2 < \ldots < C_n < C_{n-1} < \ldots < C_5 < C_3 < C_1$. This is proven by simply considering $C_i - C_{i-2}$.

Let $C_i = p_i /q_i$ where $$p_0 = a_0, p_1 = a_0 a_1 + 1, p_i = a_i p_{i-1} + p_{i-2}\\q_0 = 1, q_1 = a_1, q_i = a_i q_{i-1} + q_{i-2}.$$ Hence $$p_0 = 2, p_1 = 2 \cdot 1 + 1 = 3\\ q_0 = 1, q_1 = 1.$$ So $$C_0 = \frac{p_0}{q_0} = 2,\\ C_1 = \frac{p_1}{q_1} = 3.$$ This confirms that $a_1 = 2, b_1=1, c_1=3,d_1=1$ in your notation.

$$p_2 = a_2 p_1 + p_0 = 2 \cdot 3 + 2 = 8, q_2 = a_2 q_1 + q_0 = 2 \cdot 1 + 1 = 3 \\ \implies C_2 = 8/3.$$ $$p_3 = a_3 p_2 + p_1 = 1 \cdot 8 + 3 = 11, q_3 = a_3 q_2 + q_1 = 1 \cdot 3 + 1 = 4 \\ \implies C_3 = 11/4.$$

It is easy to check that these results are in line with $n=1$ given by the recursive sequences. Hence the base case of the induction holds. Try to prove the induction.

Induction: $a_n/b_n$ will always correspond to even $n$ in the $C_n$ notation. Hence we need only prove that $a_{n+1} = 2p_n + p_{n-1}$ and $b_{n+1} = 2q_n + q_{n-1}$ for the left-hand side of the inequality $a_n/b_n < x$. But this follows immediately from the recursive equations for $p$ and $q$, as $a_{n+1}=2$ (where this $a$ is the $a$ in the continued fraction). We use these to prove $c_{n+1}$ and $d_{n+1}$. We have $$c_{n+1}=p_{n+2} = a_{n+2}p_{n+1} + p_n = a_{n+2} (a_{n+1} p_n + p_{n-1}) + p_n = p_n(a_{n+2} a_{n+1}+ 1) + a_{n+2} p_{n-1} = 3 c_n + a_n$$ where the $a_n$ after the last equality corresponds to the $a_n/b_n <x$ and the rest to the $a_i$'s in the continued fraction. $d_{n+1}$ is proven in a similar manner.

I must admit I find it terribly confusing dividing up the convergents on either side of $x$, as they are closely linked. Splitting them up into 4 separate sequences seems silly and unnecessary. $C_n$ notation saves a lot of trouble.