1
$\begingroup$

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$.

I am not sure where to start with this one. Help please? :)

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.