The Fibonacci Sequence and Schreier-Zeckendorf Sets

A finite subset of the natural numbers is weak-Schreier if min S ≥ |S|, strong-Schreier if min S>|S|, and maximal if min S = |S|. Let Mₙ be the number of weak-Schreier sets with n being the largest element and (Fₙ)n≥ -1 denote the Fibonacci sequence. A finite set is said to be Zeckendorf if it does not contain two consecutive natural numbers. Let Eₙ be the number of Zeckendorf subsets of \1,2,…,n\. It is well-known that Eₙ = Fₙ₊₂. In this paper, we first show four other ways to generate the Fibonacci sequence from counting Schreier sets. For example, let Cₙ be the number of weak-Schreier subsets of \1,2,…,n\. Then Cₙ = Fₙ₊₂. To understand why Cₙ = Eₙ, we provide a bijective mapping to prove the equality directly. Next, we prove linear recurrence relations among the number of Schreier-Zeckendorf sets. Lastly, we discover the Fibonacci sequence by counting the number of subsets of \1,2,…, n\ such that two consecutive elements in increasing order always differ by an odd number.