615
$\begingroup$

So we all know that the continued fraction containing all $1$s...

$$ x = 1 + \frac{1}{1 + \frac{1}{1 + \ldots}} $$

yields the golden ratio $x = \phi$, which can easily be proven by rewriting it as $x = 1 + \dfrac{1}{x}$, solving the resulting quadratic equation and assuming that a continued fraction that only contains additions will give a positive number.

Now, a friend asked me what would happen if we replaced all additions with subtractions:

$$ x = 1 - \frac{1}{1 - \frac{1}{1 - \ldots}} $$

I thought "oh cool, I know how to solve this...":

\begin{align} x &= 1 - \frac{1}{x} \\ x^2 - x + 1 &= 0 \end{align}

And voila, I get...

$$ x \in \{e^{i\pi/3}, e^{-i\pi/3} \} $$

Ummm... why does a continued fraction containing only $1$s, subtraction and division result in one of two complex (as opposed to real) numbers?

(I have a feeling this is something like the $\sum_i (-1)^i$ thing, that the infinite continued fraction isn't well-defined unless we can express it as the limit of a converging series, because the truncated fractions $1 - \frac{1}{1-1}$ etc. aren't well-defined, but I thought I'd ask for a well-founded answer. Even if this is the case, do the two complex numbers have any "meaning"?)

$\endgroup$
15
  • 22
    $\begingroup$ As an aside, do continued fractions with subtraction instead of addition have a name? I feel like the term "continued fraction" is reserved the form that uses addition. $\endgroup$ Mar 3, 2016 at 20:48
  • 89
    $\begingroup$ @MartinBüttner You got to be careful who you pick as your friends :) $\endgroup$
    – imranfat
    Mar 3, 2016 at 22:07
  • 81
    $\begingroup$ @imranfat Looking at this page, I couldn't ask for better ones. ;) $\endgroup$ Mar 3, 2016 at 22:08
  • 9
    $\begingroup$ “Why is $x$ complex“ is IMO not even a well-phrased question. A number is complex if it was introduced accordingly. If I start with “let $a\in\mathbb{C}$ such that etc etc, then do some maths and conclude that $a=3\pi$, it is still a complex number. What's interesting though is that it's in the real subset. Similarly, if you started out with some quaternion, then the question “is it complex” would make sense. But just juggling around algebraic expressions, using a solution technique for quadratic equations in $ℂ$ and then being surprised that the result is complex, is a bit ridiculous. $\endgroup$ Mar 3, 2016 at 23:29
  • 22
    $\begingroup$ @leftaroundabout Of course the surprising part isn't that a quadratic equation can have complex roots, but that a (by analogy with the golden ratio case seemingly valid) way to transform a (seemingly) real expression results in a quadratic equation with complex solutions, just like you'd be surprised if you got a negative rational result from summing natural numbers. My question wasn't "why am I getting complex roots for a quadratic" but "why do I seem to be able to deduct that this fraction is complex". $\endgroup$ Mar 4, 2016 at 8:56

8 Answers 8

529
$\begingroup$

You're attempting to take a limit.

$$x_{n+1} = 1-\frac{1}{x_n}$$

This recurrence actually never converges, from any real starting point. Indeed, $$x_2 = 1-\frac{1}{x_1}; \\ x_3 = 1-\frac{1}{1-1/x_1} = 1-\frac{x_1}{x_1-1} = \frac{1}{1-x_1}; \\ x_4 = x_1$$

So the sequence is periodic with period 3. Therefore it converges if and only if it is constant; but the only way it could be constant is, as you say, if $x_1$ is one of the two complex numbers you found.

Therefore, what you have is actually basically a proof by contradiction that the sequence doesn't converge when you consider it over the reals.

However, you have found exactly the two values for which the iteration does converge; that is their significance.

Alternatively viewed, the map $$z \mapsto 1-\frac{1}{z}$$ is a certain transformation of the complex plane, which has precisely two fixed points. You might find it an interesting exercise to work out what that map does to the complex plane, and examine in particular what it does to points on the real line.

