Problem Statement
This task investigates continued fraction representations of quadratic irrationals, rational approximations, and integer solutions to Pell's equation $x^2 - D y^2 = 1$.
**(a)** [4 marks] By writing $\sqrt{3} = 1 + (\sqrt{3} - 1)$ and taking reciprocals of fractional remainders, prove that the simple continued fraction of $\sqrt{3}$ is periodic and given by $[1; \overline{1, 2}]$.
**(b)** [5 marks] The $n$-th convergent is defined as $C_n = \frac{p_n}{q_n} = [a_0; a_1, \dots, a_n]$. The numerators and denominators satisfy the linear recurrence relations:
$$p_n = a_n p_{n-1} + p_{n-2}, \quad q_n = a_n q_{n-1} + q_{n-2}$$
with $p_{-1} = 1, p_{-2} = 0$ and $q_{-1} = 0, q_{-2} = 1$.
Use mathematical induction to prove that:
$$p_n q_{n-1} - p_{n-1} q_n = (-1)^{n-1} \quad \text{for all } n \ge 0$$
**(c)** [4 marks] Compute the first five convergents $C_0, C_1, C_2, C_3, C_4$ of $\sqrt{3}$ as simplified common fractions.
**(d)** [6 marks] Pell's equation for $D = 3$ is $x^2 - 3y^2 = 1$.
Show that the numerator and denominator of convergent $C_1 = \frac{p_1}{q_1}$ provide the fundamental minimal positive integer solution $(x_1, y_1)$ to $x^2 - 3y^2 = 1$.
Verify that $C_3 = \frac{p_3}{q_3}$ also satisfies $x^2 - 3y^2 = 1$, and explain why only odd convergents satisfy this equation.
**(e)** [6 marks] The generator matrix $\mathbf{M} = \begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix}$ generates all integer solutions via $\begin{pmatrix} x_{k+1} \\ y_{k+1} \end{pmatrix} = \mathbf{M} \begin{pmatrix} x_k \\ y_k \end{pmatrix}$.
Find the next two solutions $(x_2, y_2)$ and $(x_3, y_3)$, and prove that $\lim_{k \to \infty} \frac{x_k}{y_k} = \sqrt{3}$.
Verified Solution & Marking Scheme
Part (a): Periodic Continued Fraction Expansion [M1, A1, AG]
$$x_0 = \sqrt{3} \implies a_0 = \lfloor\sqrt{3}\rfloor = 1, \quad r_0 = \sqrt{3} - 1$$
$$x_1 = \frac{1}{\sqrt{3} - 1} = \frac{\sqrt{3} + 1}{2} \implies a_1 = \left\lfloor\frac{\sqrt{3} + 1}{2}\right\rfloor = 1, \quad r_1 = \frac{\sqrt{3} + 1}{2} - 1 = \frac{\sqrt{3} - 1}{2}$$
$$x_2 = \frac{2}{\sqrt{3} - 1} = \sqrt{3} + 1 \implies a_2 = \lfloor\sqrt{3} + 1\rfloor = 2, \quad r_2 = (\sqrt{3} + 1) - 2 = \sqrt{3} - 1$$
Since $r_2 = r_0$, the pattern repeats with period 2:
$$\sqrt{3} = [1; \overline{1, 2}]$$ [AG]
Part (b): Induction Proof of Determinant Identity [M1, A1, R1]
Base case $n = 0$:
$$p_0 q_{-1} - p_{-1} q_0 = a_0(0) - (1)(1) = -1 = (-1)^{-1} = (-1)^1$$
Inductive hypothesis: Assume true for $n = k$:
$$p_k q_{k-1} - p_{k-1} q_k = (-1)^{k-1}$$
For $n = k + 1$:
$$p_{k+1} q_k - p_k q_{k+1} = (a_{k+1} p_k + p_{k-1}) q_k - p_k (a_{k+1} q_k + q_{k-1})$$
$$= a_{k+1} p_k q_k + p_{k-1} q_k - a_{k+1} p_k q_k - p_k q_{k-1} = -(p_k q_{k-1} - p_{k-1} q_k)$$
$$= -(-1)^{k-1} = (-1)^k$$
By PMI, the identity holds for all integers $n \ge 0$.
Part (c): Evaluation of Convergents [M1, A1, A1]
Convergents table:
- $n = 0: a_0 = 1 \implies C_0 = \frac{1}{1} = 1$
- $n = 1: a_1 = 1 \implies C_1 = 1 + \frac{1}{1} = \frac{2}{1}$
- $n = 2: a_2 = 2 \implies C_2 = 1 + \frac{1}{1 + 1/2} = 1 + \frac{2}{3} = \frac{5}{3}$
- $n = 3: a_3 = 1 \implies C_3 = \frac{1(5) + 2}{1(3) + 1} = \frac{7}{4}$
- $n = 4: a_4 = 2 \implies C_4 = \frac{2(7) + 5}{2(4) + 3} = \frac{19}{11}$
Convergents are: $1, \; 2, \; \frac{5}{3}, \; \frac{7}{4}, \; \frac{19}{11}$.
Part (d): Pell's Equation Solutions [M1, A1, R1]
For $C_1 = \frac{2}{1} \implies x_1 = 2, y_1 = 1$:
$$2^2 - 3(1)^2 = 4 - 3 = 1$$
For $C_3 = \frac{7}{4} \implies x_2 = 7, y_2 = 4$:
$$7^2 - 3(4)^2 = 49 - 3(16) = 49 - 48 = 1$$
For even convergents:
$C_0: 1^2 - 3(1)^2 = -2 \neq 1$
$C_2: 5^2 - 3(3)^2 = 25 - 27 = -2$
$C_4: 19^2 - 3(11)^2 = 361 - 363 = -2$
Since period length is $\ell = 2$ (even), solutions occur at odd indices $n = 2k - 1$.
Part (e): Matrix Power Generation & Convergence [M1, A1, R1]
Using generator matrix $\mathbf{M} = \begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix}$:
$$\begin{pmatrix} x_2 \\ y_2 \end{pmatrix} = \begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} 2 \\ 1 \end{pmatrix} = \begin{pmatrix} 7 \\ 4 \end{pmatrix}$$
$$\begin{pmatrix} x_3 \\ y_3 \end{pmatrix} = \begin{pmatrix} 2 & 3 \\ 1 & 2 \end{pmatrix} \begin{pmatrix} 7 \\ 4 \end{pmatrix} = \begin{pmatrix} 2(7) + 3(4) \\ 1(7) + 2(4) \end{pmatrix} = \begin{pmatrix} 26 \\ 15 \end{pmatrix}$$
Check: $26^2 - 3(15)^2 = 676 - 3(225) = 676 - 675 = 1$.
For convergence: Divide $x_k^2 - 3y_k^2 = 1$ by $y_k^2$:
$$\left(\frac{x_k}{y_k}\right)^2 - 3 = \frac{1}{y_k^2}$$
As $k \to \infty, y_k \to \infty \implies \frac{1}{y_k^2} \to 0$, so $\left(\frac{x_k}{y_k}\right)^2 \to 3 \implies \lim_{k \to \infty} \frac{x_k}{y_k} = \sqrt{3}$.