The Fibonacci Sequence and Schreier-Zeckendorf Sets

A finite subset of the natural numbers is weak-Schreier if min S >= vertical bar S vertical bar, strong-Schreier if min S > vertical bar S vertical bar, and maximal if min S = vertical bar S vertical bar. Let M-n be the number of weak-Schreier sets with n being the largest element and (F-n)(n) >=-1 denote the Fibonacci sequence. A finite set is said to be Zeckcndorf if it does not contain two consecutive natural numbers. Let E-n be the number of Zeckendorf subsets of {1, 2, ..., n}. It is well-known that E-n = Fn+2. In this paper, we first show four other ways to generate the Fibonacci sequence from counting Schreier sets. For example, let C-n be the number of weak-Schreier subsets of {1,2, ..., n}. Then C-n = Fn+2. To understand why C-n = E-n, 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.