Continued Fraction Expansion of Irrational Square Root/Examples/29/Convergents
Convergents to Continued Fraction Expansion of $\sqrt {29}$
The sequence of convergents to the continued fraction expansion of the square root of $29$ begins:
- $\dfrac 5 1, \dfrac {11} 2, \dfrac {16} 3, \dfrac {27} 5, \dfrac {70} {13}, \dfrac {727} {135}, \dfrac {1524} {283}, \dfrac {2251} {418}, \dfrac {3775} {701}, \dfrac {9801} {1820}, \ldots$
The numerators form sequence A041046 in the On-Line Encyclopedia of Integer Sequences (N. J. A. Sloane (Ed.), 2008).
The denominators form sequence A041047 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 $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 {29}$:
- $\sqrt {29} = \sqbrk {5, \sequence {2, 1, 1, 2, 10} }$
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$ | $5$ | $5$ | $1$ | $\dfrac { 5 } 1$ | $5$ |
$1$ | $2$ | $5 \times 2 + 1 = 11$ | $2$ | $\dfrac { 11 } { 2 }$ | $5.5$ |
$2$ | $1$ | $1 \times 11 + 5 = 16$ | $1 \times 2 + 1 = 3$ | $\dfrac { 16 } { 3 }$ | $5.3333333333$ |
$3$ | $1$ | $1 \times 16 + 11 = 27$ | $1 \times 3 + 2 = 5$ | $\dfrac { 27 } { 5 }$ | $5.4$ |
$4$ | $2$ | $2 \times 27 + 16 = 70$ | $2 \times 5 + 3 = 13$ | $\dfrac { 70 } { 13 }$ | $5.3846153846$ |
$5$ | $10$ | $10 \times 70 + 27 = 727$ | $10 \times 13 + 5 = 135$ | $\dfrac { 727 } { 135 }$ | $5.3851851852$ |
$6$ | $2$ | $2 \times 727 + 70 = 1524$ | $2 \times 135 + 13 = 283$ | $\dfrac { 1524 } { 283 }$ | $5.3851590106$ |
$7$ | $1$ | $1 \times 1524 + 727 = 2251$ | $1 \times 283 + 135 = 418$ | $\dfrac { 2251 } { 418 }$ | $5.3851674641$ |
$8$ | $1$ | $1 \times 2251 + 1524 = 3775$ | $1 \times 418 + 283 = 701$ | $\dfrac { 3775 } { 701 }$ | $5.3851640514$ |
$9$ | $2$ | $2 \times 3775 + 2251 = 9801$ | $2 \times 701 + 418 = 1820$ | $\dfrac { 9801 } { 1820 }$ | $5.3851648352$ |
$\blacksquare$