Continued Fraction Expansion of Irrational Square Root/Examples/13/Convergents
Jump to navigation
Jump to search
Convergents to Continued Fraction Expansion of $\sqrt {13}$
The sequence of convergents to the continued fraction expansion of the square root of $13$ begins:
- $\dfrac 3 1, \dfrac 4 1, \dfrac 7 2, \dfrac {11} 3, \dfrac {18} 5, \dfrac {119} {33}, \dfrac {137} {38}, \dfrac {256} {71}, \dfrac {393} {109}, \dfrac {649} {180}, \ldots$
The numerators form sequence A041018 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).
The denominators form sequence A041019 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).
Proof
Let $\sqbrk {a_0, a_1, a_2, \ldots}$ be its continued fraction expansion.
Let $\sequence {p_n}_{n \mathop \ge 0}$ and $\sequence {q_n}_{n \mathop \ge 0}$ be its numerators and denominators.
Then the $n$th convergent is $\dfrac {p_n} {q_n}$.
By definition:
- $p_k = \begin {cases} a_0 & : k = 0 \\ a_0 a_1 + 1 & : k = 1 \\ a_k p_{k - 1} + p_{k - 2} & : k > 1 \end {cases}$
- $q_k = \begin {cases} 1 & : k = 0 \\ a_1 & : k = 1 \\ a_k q_{k - 1} + q_{k - 2} & : k > 1 \end {cases}$
From Continued Fraction Expansion of $\sqrt {13}$:
- $\sqrt {13} = \sqbrk {3, \sequence {1, 1, 1, 1, 6} }$
Thus the convergents are assembled:
$k$ | $a_k$ | $p_k = a_k p_{k - 1} + p_{k - 2}$ | $q_k = a_k q_{k - 1} + q_{k - 2}$ | $\dfrac {p_k} {q_k}$ | Decimal value |
---|---|---|---|---|---|
$0$ | $3$ | $3$ | $1$ | $\dfrac { 3 } 1$ | $3$ |
$1$ | $1$ | $3 \times 1 + 1 = 4$ | $1$ | $\dfrac { 4 } { 1 }$ | $4$ |
$2$ | $1$ | $1 \times 4 + 3 = 7$ | $1 \times 1 + 1 = 2$ | $\dfrac { 7 } { 2 }$ | $3.5$ |
$3$ | $1$ | $1 \times 7 + 4 = 11$ | $1 \times 2 + 1 = 3$ | $\dfrac { 11 } { 3 }$ | $3.6666666667$ |
$4$ | $1$ | $1 \times 11 + 7 = 18$ | $1 \times 3 + 2 = 5$ | $\dfrac { 18 } { 5 }$ | $3.6$ |
$5$ | $6$ | $6 \times 18 + 11 = 119$ | $6 \times 5 + 3 = 33$ | $\dfrac { 119 } { 33 }$ | $3.6060606061$ |
$6$ | $1$ | $1 \times 119 + 18 = 137$ | $1 \times 33 + 5 = 38$ | $\dfrac { 137 } { 38 }$ | $3.6052631579$ |
$7$ | $1$ | $1 \times 137 + 119 = 256$ | $1 \times 38 + 33 = 71$ | $\dfrac { 256 } { 71 }$ | $3.6056338028$ |
$8$ | $1$ | $1 \times 256 + 137 = 393$ | $1 \times 71 + 38 = 109$ | $\dfrac { 393 } { 109 }$ | $3.6055045872$ |
$9$ | $1$ | $1 \times 393 + 256 = 649$ | $1 \times 109 + 71 = 180$ | $\dfrac { 649 } { 180 }$ | $3.6055555556$ |
$\blacksquare$