Partial Quotients of Continued Fraction Expansion of Irrational Square Root

From ProofWiki
Jump to navigation Jump to search

Theorem

Let $n \in \Z$ such that $n$ is not a square.

Let the continued fraction expansion of $\sqrt n$ be expressed as:

$\left[{a_0, a_1, a_2, \ldots}\right]$


Then the partial quotients of this continued fraction expansion can be calculated as:

$a_r = \left\lfloor{\dfrac{\left\lfloor{\sqrt n}\right\rfloor + P_r} {Q_r} }\right\rfloor$

where:

$P_r = \begin{cases} 0 & : r = 0 \\

a_{r - 1} Q_{r - 1} - P_{r - 1} & : r > 0 \\ \end{cases}$


$Q_r = \begin{cases} 1 & : r = 0 \\

\dfrac {n - {P_r}^2} {Q_{r - 1} } & : r > 0 \\ \end{cases}$


Proof

The proof proceeds by strong induction.

For all $r \in \Z_{\ge 0}$, let $P \left({r}\right)$ be the proposition:

$a_r = \left\lfloor{\dfrac{\left\lfloor{\sqrt n}\right\rfloor + P_r} {Q_r} }\right\rfloor$

where:

$P_r = \begin{cases} 0 & : r = 0 \\

a_{r - 1} Q_{r - 1} - P_{r - 1} & : r > 0 \\ \end{cases}$


$Q_r = \begin{cases} 1 & : r = 0 \\

\dfrac {n - {P_r}^2} {Q_{r - 1} } & : r > 0 \\ \end{cases}$


Edge Cases

By definition of the structure of a continued fraction:

$\sqrt n = a_0 + \dfrac 1 {x_1}$

for some $a_0 \in \Z$ and $x_1 \in \R_{>0}$.

Thus:

\(\ds a_0\) \(=\) \(\ds \left\lfloor{\sqrt n}\right\rfloor\) Definition of Floor Function
\(\ds \) \(=\) \(\ds \left\lfloor{\dfrac {\sqrt n + 0} 1}\right\rfloor\)
\(\ds \) \(=\) \(\ds \left\lfloor{\dfrac {\sqrt n + P_0} {Q_0} }\right\rfloor\) Definition of $P_0$ and $Q_0$
\(\ds \) \(=\) \(\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_0} {Q_0} }\right\rfloor\) Floor of $\dfrac {x + m} n$

Thus $P \left({0}\right)$ is seen to hold.


We have that:

$\sqrt n = a_0 + \dfrac 1 {x_1}$

Then:

\(\ds \dfrac 1 {x_1}\) \(=\) \(\ds \sqrt n - a_0\)
\(\ds \leadsto \ \ \) \(\ds x_1\) \(=\) \(\ds \dfrac 1 {n - a_0}\)
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + a_0} {\left({\sqrt n - a_0}\right) \left({\sqrt n + a_0}\right)}\) multiplying top and bottom by $\sqrt n + a_0$
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_1} {Q_1}\) Definition of $P_1$ and $Q_1$


By definition of the structure of a continued fraction:

$x_1 = a_1 + \dfrac 1 {x_2}$

for some $a_1 \in \Z$ and $x_2 \in \R_{>0}$.

Hence:

\(\ds a_1\) \(=\) \(\ds \left\lfloor{\dfrac {\sqrt n + P_1} {Q_1} }\right\rfloor\) Definition of Floor Function
\(\ds \) \(=\) \(\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_1} {Q_1} }\right\rfloor\) Floor of $\dfrac {x + m} n$

Thus $P \left({1}\right)$ is seen to hold.


Basis for the Induction

We have that:

$x_1 = a_1 + \dfrac 1 {x_2}$

Then:

\(\ds \dfrac 1 {x_2}\) \(=\) \(\ds x_1 - a_1\)
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_1} {Q_1} - a_1\)
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_1 - a_1 Q_1} {Q_1}\)
\(\ds \leadsto \ \ \) \(\ds x_2\) \(=\) \(\ds \dfrac {Q_1} {\sqrt n - \left({a_1 Q_1 - P_1}\right) }\)
\(\ds \) \(=\) \(\ds \dfrac {Q_1} {\sqrt n - P_2}\) Definition of $P_2$
\(\ds \) \(=\) \(\ds \dfrac {Q_1 \left({\sqrt n + P_2}\right)} {\left({\sqrt n - P_2}\right) \left({\sqrt n + P_2}\right)}\) multiplying top and bottom by $\sqrt n + P_2$
\(\ds \) \(=\) \(\ds \dfrac {Q_1 \left({\sqrt n + P_2}\right)} {n - {P_2}^2}\) Difference of Two Squares
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_2} {\left({n - {P_2}^2}\right) / Q_1}\) By Expansion of Associated Reduced Quadratic Irrational, $\left({n - {P_2}^2}\right) / Q_1$ is an integer
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_2} {Q_2}\) Definition of $Q_2$