$\endgroup$
8
  • 4
    $\begingroup$ It's coincidental that this 'continued fraction' has such nice periodic nature. Incidentally, the 'original continued fraction' has non-trivial convergence behaviour, as I show at math.stackexchange.com/a/624037/21820. (No idea who downvoted my answer though it is the other one that is incorrect.) $\endgroup$
    – user21820
    Mar 4, 2016 at 4:29
  • 20
    $\begingroup$ Fantastic answer! One point: it’s not quite a transformation of the complex plane; but rather of the extended complex plane $\mathbb{C} \cup \{\infty\}$, aka the Riemann sphere, or alternatively (more elementarily but less elegantly) of $\mathbb{C} \setminus \{ 0, 1 \}$. $\endgroup$ Mar 5, 2016 at 21:15
  • $\begingroup$ @MartinBüttner: the Golden Ratio goes to $\phi - 2$, not to 1. From $\mathbb{C}_\infty$, one can exclude any orbit or union of orbits, and get another domain on which the transformation acts (totally and invertibly); and $\{0,1,\infty\}$ is a complete (cyclic) orbit, so $\mathbb{C}\setminus\{0,1\}$ gives a suitable domain. $\endgroup$ Mar 6, 2016 at 8:39
  • 2
    $\begingroup$ @MartinBüttner Yes: assuming the value exists, you can show it is anything using your method. Therefore (by contradiction) it can't exist. $\endgroup$ Mar 7, 2016 at 7:57
  • 1
    $\begingroup$ @user254665 That doesn't mean the series could never converge; only that it doesn't do so from this particular starting point. $\endgroup$ Mar 12, 2016 at 10:48
102
$\begingroup$

I guess that what you're asking for is how the the imaginary unit, i.e. the square root of $-1$ is involved. Indeed it comes from the known identity between continuous fraction and continuous square roots, i.e. $$ \sqrt{a-b\sqrt{a-b\sqrt{a-b\sqrt{a-b\sqrt{\cdots}}}}}= -\cfrac{a}{b-\cfrac{a}{b-\cfrac{a}{b-\cfrac{a}{\ddots}}}} $$ Then you have in your case $a=1$ and $b=1$ you have $$ \sqrt{1-1\sqrt{1-1\sqrt{1-1\sqrt{1-1\sqrt{\cdots}}}}}= -\cfrac{1}{1-\cfrac{1}{1-\cfrac{1}{1-\cfrac{1}{1-\ddots}}}} $$ The solution is the well known solution of the equation $$ x=a/(b+x)$$ which brings to the result you found.

$\endgroup$
5
  • 7
    $\begingroup$ I hate hearing it called the "imaginary root". Damn you Descartes! Nice answer anyway :) $\endgroup$ Mar 4, 2016 at 16:03
  • 3
    $\begingroup$ Don't tell me! I wrote "imaginary unit" and someone edited it! $\endgroup$
    – Dac0
    Mar 4, 2016 at 17:47
  • 5
    $\begingroup$ You don't seem to have written "unit": the edit history doesn't have a single occurrence of this word. $\endgroup$
    – Ruslan
    Mar 4, 2016 at 19:35
  • 7
    $\begingroup$ strange... I never use the term "imaginary root", anyway now I change it :) $\endgroup$
    – Dac0
    Mar 4, 2016 at 20:19
  • 1
    $\begingroup$ “how the the imaginary unit, i.e. the square root of −1−1 is involved” - FWIW, remember that, via the closed form formula for the solution of the general cubic equation, non-real numbers may be encountered, even though the roots are real. $\endgroup$
    – Mike Jones
    Mar 9, 2016 at 17:56
71
$\begingroup$

When you substitute $a_n=a_{n+1}=x$ in $$a_{n+1}=1-\frac{1}{a_n}$$ you assume that the sequence converges to a fixed-point.

If this assumption is true (as in the + case), this method will help you find the fixed-point.

However, since the sequence does not converge, the solution of $$x=1-\frac{1}{x}$$ cannot be the fixed-point (since there is none).

