Archive

Posts Tagged ‘golden ratio’

Fibonacci times Euler

November 5, 2016 2 comments

Recall the Fibonacci numbers F_n given by 1,1,2,3,5,8,13,21… There is no need to define them. You all know. Now take the Euler numbers (OEIS) E_n 1,1,1,2,5,16,61,272… This is the number of alternating permutations in S_n with the exponential generating function \sum_{n=0}^\infty E_n t^n/n! = \tan(t)+\sec(t).  Both sequences are incredibly famous. Less known are connection between them.

(1) Define the Fibonacci polytope \Phi_n to be a convex hull of  0/1 points in \Bbb R^n with no two 1 in a row. Then  \Phi_n has F_{n+1} vertices and vol(\Phi_n)=E_n/n! This is a nice exercise.

(2) F_n \cdot E_n \ge n! (by just a little). For example, F_4 \cdot E_4 = 5 \cdot 5 = 25 > 4!. This follows from the fact that

F_n \sim \frac{1}{\sqrt{5}} \, \phi^{n+1} and E_n\sim \frac{4}{\pi}\left(\frac{2}{\pi}\right)^{n} n!, where \phi=(1+\sqrt{5})/2 is the golden ratio. Thus, the product F_n \cdot E_n \sim c n! \left(\frac{2\phi}{\pi}\right)^n. Since \pi = 3.14 and 2\phi = 3.24, the inequality F_n \cdot E_n \ge n! is easy to see, but still a bit surprising that the numbers are so close.

Together with Greta Panova and Alejandro Morales we wrote a little note “Why is π < 2φ?” which gives a combinatorial proof of (2) via a direct surjection. Thus we obtain an indirect proof of the inequality in the title.  The note is not a research article; rather, it is aimed at a general audience of college students.  We will not be posting it on the arXiv, so I figure this blog is a good place to advertise it.

The note also explains that the inequality (2) also follows from Sidorenko’s theorem on complementary posets. Let me briefly mention a connection between (1) and (2) which is not mentioned in the note.  I will assume you just spent 5 min and read the note at this point.  Following Stanley, the volume of \Phi_n is equal to the volume of the chain polytope (=stable set polytope), see Two Poset Polytopes.  But the latter is exactly the polytope that Bollobás, Brightwell and Sidorenko used in their proof of the upper bound via polar duality.