De divina proportione

Posted on by

As a mathematician, I often wonder if life would have been easier were I born 2,400 years ago. Back then, all you had to do to become eternally famous was to show that 3^2+4^2=5^2 ( I am looking at you Πυθαγόρα!) OK, maybe I am not giving the Ancients enough credit. I mean, they didn’t have an iPhone back then, so they probably had to do 3^2+4^2 by hand. All kidding aside, they did generalize the previous equality to other large numbers like 12^2+5^2=13^2 (I am feeling a little sassy today, I guess.) Still, back then, mathematics did not start as an abstract subject about relations between numbers. It grew from a naive attempt to control elements of design that were essential to living, like building airplanes and plasma TVs. The Greeks didn’t succeed then and, if I am not mistaken, they still haven’t succeeded in making either airplanes, or plasma TVs. But, back then at least, my ancestors made some beautiful buildings. Like the Parthenon.

The Acropolis in Athens, GreeceThe temple of Athina (the Goddess of Wisdom, which gave her name to the city we now call Athens after a fierce contest with Poseidon – imagine flying into Poseidonia every time you visited Greece had she lost) was designed to be seen from far away and inspire awe in those who wished to conquer the city-state of Athens. But, those who were granted access to the space behind the doric columns, came face to face with the second divine woman to ever make Zeus stand in attention, whenever she met her dad on legendary Mt. Olympus: Αθηνά. And so, Φειδίας (Phidias), that most famous of ancient Greek sculptors, decided to immortalize Athina’s power with a magnificent statue, a tribute to the effortless grace with which she personified the wisdom of an ancient culture in harmony with the earth’s most precious gift – feta cheese.

Here she is, playing an invisible electric cello next to Yo-Yo Ma (also invisible).

Here she is, playing an invisible electric cello next to Yo-Yo Ma (also invisible). And yes, she liked to work out.

OK, I may be biased on this one. For Greeks, virgin olive oil and φέτα cheese go like peanut butter and jelly (I didn’t even know the last two went so well together, until I left Greece for the country of America!) Oh yeah, you are probably wondering what feta cheese and olive oil have to do with the Goddess of Wisdom. Well, how do you think she won over the Athenians, against Zeus’ almighty brother, Poseidon? The olive branch, of course. The sea is good and all (actually, the sea is pretty freakin’ amazing in Greece), but you can’t eat it with feta – you can preserve feta in brine (salt water), which is why Poseidon had a fighting chance in the first place – but, yeah, not good enough. Which brings us to the greatest rival, nay – nemesis, of the first letter with an identity crisis, \pi: The letter \phi. You are most likely familiar with the letter-number \pi = 3.1415925123\ldots (you may have even seen the modern classic, American Pie, a tour-de-force, honest look at the life of Pi. No pun intended.) But, what about the number 1.618033\ldots? Well, I could tell you all about this number, \phi, named after the sculptor dude above, but I ‘d rather you figure out its history on your own through this simple math problem:

The divine proportion: Does there exist a function f: \mathbb{N} \rightarrow \mathbb{N}, such that f(1)=2, f(f(n)) = f(n)+n and f(n) < f(n+1) for all n \in \mathbb{N}?

Καλή τύχη, μικροί μου Φιμπονάτσι!

