Archive

Posts Tagged ‘Fibonacci numbers’

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.

Advertisements