5
$\begingroup$

Every infinite continued fraction is irrational. But can every number, in particular those that are not the root of a polynomial with rational coefficients, be expressed as a continued fraction?

$\endgroup$
  • $\begingroup$ Yes. The infinite continued fractions with $0$ integer part are precisely the irrational numbers in $(0,1)$. $\endgroup$ – Brian M. Scott Feb 11 '13 at 3:16
  • $\begingroup$ how do you prove it? $\endgroup$ – user61779 Feb 11 '13 at 3:21
9
$\begingroup$

The infinite continued fractions are precisely the irrational numbers; you will find a proof here, along with a proof that the expansion is unique.

$\endgroup$
  • 1
    $\begingroup$ The link you posed does not exists anymore, please posed then content if possible. $\endgroup$ – Peter Teoh Jun 29 '16 at 2:35
  • 1
    $\begingroup$ @Peter: Apparently they rearranged their site, but the page still exists, and I've updated the link. $\endgroup$ – Brian M. Scott Jun 29 '16 at 2:50
8
$\begingroup$

To express an irrational number $\alpha$ as a continued fraction, do this:

  1. Put $\alpha_0 = \alpha$ and $n=0$.
  2. Let $a_n = \lfloor\alpha_n\rfloor$, the greatest integer not exceeding $\alpha_n$.
  3. Put $\alpha_{n+1} = {(\alpha_n - a_n)}^{-1}$.
  4. Add 1 to $n$.
  5. Go back to step 2.

The continued fraction expansion of $\alpha$ is then:

$$\alpha = a_0 + \cfrac{1}{ a_1 + \cfrac{1}{ a_2 + \cfrac{1}{ a_3 + \cdots}}}$$

For example, let's take $\alpha = \pi = 3.141529\ldots$. Then

  1. $\alpha_0 = 3.141529\ldots$ and $a_0 = 3$.
  2. $\alpha_1 = {(0.14159\ldots)}^{-1} \approx 7.06251$ and $a_1 = 7$.
  3. $\alpha_2 = {(0.06251\ldots)}^{-1} \approx 15.9966$ and $a_2 = 15$.
  4. $\alpha_3 = {(0.09966\ldots)}^{-1} \approx 1.00341$ and $a_3 = 1$.

And so we have

$$\pi = 3 + \cfrac{1}{ 7 + \cfrac{1}{ 15 + \cfrac{1}{ 1 + \cdots}}}$$

which is correct.

Note that since $a_n = \lfloor\alpha_n\rfloor$, we know that $\alpha_n-1 < a_n \le \alpha_n$, and therefore that $\alpha_n - a_n$ must be at least 0, but less than 1. If $\alpha_n - a_n$ is nonzero, its reciprocal, which is $\alpha_{n+1}$, must be strictly greater than 1. Then $a_{n+1}$ must be a positive integer, as required.

If you take $\alpha$ to be a rational number, the process will terminate when one of the $\alpha_n$ is zero. If $\alpha$ is an irrational number, the process can't terminate in this way, since if it had, you would be able to write $\alpha$ as a finite continued fraction, which you would be able to put into standard $\frac ab$ form, which is impossible. That is a (somewhat handwavy) proof that you were looking for.

$\endgroup$
-2
$\begingroup$

The set of non-computable numbers is a strict subset of the transcendental numbers. If infinite continued fractions are computable, then I believe that they would not include all the transcendental numbers. Chaitin's constant is transcendental, but cannot be represented by an infinite continued fraction. Chaitin's constant cannot be represented through an algorithmic process.

$\endgroup$
  • $\begingroup$ Where is there any restriction that the continued fractions be computable? (Specifically, the sequence of $a_i$s is not required to be computable.) $\endgroup$ – Noah Schweber Jan 3 at 17:53

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.