25 thoughts on “De divina proportione”

  3. Your pi is a bit strange, isn’t it? I happened to memorize 100 digits when I was a kid which is more than enough say that the right beginning is 3.1415926535897932384626433832795… and not your mutated version! Also, the golden mean ratio is rounded to 1.618034 which is almost exact.

    Now, Frank’s formula can’t be right as it gives f(1)=5.

    Z is also strange because f(8) gives something like 30. Too bad. It should give the next Fibonacci’s number, 13 or so.

    Let me explain. When we start with f(1)=2 and define f(f(1)) = f(2), we get 2+1, which is 3, and by continuing so, we clearly see that f(n) = the next Fibonacci number after “n” if “n” itself is a Fibonacci number, i.e. an element of the sequence 1,2,3,5,8,13 etc. where the next element is always the sum of the previous two.

    I can construct the values of f(n) for “n” being a Fibonacci’s number. The explicit formula for the n-th Fibonacci number is known and is similar to Frank’s formula.

    But roughly speaking, f(n) is the “next Fibonacci number” if “n” is Fibonacci and because the ratio of the adjacent Fibonacci numbers is the golden ratio, 1.618034 or so. one may say that for large enough “n”, the function f(n) must be very close to 1.618034 times n. But it must be an integer.

    The definition of f(n) is clearly possible for the subset of integers which are (n) Fibonacci numbers. It’s an increasing function (the next Fibonacci number), I have already described it. Can one fill the holes now?

    f(1)=2, f(2)=3, f(3)=5, f(5)=8, and so on.

    You see that f(4) is missing. It must be greater than 5 but smaller than 8. In other words, f(4) is either 6 or 7. This will then constrain f(6) or f(7) to be either 4+6 or 4+7, and so on. We will fill lots of other holes. I am confident it may be easily proved that we will stay in between the original Fibonacci numbers, with the right spacing.

    This fills some holes. However, f(7) and f(6) will remain undefined. We will be able to pick some other values, and so on.

    I haven’t gone through all the details but I would bet that the holes can be filled and it probably doesn’t matter which of the number we choose for f(4) and similarly f(n) for n being the first remaining “hole” as long as it is in the allowed interval given by the inequalities.

    I have made a certain finite number of tests and I believe, in particular, that

    f(n) = Round [ n*(1+Sqrt[5])/2 ]

    is a valid solution. Just to be sure, (1+Sqrt[5])/2 = 1.618034… is the golden ratio. To verify that this is a solution, if it is a solution, one must check that the rounding goes the right way.

    Reply ↓

    • I have numerically verified that

      f(n) = Round(1.618034…*n)

      is increasing for “n” at least up to 100,000 and it obeys f(f(n))=f(n)+n in this interval, too. Because the result and the used maths is so simple, I am confident that I could give a proof without a computer, too, but I will leave it to others. 😉

      Reply ↓

    • The value of pi was an Easter egg for you, Lubos. Glad to see my effort was recognized 🙂 As for your comment, you are spot on. Still, there is a very simple way to finish the proof. Can you find it?

      Reply ↓

      • Dear Spiros, OK 😉 let’s steal it from others.

        The function f(n) = Round(1.618034*n) with the right value of the golden mean is increasing because f(n+1)-f(n) is either 1 or 2 from rounding 1.618 so it is increasing.

        Now, let me verify the recursion relation.

        f(f(n))-f(n)-n
        gives
        Round (1.618*f(n)) – f(n) – n

        Now, let us divide 1.618 to 1 and 0.618. No particular reason, it’s just what we often do with the golden ratio because 1/0.618 = 1+0.618, it’s the funny thing about dividing the Greek bodies’ proportions. (I think that after decades of socialism, the ratio of thickness to height is closer to 1.618: I never understood why people thought that the human proportions were like this because humans are/were much less fat than that, weren’t they?)

        OK, so

        Round (1.618*f(n)) – f(n) – n =
        Round ((1 + 0.618)*f(n)) – f(n) – n = ….

        This is funny because the first Round is rounding a sum of an integer and a non-integer. The integer term may be just taken in front of the rounding because it is already rounded and it doesn’t affect the fractional part. So

        … = f(n)+Round (0.618*f(n)) – f(n) – n = ….

        But now we see that f(n) actually cancels, so this is

        … = Round(0.618*f(n)) – n = …

        Well, this has to be equal to zero because it is essentially the rounded value of 0.618 times the difference that defines f(n).

        … = Round(0.618*f(n)-n) = Round(0.618*(Round(1.618*n)-1.618*n))

        I have rewritten the term “n” as Round(1.618*0.618*n) so that it could be inserted to the same bracket.

        However, now, Round(1.618*n)-1.618*n is the difference of a rounded number and the same (irrational) number so its absolute value is less than 0.5. And if you multiply this number with absolute value below 0.5 by 0.618, you get a number that rounds to zero. QED. 😉

        Reply ↓

          • OK, so when it comes to *this* task, I will already really leave it to the high school student. I don’t think that this task is really well-defined.

            With long lines and/or smaller fonts, my proof could be written on one line and much of the length of the comment in which it was written was there due to the pedagogical clarity that a high school student could easily omit and the hired “shortener” could omit it, too. I view this as added value, not a subtracted value, and the question how complicated steps one may really do so that the proof is still legit depends on conventions and/or background.

            At the end, when f(n) is defined as Round(1.618*n), we could easily write down the proof as f(f(n))-f(n)-n = … = 0 immediately. Everything in between are steps one can claim to see immediately or calculate in her head or they may be called elementary operations.

            Quite generally, I think that this “shortening of proofs” isn’t a physicist’s approach to questions. So I always sympathized with a comment in Feynman’s lectures in physics that a physicist doesn’t find it important to subtract every redundant axioms and minimize them at any cost. A (not necessarily minimal) collection of axioms/postulates that is internally consistent is just fine.

            Reply ↓

            • It is true that brevity doesn’t always imply elegance. In this case, though, it does. Hint: Do you really need to construct the function?

            • Dear Spiros, no, one can prove the assertion without constructing a function obeying the conditions. After all, because the proof with the “canonical” example depends on 0.618/2 being smaller than 1/2, and it’s actually way smaller, it seems likely that the function obeying your conditions isn’t unique, as initially claimed.

              Still, I believe that Round(1.618…*n) is the most canonical example of a function obeying the conditions, it’s qualitatively prettier – by its being so explicit and natural – than any other solution, and I actually think that when a constructive proof with a canonical enough construction may be given, it is always preferred over an abstract existential proof.

            • An alternative semi-constructive proof. I won’t even mention that f(n) = next Fibonacci number if “n” is Fibonacci. 😉

              Define f(1)=2. And define f(n) one by one, for larger n, by this rule: if n=f(m) for some previous “m”, i.e. if “n” is already in the range of values f(m), then set f(n)=f(f(m)) = f(m) +m. Otherwise, if “n” is a value that hasn’t appeared as f(m), set f(n)=f(n-1)+1 [one could sometimes afford +2, but I want to be specific].

              By this construction, it’s clear that the recursive rule is always obeyed. It’s increasing for those n-1 vs n for which we used the second rule, f(n)=f(n-1)+1. It’s also increasing if we used the first value because 1) the previous sequence was increasing, 2) the size of the hole is greater than the size of the hole from which we imprinted it via f(n).

            • Dear Spiros,
              the ad hoc definition implies that generically there are two values of the argument of f, namely A=f(a) and the (greater, next) B=f(b), for which f is defined as

              f(A) = f(a)+a
              f(B) = f(b)+b

              and then there are the values C strictly between A,B which I call the hole and where I define f(C) by some ad hoc “plus one” jumping rule. I choose the minimal increment, one, that is compatible with the strictly increasing nature of f.

              Now, using a formalism, concerning 2), you are asking me – just realize that – why f(B)-f(A) is greater than f(b)-f(a) because you’re asking me why I am allowed to increase the value from f(A) by one B-A+1 times and still remain below f(B).

              But f(B)-f(A) – [ f(b) – f(a) ] = b-a which is still positive before “a” was written down before “b”. 😉 I am probably not presenting it optimally comprehensibly but do you think it’s wrong? Sorry for not giving you one line. My interest in your one-line proof has grown a bit. 😉

              LM

            • You got it. You wrote the one line proof! In my mind, the whole problem can be solved in a couple lines using what you have already written:
              Set a_1=2, f(a_k)=a_{k+1}. Then, from the equation f(f(n))=f(n)+n, we get a_{k+2}=a_{k+1}+a_k, the Fibonacci numbers 🙂 The final step (the one line proof I was referring to at this stage), is this: We need to show that between f(a_{k+1}) and f(a_k) there are enough integers to map the remaining interval (a_k,a_{k+1}) (by definition, a function must avoid collisions in its range). In other words, we need to show that a_{k+2}-a_{k+1}\geq a_{k+1}-a_k, which is equivalent to having a_k \geq a_{k-1}, which is true since a_k-a_{k-1}= a_{k-2} \geq 0.

            • Dear Spiros, good to hear! Concerning your one-line proof, it still shows on 8 lines in my browser which must be some bug on my computer! 😉

              Second, I am not sure whether your proof is complete or whether I am just overlooking something. One has to verify not only that there are “enough numbers in between the Fibonacci numbers. Even for values of “n” which are not Fibonacci, it must still be true that f(f(n)) = f(n)+n. I don’t quite see whether you have guaranteed that it’s possible. This recursive formula could very well force you into higher increments for larger values of “n”.

              But if you promise me that you have understood what I wrote and what you wrote is ultimately a shortened version of the same thing, then it’s OK 😉 but sometimes overly shortened things may be incomprehensible to me…

  4. I have not yet read Lubos’s proof, but (a messier) algebraic proof using some basic Fibonacci formula you could get by just tinkering around:

    Let us denote the nth Fibonacci number by F(n).

    Pick f(4) to be some ‘a’, where ‘a’ is not a Fibonacci number of course. The series “generated” by ‘f’ starting from 4 would be of the form 4 F(n) + a F(n+1).

    We can be sure the above series would not “run into” the Fibonacci series as for any consecutive pair F(n) and F(n+1), and an F(m) coming later than the pair in the Fibonacci series –

    F(m) = F(k)F(n) + F(k+1)F(n+1) for some k. Since 4 and ‘a’ are not Fibonacci there is no “running into”.

    Now if, say, you took 7 to be the ‘a’ above you now need to define f(6). We can do it by repeating the same strategy, and can be assured the “f(6)” series would not run into the “f(2)” series either, by a similar but even messier (though straightforward) calculation using representing a later Fibonacci number in terms of earlier ones. And so on..

    Reply ↓

    • Ashley, the amazing thing about this problem is that to solve it, you don’t need to know anything about Fibonacci numbers, but you come across them anyway! This problem is the simplest math Olympiad problem I have ever encountered. You are allotted 90 mins on average to solve such a problem. The solution is a few lines long, but it can take a lot longer to solve if knowledge of Fibonacci sequences becomes involved. Sometimes, the most elegant solution is the one we arrive at when we are taking elementary steps in the dark.

      Reply ↓

      • Dear Spiros,

        when you excitedly say “you don’t need to know anything about Fibonacci numbers, but you come across them anyway!”, I am just not getting it.

        The problem you mentioned contains the relation “f(f(n)) = f(n)+n” which guarantees, for “n” in the range of the function “f”, that “f(n)” is “the next Fibonacci number after n”. Because this recursive relation is a full definition needed to define Fibonacci numbers, what a surprise that you define them.

        One doesn’t have to know that the objects defined in this way are called Fibonacci numbers. One doesn’t even have to know that the great mathematician Leonardo Fibonacci of Pisa was the key guy who spread the Hindu-Arabic numeral system in Europe. 😉 But this is true about all things in maths – and in science as well – isn’t it? If you give enough data or a definition, you may define what the object is even if you don’t mention the name. And even when you mention the definition, the object may still have many features – such as the asymptotic ratio f(n)/n, the golden mean, and the way to write it as (sqrt(5)+1)/2 = 1.618…, that aren’t known from the beginning but one may gradually discover them by looking into the structure creatively.

        If I tell you to calculate the transition amplitudes in QM for times between “t” and “t+dt” and then to use the transitivity of the evolution operator to calculate the evolution from “t1” to “t2” by decomposing the interval into infinitesimal pieces, one may also say that “one doesn’t have to even know what Feynman’s path integral is but she encounters it, anyway”. What a surprise if I have described the way to encounter it, pretty much its definition. What’s the difference from the Fibonacci case?

        So I don’t understand how the problem differs from pretty much any math (or mathematical physics) problem.

        Cheers
        LM

        Reply ↓

        • Dear Lubos,

          Two things: You are right and you are right again.
          First right: My one-line solution is not sufficient to prove the existence of the function, since I only selectively used the condition f(f(n)) = f(n)+n.
          Second right: Your initial solution with Round(1.618*n) is correct and is the right way to prove the existence of this function. I am not sure why, but until I went back and looked at your solution now, I kept thinking that you had written Round(1.618^n), which seemed strange to me. Mea culpa!

          As for your comments above, I agree that Fibonacci is the dude. What I had in mind when answering Ashley above was the simple (wrong) proof that did not use Fibonacci knowledge at all and might have given a high school student a fighting chance. I find it interesting that, somehow unconsciously, the problem I chose for this post was a good illustration of how the golden ratio works…

          Thanks for keeping me honest,
          Spiros

          Reply ↓

Your thoughts here.