## Fibonacci times Euler

Recall the *Fibonacci numbers* 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)* 1,1,1,2,5,16,61,272… This is the number of alternating permutations in with the exponential generating function . Both sequences are incredibly famous. Less known are connection between them.

(1) Define the *Fibonacci polytope* to be a convex hull of 0/1 points in with no two 1 in a row. Then has vertices and vol This is a nice exercise.

(2) (by just a little). For example, . This follows from the fact that

and , where is the g*olden ratio*. Thus, the product . Since and , the inequality 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 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.

Cool! First time I’ve seen a *surjective* proof in combinatorics. 🙂