Fibonacci and gold

Most people have heard either about the golden ratio

\varphi := \frac{1}{2}(1 + \sqrt{5}) \approx 1.618\ldots

or about the Fibonacci numbers

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ….

They are intimately related, and I could write several enormous posts enumerating all of their amazing properties.

The golden ratio \varphi is an irrational number which satisfies the polynomial equation x^2 - x - 1 = 0, that is, we have \varphi^2 - \varphi - 1 = 0. In fact, since this is the lowest-degree (hence “simplest”) polynomial annihilating \varphi, we refer to it as the minimal polynomial of \varphi. Many surprising facts can be derived from this innocuous-looking relation. For example, \varphi^2 = 1 +\varphi immediately yields that \varphi = \sqrt{1 + \varphi}, from which we get the “continued surd” expression

\varphi = \sqrt{1 + \sqrt{1 + \sqrt{\ldots}}}

Stated differently, \varphi is a fixed point of the mapping x \mapsto \sqrt{1 + x}. When you were a kid, if you were bored with a calculator, maybe you had the idea of starting with some number, adding 1 to it and taking its square root, and then repeating this process ad nauseum. If you did that, you would have found that eventually the numbers on your calculator stop changing at exactly the value \varphi \approx 1.618 \ldots.

For something else, take our original equation \varphi^2 = \varphi + 1, and divide through by \varphi to obtain \varphi = 1 + \frac{1}{\varphi}. This tells us \varphi is also fixed by the map x \mapsto 1 + \frac{1}{x}. It follows immediately that the so-called “continued fraction expansion” of \varphi, which (in a precise sense) provides the data of the “best rational approximants” to \varphi, must look like:

With a lot of irrational numbers, we get much less pretty continued fraction expansions:

One thing to note is that the appearance of a large number in the continued fraction expansion, like 292 above, is telling us something about Diophantine approximation: that is, how well we’re able to approximate our number by rationals of a given denominator. The rationals you obtain by truncating a number’s continued fraction expansion are provably always the “best” in this sense. Thus, if we look at \varphi, whose continued fraction is just all 1’s, we can say that in this precise sense, \varphi is the number for which this “approximability” is the worst. It is as hostile as can be towards rational numbers.

Anyway, this is just a small taste of \varphi. Now let’s do something seemingly random: take the polynomial x^2 - x - 1 and “flip” the sequence of coefficients around, to obtain 1 - x - x^2 (alternatively, replace each exponent k in the expression with the new exponent 2-k). Now we’ll take a reciprocal:

\displaystyle \frac{1}{1-x-x^2} = \frac{1}{1-(x+x^2)}.

We’re going to look at the series expansion of this thing, which we get from the geometric series formula. For what it’s worth, I don’t care at all about convergence (it’s the summer break; my operator theory course doesn’t start until 2 weeks from now!), so just work completely formally.

\displaystyle \frac{1}{1-x-x^2} = \sum_{n=0}^\infty (x+x^2)^n = \sum_{n=0}^\infty \sum_{k=0}^n \binom{n}{k} x^k (x^2)^{n-k} = \sum_{n=0}^\infty \sum_{k=0}^n \binom{n}{k} x^{2n-k}.

Stare at this thing for a while and you notice that the coefficient F_k of x^k in the above is given by

\displaystyle F_k = \sum_{n=0}^\infty \binom{n}{2n-k}

which is (of course) actually a finite sum since we nonchalantly ditch any terms with 2n-k < 0 or 2n - k > n. The sequence F_k is the Fibonacci sequence (okay, except for being offset by one or something). It is not hard to show that as k \to \infty, we have F_{k+1}/F_k \to \varphi. In fact these common ratios are nothing more than the convergents of the continued fraction expansion of \varphi.

One cool thing Wikipedia mentions is that you can tile the plane with a “spiral” of squares whose side lengths are given by the Fibonacci sequence:

In the next post I will discuss why all this number-theoretic information related to \varphi (root of the polynomial x^2-x-1) shows up in the power series expansion of the reciprocal of the “reversed” polynomial 1-x-x^2. I’ll also apply the same general procedure to x^3 - x - 1, which has the so-called “plastic constant” \rho as its root. The sequence we’ll obtain is called the Padovan sequence, and you can perform a similar tiling of the plane using triangles of those side lengths. Once you look at x^4 - x - 1, the sequence you get from the series expansion is no longer nice and monotonic. This is odd, but in hindsight unsurprising since by analogy we would expect it to correspond to some kind of “tiling of the plane by a spiral of 2-sided polygons”, which is absurd.

Advertisements

About mlbaker

just another guy trying to make the diagrams commute.
This entry was posted in articles. Bookmark the permalink.

5 Responses to Fibonacci and gold

  1. matto says:

    Given that φ is a fixed point of the map f : x ↦ 1 + 1/x, it does not follow immediately that the “so-called” continued fraction expansion of φ is 1 + 1/(1+ 1/(1 + &c. Just a few days ago I was trying to find a continued fraction expansion for √2 − 1, the positive root of the equation x² + 2x − 1 = 0; re-writing this as x = −2 + 1/x and expanding in the obvious way yields the continued fraction expansion for −√2 − 1, the conjugate! Why? Though the map g : x ↦ −2 + 1/x has two fixed points, only one is attractive, and it’s not the one I wanted: |g'(√2 − 1)| > 3 + 2√2 > 1. If, however, we re-write x² + 2x − 1 = 0 as x = (x + 2)⁻¹ then the associated map h (which is the inverse of g!) satisfies |h'(√2 − 1)| = 1/|g'(√2 − 1)| < 1. Luckily for φ, the attractive fixed point of f is indeed φ. To find the continued fraction expansion of φ's conjugate, invert f; we get 1/(−1 + 1/(−1 + &c.

    • mlbaker says:

      You have a point, but given uniqueness of continued fraction expansions for irrationals, it does follow.

    • matto says:

      I wasn’t clear. Consider the following modification of your paragraph:
      “… take our original equation φ² = φ + 1, and divide through by φ, subtract 1 from both sides, and invert to obtain φ = 1/(−1 + φ). This tells us φ is also fixed by the map x ↦ 1/(−1 + x). It follows immediately that the so-called “continued fraction expansion” of φ […] must look like: 1/(−1 + 1/(−1 + &c.”
      This is false. I suggest adding “Since φ is an attractive fixed point of the map x ↦ 1 + 1/x, it follows that…” to your original.

  2. Do you mind if I quote a couple of your posts as long as I
    provide credit and sources back to your website?
    My blog is in the very same area of interest as yours and my users would certainly benefit from
    some of the information you provide here. Please let
    me know if this okay with you. Regards!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s