Order ideals of a fence

Question

Let $F_n$ be the $n$-element fence, that is, $F_n=\{a_1, \ldots, a_n\}$ with $$a_1>a_2<a_3>\cdots a_n$$ and no other elements related. Here is the Wikipedia article about fences : https://en.wikipedia.org/wiki/Fence_(mathematics).

The Fibonacci sequence is given by $f_1=f_2=1$ and $f_k=f_{k-2}+f_{k-1}$, for $k>2$. The first few numbers are $$1,1,2,3,5,8,13,21,\ldots$$ Show that the number of order-ideals (down-sets) of $F_n$ is $f_{n+2}$.

It is easy to see that $F_1$ has two order-ideals: $\varnothing$ and $\{a_1\}$; $F_2$ is a two element chain $a_1>a_2$ and has three order-ideals: $\varnothing$, $\{a_2\}$ and $\{a_1,a_2\}$, and so on.

How can I prove this in general?

Thanks!

Answer 1

Use induction on the number of elements.
For the induction step, use this answer and the fact that $$F_n\setminus\{a_n\}\cong F_{n-1} \quad\text{and}\quad F_n\setminus({\uparrow}a_n \cup {\downarrow}a_n) \cong F_{n-2}.$$

Answer 2

Let $\mathcal{O}(P)$ be the set of order-ideals of the poset $P$. Since $|F_1|=1$, it is $|\mathcal{O}(F_1)|=2=f_3$. Suppose that $|\mathcal{O}(F_k)|=f_{k+2}$ for all $k<n$. Since $$F_n\setminus\{a_n\}\cong F_{n-1} \quad\text{and}\quad F_n\setminus({\uparrow}a_n \cup {\downarrow}a_n) \cong F_{n-2}$$ which can be easily verified by eye inspection using the diagrams, by induction and this answer $$|\mathcal{O}(F_n)|=|\mathcal{O}(F_{n-1})|+|\mathcal{O}(F_{n-2})|=f_{n+1}+f_n=f_{n+2}.$$