3
$\begingroup$

I know that it is possible to make a CF (continued fraction) for every number that is a solution of a quadratic equation but I don't know how.

The number I'd like to write as a CF is:

$$\frac{1 - \sqrt 5}{2}$$

How do I tackle this kind of problem?

3 Answers 3

4

The general procedure is as follows for positive $x$. Let $x_0=x$, and let $[a_0;a_1,a_2,\dots]$ be the desired CF expansion. Then $a_0=\lfloor x_0\rfloor$. Given $x_n$ and $a_n$, let $$x_{n+1}=\frac1{x_n-a_n}$$ and $a_{n+1}=\lfloor x_{n+1}\rfloor$.

Since $\frac12(1-\sqrt5)$ is negative, let’s work with its absolute value, $x=\frac12(\sqrt5-1)$. Clearly $0\le x<1$ so $a_0=0$. Then $$x_1=\frac1x=\frac2{\sqrt5-1}=\frac{2(\sqrt5+1)}4=\frac{1+\sqrt5}2\;;$$ so $$\lfloor x_1\rfloor=\left\lfloor\frac{1+\sqrt5}2\right\rfloor=1\;,$$ since $2\le\sqrt5<3$, and $a_1=1$.

Now $$x_2=\frac1{x_1-1}=\frac2{\sqrt5-1}=x_1\;,$$ so everything repeats: $a_2=1$, $x_3=x_1$, $a_3=1$, etc. Thus, $x=[0;1,1,1,\dots]$, and your number is the negative of this.

5

Suppose $x$ is a root of $p(z) = z^2 - b z - c$. Then, diving $p(z)$ over $z$ and solving that for $z$ gets us $$ z = b+ \frac{c}{z} $$ Iterating: $$ z = b + \cfrac{c}{b + \cfrac{c}{z}} = \cfrac{b}{c + \cfrac{c}{b+ \ddots}} $$ Since $\frac{1-\sqrt{5}}{2}$ is a root of $z^2 - z -1$ we have: $$ \frac{1-\sqrt{5}}{2} = -\frac{1}{\frac{1+\sqrt{5}}{2}} = - \cfrac{1}{1 + \cfrac{1}{1+ \frac{1}{1+\ddots}}} $$


Added: Consider a sequence, defined by $x_{n+1} = b + \frac{c}{x_n}$, with $x_0 = \frac{c}{y}$. Few initial terms of the sequence are $\frac{c}{y}$, $b + y$, $b + \cfrac{c}{b+y}$, $b + \cfrac{c}{b + \cfrac{c}{b+y}}$, etc. It is well known that terms of this sequence can also be obtained as a ratio of two solutions, $a_n$ and $b_n$ to the following recurrence equation: $$ v_{n} = b v_{n-1} + c v_{n-2} \tag{1} $$ with initial conditions $a_0=y$, $a_1 = c$ and $b_0 = 1-\frac{b}{c} y$, $b_1 = y$. Then $x_n = \cfrac{a_n}{b_n}$. The solution to $(1)$ has the form: $$ v_{n} = v_0 \frac{z_1 z_2^n - z_2 z_1^n}{z_1-z_2} + v_1 \frac{z_1^n - z_2^n}{z_1-z_2} $$ where $z_1$ and $z_2$ are the two roots of $z^2 - b z -c = 0$. Assume $z_2>z_1$. In the large $n$ limit, $$ \lim_{n \to \infty} x_n = \lim_{n \to \infty} \frac{a_n}{b_n}= \lim_{n\to \infty} \frac{a_1 (z_1^n - z_2^n) + a_0 (z_1 z_2^n - z_1^n z_2)}{b_1 (z_1^n - z_2^n) + b_0 (z_1 z_2^n - z_1^n z_2)} = \frac{a_0 z_1 - a_1}{b_0 z_1 - b_1} = \frac{c (c- y z_1)}{c (y - z_1) + b y z_1} $$ In the case at hand $x_0 = \infty$ and $x_1 = b$, corresponding to the limit of $y \to \infty$, in which case the value of the continued fraction becomes: $$ \lim_{n \to \infty} x_n = \lim_{y \to 0} \frac{c (c- y z_1)}{c (y - z_1) + b y z_1} = - \frac{c}{z_1} = z_2 $$

  • 0
    The result of the continued fraction will be the larger of two roots. With $b>0$ and $c>0$ both roots are real.2012-08-23
  • 0
    How do you get the other root? Can you give some intuition about why, when you pass from the iterations to the limit, one of the roots "disappears"?2012-08-23
  • 0
    @RahulNarain The product of roots of the quadratic polynomial is the free term. Thus, the smaller root is $z_2 = -\frac{c}{z_1}$.2012-08-23
  • 0
    OK, but that doesn't answer my second question, because surely $z_2$ also satisfies $z=b+c/z$, $z = b+c/(b+c/z)$, and so on.2012-08-23
  • 0
    @RahulNarain I have expanded the post, addressing your second question now.2012-08-23
  • 0
    Thanks for the update. I corrected a typo, but I couldn't make sense of the phrase "In the case at hand $x_0$, corresponding to $y\to\infty$" which seems to be missing some words.2012-08-23
  • 0
    @RahulNarain I have fix the nonsensical sentence. Sorry about that.2012-08-24
  • 0
    The last expression in the second displayed equation has $\frac b{c+\cdots}$; certainly that should be $b+\frac c{b+\cdots}$ instead?2018-05-30