$\endgroup$
2
  • 1
    $\begingroup$ But why does it converge for complex numbers? That was his question. $\endgroup$
    – Houshalter
    Mar 10, 2016 at 20:12
  • 3
    $\begingroup$ It does not.... If the recursion converges, then the method the OP mentioned will work to find the fix point, otherwise it's nonsense $\endgroup$
    – Uri Goren
    Mar 10, 2016 at 20:45
38
$\begingroup$

Have you even looked at the approximations, i.e., what happens if you stop filling up the "$\ldots$"? You get things that look like this: $$ 1-\frac1{1-\frac1{1-\frac1{\underbrace{\color{red}{1-\frac1{1}}}_0}}}$$ and that means that there is always some division by zero lurking deep inside. Hence we certainly cannot define this sort-of continued fraction as the limit of its finite approximants.

$\endgroup$
6
  • 9
    $\begingroup$ Yes I have (and said so in the last paragraph of the question). But the infinite continued fraction could still have been the limit of some other sequence of fractions. (In fact it is as Patrick's answer shows. Replace the 0 with one of the two complex roots and you get a constant and well-defined sequence.) $\endgroup$ Mar 4, 2016 at 17:30
  • 14
    $\begingroup$ This is not a valid explanation. The fraction continues indefinitely, so it cannot be evaluated in this sense. It may, however, still be divergent. It is more accurate to say we have an expression of the form $1 - \frac{1}{x}$, with $x$ still possibly be undefined. $\endgroup$ Mar 6, 2016 at 22:02
  • 5
    $\begingroup$ Instead of just leaving something away to terminate the "…", you could as well set it to some arbitrary value, e. g. 2. Then there would never "lurk" a DBZ deep inside. $\endgroup$
    – Alfe
    Mar 10, 2016 at 16:03
  • 5
    $\begingroup$ @ThisIsNotAnId For the usual continued fractions, the value is defined as limit of the finite continued fractions obtained precisely by chopping off at some point as I did. But I agree that in order to make sense of the OP's expression, one must somehow adjust the definition. Adjusting well-known definitions may lead to interesting results (such as $1+2+3+\ldots=-\frac1{12}$), but one must be aware that one has stretched things and be prepared for questions of why that makes sense and how that relates to the "traditional" but unapplicable definition (again, cf. $1+2+\ldots=-\frac1{12}$) $\endgroup$ Mar 10, 2016 at 20:43
  • 1
    $\begingroup$ is this indefiniteness the cause of complex root? $\endgroup$ May 19, 2017 at 12:45
32
$\begingroup$

This general method really is used. In the 1981 book Zetafunktionen und Quadratischer Körper by D. B. Zagier, he uses $$ x = n_0 - \frac{1}{n_1 - \frac{1}{n_2 - \frac{1}{n_3 - \ldots}}} $$ with $n_1,n_2,n_3,\ldots \geq 2$ as his basic way to represent quadratic irrationals. In the question above, the OP has all the $n_j = 1,$ which Zagier forbids. Zagier begins with this on page 126. It is necessary for him to do this because he wants to define "reduced" indefinite binary quadratic forms (page 122) as $A x^2 + B xy + C y^2$ with $B^2 - 4AC> 0$ but not a square, and $A>0, C>0, B > A+C.$ Here we go, page 126: the real number $w$ is the larger root of $Ax^2 - Bx + C=0,$ where $\langle A,B,C\rangle$ is reduced, if and only if the continued fraction (with the minus signs) for $w$ is purely periodic. Good, that is exactly how this should work. Meanwhile, just as with ordinary continued fractions, for finite continued fractions we do not want $n_j = 1,$ as that just replaces the integer $n_{j-1}$ by $n_{j-1} - 1.$ Of course, for infinite fractions we need $n_j \geq 2$ for convergence.

Oh, Gauss-Lagrange reduced indefinite forms, integer coefficients, have $AC<0, B > |A+C|.$ These go together with traditional continued fractions. Very similar theorem about purely periodic continued fractions.

$\endgroup$
2
  • 2
    $\begingroup$ Notice that $n \geq 2$. In this guy's example $n \equiv 1$. $\endgroup$
    – cactus314
    Mar 4, 2016 at 15:41
  • 3
    $\begingroup$ @cactus314 Wrong sign. n is neither function nor boolean variable. $\endgroup$ Mar 5, 2016 at 0:23
15
$\begingroup$

For any continued fraction we have some inequalities, that $[a]< [a,b,c]<[a,b]$ or with big fractions:

$$ a < a + \frac{1}{b + \frac{1}{c}} < a + \frac{1}{b} \tag{$\ast$}$$

What should the values of $a,b,c$ be in your case. Let's try adjusting the signs little bit:

$$ x = 1 - \cfrac{1}{1 - \cfrac{1}{x}} = 1 + \cfrac{1}{-1 + \cfrac{1}{x}} $$

Looks like $a = 1, b = -1, c = x$. Do we have that $[1] < [1,-1,x] < [1,x]$ ? We need $a,b,c > 0$. In your case we have the sequence:

$$ 1 \to 1 - \frac{1}{1} = 0 \to 1 - \frac{1}{0}= \infty \to 1 + \frac{1}{\infty}= 1$$

Then $1 \to 0 \to \infty \to 1$ is a cycle of size 3.


This still seems like a cop-out to me. We should look for an explanation why normal operations like $x \to x+1$ and $x \mapsto \frac{1}{x}$ takes us outside the realm of the fractions $\mathbb{Q}$.

$\endgroup$
2
  • 3
    $\begingroup$ A comment to the last paragraph (below the rule): Also $\lim_{n\to \infty} \sum_{i=0}^n \frac{1}{n!} = \mathrm e \not\in \mathbb Q$, even though it is just the addition of rational numbers. The connection is the limit to infinity, I think. $\endgroup$ Mar 5, 2016 at 17:39
  • 3
    $\begingroup$ In your second code block, shouldn't the sign-adjusted version $x = 1 + 1/(-1 + 1/x)$ be negated? Meaning shouldn't it be $x = -(1 + 1/(-1 + 1/x))$ or $-x = 1 + 1/(-1 + 1/x)$? $\endgroup$ Mar 14, 2016 at 15:46
4
$\begingroup$

Note that the answer, $x =1-\frac{1}{1-x}$.

$(x-1)(1-x)=1$

$-x^2+2x^2-1=1$

$-x^2+2x^2-2=0$

Now, take the quadratic formula. You get $x=1\pm i $

Lets look into the quadratic, and take the rest for real within the quadratic formula.

If you have a formula in the form of $ax^2+bx+c=0$, you can take $b^2-4ac$. If that value is positive, it is real. If not, it is imaginary. Since $a=-1, b=2,c=-2$, $b^2-4ac=4-(4\cdot(-1)\cdot(-2))=-4$, which means that the square root of that number will be an imaginary number, as shown above.

$\endgroup$
3
  • $\begingroup$ Thanks but this doesn't really answer my question. From one of the comments on the question: "Of course the surprising part isn't that a quadratic equation can have complex roots, but that a (by analogy with the golden ratio case seemingly valid) way to transform a (seemingly) real expression results in a quadratic equation with complex solutions, just like you'd be surprised if you got a negative rational result from summing natural numbers. My question wasn't "why am I getting complex roots for a quadratic" but "why do I seem to be able to deduct that this fraction is complex"." $\endgroup$ May 7, 2017 at 10:20
  • $\begingroup$ Is this appreciation or is that critism? I don't understand with my bad English :P $\endgroup$
    – Xetrov
    May 7, 2017 at 13:20
  • $\begingroup$ I appreciate that you're trying to help, but I feel that your answer misses the point of my question. I already know that quadratic equations can give complex results (and when that happens) but the question was why the continued fraction in the question evaluates to a complex value although it looks like it really shouldn't. Patrick Stevens has already answered that part to my satisfaction though. :) $\endgroup$ May 7, 2017 at 14:18
0
$\begingroup$

what have you done can be seen as a proof of divergence, we assume that the given continued fraction converges to a finite real value $x$, thus once you prove that $x$ is a complex number with $ Im(x) \neq 0$ you get the contradiction.

$\endgroup$

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.