# How do I solve a Continued Fraction of solution to quadratic equation?

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?

-

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}}}$$

-
So this solution is [-1;2,1,1,...], isn't that different from the one in the post above? – Spyral Aug 23 '12 at 18:51
@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...) – Raymond Manzoni Aug 23 '12 at 18:57
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 =/ – Spyral Aug 23 '12 at 19:08
Even though all these methods might be correct, this one was the clearest to me, thanks – Spyral Aug 23 '12 at 19:12
@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. – André Nicolas Aug 23 '12 at 19:14

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$$

-
The result of the continued fraction will be the larger of two roots. With $b>0$ and $c>0$ both roots are real. – Sasha Aug 23 '12 at 18:49
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"? – Rahul Aug 23 '12 at 18:52
@RahulNarain The product of roots of the quadratic polynomial is the free term. Thus, the smaller root is $z_2 = -\frac{c}{z_1}$. – Sasha Aug 23 '12 at 18:54
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. – Rahul Aug 23 '12 at 19:03
@RahulNarain I have expanded the post, addressing your second question now. – Sasha Aug 23 '12 at 19:26

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.

-