Journal of Integer Sequences, Vol. 22 (2019), Article 19.6.5

The Fibonacci Sequence and Schreier-Zeckendorf Sets

Hùng Việt Chu
Department of Mathematics
University of Illinois at Urbana-Champaign
Champaign, IL 61820


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

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequence A000045.)

Received June 26 2019; revised version received August 31 2019; September 2 2019. Published in Journal of Integer Sequences, September 3 2019.

Return to Journal of Integer Sequences home page