4

Let's rewrite $\ \dfrac {1-\sqrt{5}}2=-1+\dfrac {3-\sqrt{5}}2$ to have something positive to evaluate then : $$\frac 1{\dfrac {3-\sqrt{5}}2}=\frac 2{3-\sqrt{5}}=\frac {2(3+\sqrt{5})}{(3-\sqrt{5})(3+\sqrt{5})}=\frac {2(3+\sqrt{5})}{9-5}=\frac {3+\sqrt{5}}{2}=2+\frac {\sqrt{5}-1}{2}$$ (we want the term at the right to be between $0$ and $1$ at each stage)

You may continue this process until repetition !

You should get : $$\dfrac {1-\sqrt{5}}2=-1+\cfrac 1{2+\cfrac 1{1+\cfrac 1{1+\ddots}}}$$

  • 0
    So this solution is [-1;2,1,1,...], isn't that different from the one in the post above?2012-08-23
  • 0
    @Spyral: Sasha has a minus sign over the whole C.F. I have only the integer part with a sign (both results are correct, perhaps that this one is [more common](http://en.wikipedia.org/wiki/Continued_fraction#Basic_formulae)...)2012-08-23
  • 0
    That confused me indeed.. I thought a C.F. was UNIQUE.. so your solution being [-1,2,1,1,...], sasha's being -[0;1,1,...] and Brian M. Smiths being [0;1,1,...] is kind of confusing me =/2012-08-23
  • 0
    Even though all these methods might be correct, this one was the clearest to me, thanks2012-08-23
  • 2
    @Spyral: There are many types of continued fraction. The standard one in Number Theory is the *simple continued fraction* given in the very nice answer by Raymond Manzoni. For these, there is almost a uniqueness theorem (depending on how you define things, a rational will have two simple continued fraction expansions that are minor variants of each other). For *generalized continued fractions*, there is definitely not uniqueness.2012-08-23
  • 0
    @Spyral: Brian and Sasha have both $-[0;1,1,\cdots]$ (Brian adds 'your number is the negative of this'). For a fixed convention the solution is unique.2012-08-23
  • 0
    Thank you for the explanation @AndréNicolas and Raymond!2012-08-23
  • 0
    @Spyral: Glad it made things clearer !2012-08-23
  • 0
    Thanks for the kind words and fine explanations @André !2012-08-23