A Note on the Fibonacci Sequence and Schreier-type Sets

Hung Viet Chu

Published 2022-05-27Version 1

A set $A$ of positive integers is said to be Schreier if either $A = \emptyset$ or $\min A\ge |A|$. For $n\ge 1$, let $$\mathcal{K}_n\ :=\ \{A\subset \{1, \ldots, n\}\,:\, \mbox{either }A = \emptyset \mbox{ or } (\max A-1\in A\mbox{ and }\min A\ge |A|)\}.$$ We give a combinatorial proof that for each $n\ge 1$, we have $|\mathcal{K}_n| = F_n$, where $F_n$ is the $n$th Fibonacci number. As a corollary, we obtain a new combinatorial interpretation for the sequence $(F_n + n)_{n=1}^\infty$. Next, we give a bijective proof for the recurrence of the sequence $(|\mathcal{K}_{n, p, q}|)_{n=1}^\infty$ (for fixed $p\ge 1$ and $q\ge 2$), where $\mathcal{K}_{n, p, q} = $ $$\{A\subset \{1, \ldots, n\}\,:\, \mbox{either }A = \emptyset \mbox{ or } (\max A-\max_2 A = p\mbox{ and }\min A\ge |A|\ge q)\}$$ and $\max_2 A$ is the second largest integer in $A$, given that $|A|\ge 2$. Note that by definition, $\mathcal{K}_{n, 1, 2} = \mathcal{K}_{n}$ for all $n\ge 1$.