By definition of the structure of a continued fraction:

$x_2 = a_2 + \dfrac 1 {x_3}$

for some $a_2 \in \Z$ and $x_3 \in \R_{>0}$.


Thus:

\(\ds a_2\) \(=\) \(\ds \left\lfloor{\dfrac {\sqrt n + P_2} {Q_2} }\right\rfloor\) Definition of Floor Function
\(\ds \) \(=\) \(\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_2} {Q_2} }\right\rfloor\) Floor of $\dfrac {x + m} n$


This is the basis for the induction.


Induction Hypothesis

Now it needs to be shown that, if $P \left({k - 1}\right)$ and $P \left({k}\right)$ ares true, for all $k \ge 2$, then it logically follows that $P \left({k + 1}\right)$ is true.


This is the induction hypothesis:

$a_k = \left\lfloor{\dfrac{a_0 + P_k} {Q_k} }\right\rfloor$

where:

$P_k = a_{k - 1} Q_{k - 1} - P_{k - 1}$
$Q_k = \dfrac {n - {P_k}^2} {Q_{k - 1} }$

and:

$x_k = \dfrac{\sqrt n + P_k} {Q_k}$


from which it is to be shown that:

$a_{k + 1} = \left\lfloor{\dfrac{a_0 + P_{k + 1} } {Q_{k + 1} } }\right\rfloor$

where:

$P_{k + 1} = a_k Q_k - P_k$
$Q_{k + 1} = \dfrac {n - {P_{k + 1} }^2} {Q_k}$

and:

$x_{k + 1} = \dfrac{\sqrt n + P_{k + 1} } {Q_{k + 1} }$


Induction Step

This is the induction step:

By definition of the structure of a continued fraction:

$x_k = a_k + \dfrac 1 {x_{k+1} }$

where:

$x_{k+1} \in \R_{>0}$
$a_k = \left\lfloor{\dfrac{a_0 + P_k} {Q_k} }\right\rfloor$

by the induction hypothesis.

Then:

\(\ds \dfrac 1 {x_{k+1} }\) \(=\) \(\ds x_k - a_k\)
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_k} {Q_k} - a_k\)
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_k - a_k Q_k} {Q_k}\)
\(\ds \leadsto \ \ \) \(\ds x_2\) \(=\) \(\ds \dfrac {Q_k} {\sqrt n - \left({a_k Q_k - P_k}\right) }\)
\(\ds \) \(=\) \(\ds \dfrac {Q_k} {\sqrt n - P_{k + 1} }\) Definition of $P_{k + 1}$
\(\ds \) \(=\) \(\ds \dfrac {Q_k \left({\sqrt n + P_{k + 1} }\right)} {\left({\sqrt n - P_{k + 1} }\right) \left({\sqrt n + P_{k + 1} }\right)}\) multiplying top and bottom by $\sqrt n + P_{k + 1}$
\(\ds \) \(=\) \(\ds \dfrac {Q_k \left({\sqrt n + P_{k + 1} }\right)} {n - {P_{k + 1} }^2}\) Difference of Two Squares
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_{k + 1} } {\left({n - {P_{k + 1} }^2}\right) / Q_k}\) By Expansion of Associated Reduced Quadratic Irrational, $\left({n - {P_{k + 1} }^2}\right) / Q_k$ is an integer
\(\ds \) \(=\) \(\ds \dfrac {\sqrt n + P_{k + 1} } {Q_{k + 1} }\) Definition of $Q_{k + 1}$


By definition of the structure of a continued fraction:

$x_{k + 1} = a_{k + 1} + \dfrac 1 {x_{k + 2} }$

for some $a_{k + 1} \in \Z$ and $x_{k + 2} \in \R_{>0}$.


Thus:

\(\ds a_{k + 1}\) \(=\) \(\ds \left\lfloor{\dfrac {\sqrt n + P_{k + 1} } {Q_{k + 1} } }\right\rfloor\) Definition of Floor Function
\(\ds \) \(=\) \(\ds \left\lfloor{\dfrac {\left\lfloor{\sqrt n}\right\rfloor + P_{k + 1} } {Q_{k + 1} } }\right\rfloor\) Floor of $\dfrac {x + m} n$


So $P \left({k}\right) \implies P \left({k + 1}\right)$ and the result follows by the Second Principle of Mathematical Induction.


Hence the result.

$\blacksquare$


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Partial_Quotients_of_Continued_Fraction_Expansion_of_Irrational_Square_Root&oldid=338954"