The Fibonacci Sequence and Schreier-Zeckendorf Sets

Abstract

A finite subset of the natural numbers is weak-Schreier if $\min S\ge |S|$, strong-Schreier if $\min S>|S|$, and maximal if $\min S=|S|$. Let $M_n$ be the number of weak-Schreier sets with $n$ being the largest element and $(F_n{)}_{n\ge -1}$ denote the Fibonacci sequence. A finite set is said to be Zeckendorf if it does not contain two consecutive natural numbers. Let $E_n$ be the number of Zeckendorf subsets of $\{1,2,\dots ,n\}$. It is well-known that $E_n=F_{n+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,\dots ,n\}$. Then $C_n=F_{n+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,\dots ,n\}$ such that two consecutive elements in increasing order always differ by an odd number.

12 pages, published in J. Integer Seq; In the reference, I added A. Bird as the author of a blog post mentioned in the paper

References in corpus (3)

• Generalizing Zeckendorf's Theorem to f-decompositions
• On the number of summands in Zeckendorf decompositions
• The Average Gap Distribution for Generalized Zeckendorf Decompositions