The Fibonacci Sequence and Schreier-Zeckendorf Sets

Hùng Vi{ê \atop .}t Chu

Department of Mathematics University of Illinois at Urbana-Champaign Champaign, IL 61820 USA

                 hungchu2@illinois.edu

Abstract

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_{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 Zeckendorf 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} = 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, …, 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, …, n} such that two consecutive elements in increasing order always differ by an odd number.

1 Background and main results

Let the Fibonacci sequence be F_{−1} = 1, F_{0} = 0, and F_{m} = F_{m−1} + F_{m−2} for all m ≥ 1. We only concern ourselves with finite subsets of natural numbers greater than 0 and use ℕ for the set {1, 2, 3, …}. We define a set to be

• weak-Schreier if min S ≥ |S|, • strong-Schreier if min S > |S| and

• maximal if min S = |S|,

where |S| is the cardinality of set S. Schreier sets are named after Schreier who defined them to solve a problem in Banach space theory in 1930 [10]. These sets were also independently discovered in combinatorics and are connected to Ramsey-type theorems for subsets of ℕ. For each n ∈ ℕ, let M_{n} be the number of weak-Schreier sets with n being the largest element. In notation,

M_{n} = |{S ⊆ ℕ : min S ≥ |S| and max S = n}|.

The first few values of M_{n} are 1, 1, 2, 3, 5, 8, 13, 21, 34, …; indeed, it is known that M_{n} = F_{n} for all n [12]. However, the author is unable to locate the first person to prove this result. If we look at either strong-Schreier sets or maximal sets instead, we can also generate the Fibonacci sequence. Let

• A_{n} be the number of strong-Schreier sets S with max S = n,

• B_{n} be the number of maximal sets S with max S = n,

• C_{n} be the number of weak-Schreier subsets of {1, 2, …, n} (including the empty set),

• D_{n} be the number of strong-Schreier subsets of {1, 2, …, n} (including the empty set).

For our sequence (C_{n})_{n≥1} and (D_{n})_{n≥1}, we relax the condition about the maximum of our sets. Clearly, for each n ∈ ℕ, M_{n} = A_{n} + B_{n}, C_{n} = ∑_{k=1}^{n} M_{k} + 1 and D_{n} = ∑_{k=1}^{n} A_{n} + 1.

Theorem 1. For each n ∈ ℕ, we have A_{n} = F_{n−1}, B_{n} = F_{n−2}, C_{n} = F_{n+2} and D_{n} = F_{n+1}

The Fibonacci representation of natural numbers was first studied by Ostrowski [9] and Lekkerkerker [8]. In 1972, Zeckendorf proved that every positive integer can be uniquely written as a sum of non-consecutive Fibonacci numbers [11]. Since then, many papers have generalized this result and explored properties of the Zeckendorf decomposition: see [1, 2, 3, 4, 5, 6, 8]. We instead focus on the important requirement for uniqueness of the Zeckendorf decomposition; that is, our set contains no two consecutive Fibonacci numbers. We give the same definition for natural numbers.

Definition 2. A finite set of natural numbers is Zeckendorf if the set does not contain two consecutive natural numbers.

Let E_{n} be the number of subsets of {1, 2, …, n} that satisfy the Zeckendorf condition. It is well-known that E_{n} = F_{n+2}.

Two different ways of counting subsets of {1, 2, …, n} give the same number; that is, C_{n} = E_{n}. To understand the connection, we construct a bijective mapping to show that C_{n} = E_{n} directly. Our proof is independent of the fact that C_{n} = E_{n} = F_{n+2} and thus, provides insight into the seemingly mysterious equality.

Theorem 3. For each n ∈ ℕ, C_{n} = E_{n}.

Next, a natural question is about sequences formed by the number of sets that satisfy both the Schreier and the Zeckendorf conditions. In particular, we say that a set satisfies the k-Zeckendorf condition if two arbitrary numbers in the set are at least k apart. We discover linear recurrence relations among the number of sets satisfying both the Schreier and the k-Zeckendorf conditions.

For each n ∈ ℕ, let H_{k,n} be the number of subsets of {1, 2, …, n} that

(1) satisfy the k-Zeckendorf condition;

(2) contain n; and

(3) are weak-Schreier.

Theorem 4. Fix k ∈ ℕ_{≥2}. We have

H_{k,n} = \begin{cases}1, & if 1 ≤ n ≤ k + 1; \\ H_{k,n−1} + H_{k,n−(k+1)}, & if n > k + 1. \end{cases}

Using the exact same argument as in the proof of Theorem 4, we can also deduce the following theorems regarding strong and maximal Schreier sets. For each n ∈ ℕ, let I_{k,n} be the number of subsets of {1, 2, …, n} that (1) satisfy the k-Zeckendorf condition, (2) contain n, and (3) are strong-Schreier.

Theorem 5. Fix k ∈ ℕ_{≥2}. We have

I_{k,n} = \begin{cases}0, & if n = 1; \\ 1, & if 2 ≤ n ≤ k + 2; \\ I_{k,n−1} + I_{k,n−(k+1)}, & if n > k + 2. \end{cases}

For each n ∈ ℕ, let J_{k,n} be the number of subsets of {1, 2, …, n} that

(1) satisfy the k-Zeckendorf condition;

(2) contain n; and

(3) are maximal.

Theorem 6. Fix k ∈ ℕ_{≥2}. We have

J_{k,n} = \begin{cases}1, & if n = 1; \\ 0, & if 2 ≤ n ≤ k + 1; \\ 1, & if k + 1 < n ≤ 2k + 2; \\ J_{k,n−1} + J_{k,n−(k+1)}, & if n > 2k + 2. \end{cases}

We give the following definition that is useful for the statement of our last result.

Definition 7. Let A = {a_{1}, a_{2}, …, a_{k}} (a_{1} < a_{2} < ⋯ < a_{k}) for some k ∈ ℕ_{≥2}. The difference set of A is {a_{2} − a_{1}, a_{3} − a_{2}, …, a_{k} − a_{k−1}}. The empty set and a set with exactly one element do not have a difference set.

We end with the following small result.

Theorem 8. Fix n ∈ ℕ. The number of subsets of {1, 2, …, n}

1. that contain n and whose difference sets contain only odd numbers is F_{n+1},

2. whose difference sets contain only odd numbers (the empty set and sets with exactly one element vacuously satisfy this requirement) is F_{n+3} − 1.

2 Proof of Theorem 1

Proof of Theorem 1. We first prove item (1). Simple computation gives A_{1} = 0 = F_{0}, A_{2} = 1 = F_{1}, A_{3} = 1 = F_{2}, A_{4} = 2 = F_{3}, and A_{5} = 3 = F_{4}. It suffices to prove that A_{n} + A_{n+1} = A_{n+2} for n ≥ 4. Fix n ≥ 4 and let us find a formula for A_{n}. The minimum number k in our sets can take values from 1 to n. For each value of k, there are n − k − 1 numbers strictly between k and n. Because our sets are strong-Schreier, they contain at most k − 3 numbers out of these n − k − 1 numbers. Hence, our formula for A_{n} is

A_{n} = ∑_{k=1}^{n−1} ∑_{j=0}^{k−3} \binom{n − k − 1}{j} + 1.

Note that the number 1 in our formula accounts for the set {n}. It remains to show that A_{n} + A_{n+1} = A_{n+2} or equivalently, A_{n+2} − A_{n+1} = A_{n} for n ≥ 4. We have

A_{n+2} − A_{n+1} = ∑_{k=1}^{n+1} ∑_{j=0}^{k−3} \binom{n − k + 1}{j} − ∑_{k=1}^{n} ∑_{j=0}^{k−3} \binom{n − k}{j}

= ∑_{k=1}^{n} ∑_{j=0}^{k−3} (\binom{n − k + 1}{j} − \binom{n − k}{j}) + ∑_{j=0}^{n−2} \binom{0}{j}

= ∑_{k=1}^{n} ∑_{j=1}^{k−3} \binom{n − k}{j − 1} + 1.

Therefore,

A_{n+2} − A_{n+1} − A_{n} = ∑_{k=1}^{n} ∑_{j=1}^{k−3} \binom{n − k}{j − 1} − ∑_{k=1}^{n−1} ∑_{j=0}^{k−3} \binom{n − k − 1}{j}

= ∑_{k=4}^{n} ∑_{j=1}^{k−3} \binom{n − k}{j − 1} − ∑_{k=3}^{n−1} ∑_{j=0}^{k−3} \binom{n − k − 1}{j} = 0.

The last equality is because for each 4 ≤ t ≤ n, we have ∑_{j=1}^{t−3} \binom{n−t}{j−1} = ∑_{j=0}^{(t−1)−3} \binom{n−(t−1)−1}{j}. Hence, A_{n+2} = A_{n+1} + A_{n} and we are done.

Next, we prove item (2), which follows immediately from item (1). We know that

B_{n} = M_{n} − A_{n} = F_{n} − F_{n−1} = F_{n−2}.

We prove item (3). Fix n ≥ 1. We have

C_{n} = ∑_{k=1}^{n} M_{k} + 1 = ∑_{k=1}^{n} F_{k} + 1 = (F_{n+2} − 1) + 1 = F_{n+2},

as desired. The number 1 accounts for the empty set. The fact that ∑_{k=1}^{n} F_{k} = F_{n+2} − 1 is due to Lucas [7, p. 4].

Similarly, we prove item (4). Fix n ≥ 1. We have

D_{n} = ∑_{k=1}^{n} A_{k} + 1 = ∑_{k=1}^{n} F_{k−1} + 1 = (F_{n+1} − 1) + 1 = F_{n+1}.

We complete our proof of Theorem 1.

Let L_{n}^{w} be the number of weak-Schreier sets as subsets of {1, 2, …, n} with an even maximum.

Corollary 9. For each n ∈ ℕ,

L_{n}^{w} = \begin{cases}F_{n}, & if n is odd; \\ F_{n+1}, & if n is even. \end{cases}

Proof. We have

L_{n}^{w} = ∑_{{1≤k≤n \atop 2|k}} M_{k} + 1 = ∑_{{1≤k≤n \atop 2|k}} F_{k} + 1.

The number 1 accounts for the empty set.

If n is even,

L_{n}^{w} = ∑_{{1≤k≤n \atop 2|k}} F_{k} + 1 = (F_{n+1} − 1) + 1 = F_{n+1}.

If n is odd,

L_{n}^{w} = ∑_{{1≤k≤n \atop 2|k}} F_{k} + 1 = (F_{n} − 1) + 1 = F_{n}.

Let L_{n}^{s} be the number of strong-Schreier sets as subsets of {1, 2, …, n} with an odd maximum.

Corollary 10. For each n ∈ ℕ,

L_{n}^{s} = \begin{cases}F_{n}, & if n is odd; \\ F_{n−1}, & if n is even. \end{cases}

Proof. We have

L_{n}^{s} = ∑_{{1≤k≤n \atop 2∤k}} A_{k} + 1 = ∑_{1≤k≤n,2∤k} F_{k−1} + 1.

If n is even,

L_{n}^{s} = ∑_{{1≤k≤n \atop 2∤k}} F_{k−1} + 1 = (F_{n−1} − 1) + 1 = F_{n−1}.

If n is odd,

L_{n}^{s} = ∑_{{1≤k≤n \atop 2∤k}} F_{k−1} + 1 = (F_{n} − 1) + 1 = F_{n}.

3 Proof of Theorem 3 — Explanation of the mysterious identity

Recall that C_{n} is the number of weak-Schreier sets as subsets of {1, 2, …, n}, while E_{n} is the number of subsets of {1, 2, …, n} that do not contain two consecutive numbers. At the first glance, C_{n} and E_{n} are little related, so it is surprising to see that C_{n} = E_{n} for all n ∈ ℕ.

For each n ∈ ℕ, let X_{n} denote the set of weak-Schreier sets as subsets of {1, 2, …, n} and let Y_{n} denote the set of subsets of {1, 2, …, n} that do not contain two consecutive numbers. In this section, we construct a bijective function f : X_{n} → Y_{n} to prove that |X_{n}| = |Y_{n}|.

Proof of Theorem 3. Fix n ∈ ℕ. Let A = {a_{1}, a_{2}, …, a_{k−1}, a_{k}} (a_{1} < a_{2} < ⋯ < a_{k}) be a weak-Schreier subset of {1, 2, …, n}. Our mapping f acts on A as follows

f(A) = f({a_{1}, a_{2}, …, a_{k−1}, a_{k}}) = {a_{1} − (k − 1), a_{2} − (k − 2), …, a_{k−1} − 1, a_{k}}.

Define f(∅) = ∅. To show that f is well-defined, we show that {a_{1} − (k − 1), a_{2} − (k − 2), …, a_{k−1} − 1, a_{k}} is in Y_{n}. Because A is weak-Schreier, k ≤ a_{1} < a_{2} < ⋯ < a_{k}. Hence,

1 ≤ a_{1} − (k − 1) < a_{2} − (k − 2) < ⋯ < a_{k−1} − 1 < a_{k} ≤ n.

Let t_{i} = a_{i} − (k − i) for 1 ≤ i ≤ k. If k = 1, then {t_{1}} is clearly in Y_{n}. If k ≥ 2, then for each 2 ≤ i ≤ k, we have

t_{i} − t_{i−1} = (a_{i} − (k − i)) − (a_{i−1} − (k − (i − 1))) = (a_{i} − a_{i−1}) + 1 ≥ 2.

Therefore, {t_{1}, t_{2}, …, t_{k}} ∈ Y_{n}. So, f is well-defined.

Next, we prove that f is injective. Suppose that f(A) = f(B). Let A = {a_{1}, a_{2}, …, a_{k}} and B = {b_{1}, b_{2}, …, b_{k}}, where a_{1} < a_{2} < ⋯ < a_{k} and b_{1} < b_{2} < ⋯ < b_{k}. Because

a_{1} − (k − 1) < a_{2} − (k − 2) < ⋯ < a_{k−1} − 1 < a_{k},
b_{1} − (k − 1) < b_{2} − (k − 2) < ⋯ < b_{k−1} − 1 < b_{k},

we know that f(A) = f(B) implies a_{i} − (k − i) = b_{i} − (k − i) for all 1 ≤ i ≤ k. Hence, a_{i} = b_{i}, which shows that A = B. Therefore, f is injective.

Finally, we prove that f is surjective. Let C = {c_{1}, c_{2}, …, c_{k}} ∈ Y_{n} be chosen, where c_{1} < c_{2} < ⋯ < c_{k}. We claim that

D = {c_{1} + (k − 1), c_{2} + (k − 2), …, c_{k−1} + 1, c_{k}}

satisfies f(D) = C and D ∈ X_{n}. Because C do not contain two consecutive numbers, we know that

k ≤ c_{1} + (k − 1) < c_{2} + (k − 2) < ⋯ < c_{k−1} + 1 < c_{k} ≤ n.

Hence, D ∈ X_{n}.

We have shown that f is both well-defined and bijective. Therefore, |X| = |Y | or C_{n} = E_{n}, as desired.

Remark 11. We would like to discuss the motivation for the bijection f used in the proof of Theorem 3. Let A be a Schreier set. The map f serves to increase the gap between adjacent elements of A by 1, thus fulfilling the Zeckendorf condition that adjacent elements differ by at least 2. Furthermore, the weak-Schreier condition that min A ≥ |A| ensures that the resulting set is in {1, 2, …, n}.

4 Proof of Theorem 4

Before we prove Theorem 4, we need a simple proposition. Proposition 12. For n, k ∈ ℤ, the following claims hold.

1. If ⌊\frac{n−2}{k+1}⌋ = ⌊\frac{n−k−2}{k+1}⌋, then ⌊\frac{n−1}{k+1}⌋ = ⌊\frac{n−2}{k+1}⌋ + 1.

2. If ⌊\frac{n−2}{k+1}⌋ > ⌊\frac{n−k−2}{k+1}⌋, then ⌊\frac{n−1}{k+1}⌋ < ⌊\frac{n−2}{k+1}⌋ + 1.

3. If ⌊\frac{n−k−2}{k+1}⌋ = ⌊\frac{n−2}{k+1}⌋, then \frac{n−k−2}{k+1} = ⌊\frac{n−2}{k+1}⌋. Proof. We prove claim (1). We have

⌊\frac{n − 2}{k + 1}⌋ = ⌊\frac{n − k − 2}{k + 1}⌋ = ⌊\frac{n − 1}{k + 1} − 1⌋ = ⌊\frac{n − 1}{k + 1}⌋ − 1.

Therefore,

⌊\frac{n − 1}{k + 1}⌋ = ⌊\frac{n − 2}{k + 1}⌋ + 1.

Next, we prove claim (2). We have

⌊\frac{n − 2}{k + 1}⌋ > ⌊\frac{n − k − 2}{k + 1}⌋ = ⌊\frac{n − 1}{k + 1} − 1⌋ = ⌊\frac{n − 1}{k + 1}⌋ − 1.

Therefore,

⌊\frac{n − 1}{k + 1}⌋ < ⌊\frac{n − 2}{k + 1}⌋ + 1.

Lastly, we prove claim (3). Write n − k − 2 = (k + 1)p + q for some 0 ≤ q ≤ k. Then

\frac{n − 2}{k + 1} = \frac{(k + 1)p + q + k}{k + 1} = p + \frac{q + k}{k + 1} = p + 1 + \frac{q − 1}{k + 1}.

If q ≥ 1, then ⌊\frac{n−2}{k+1}⌋ = p + 1 > p = ⌊\frac{n−k−2}{k+1}⌋, a contradiction. So, q = 0, implying that \frac{n−k−2}{k+1} = ⌊\frac{n−2}{k+1}⌋.

The following lemma is from [6, Lemma 2.1] by Kologlǔ et al. Lemma 13. The number of solutions to y_{1}+⋯+y_{p} = n with y_{i} ≥ c_{i} (each c_{i} a non-negative integer) is \binom{n−(c_{1}+···+c_{p})+p−1}{p−1}. Proof of Theorem 4. Fix k ≥ 2. We now find a formula for H_{k,n} for all n ∈ ℕ. Fix 1 ≤ ℓ ≤ n − 1. Suppose that the set {a_{1}, …, a_{ℓ}, n} satisfies all of our requirements. (For ℓ = 0, we have the set {n}.) In particular,

1. a_{1} ≥ ℓ + 1,

2. d_{i} = a_{i+1} − a_{i} ≥ k and d_{ℓ} = n − a_{ℓ} ≥ k.

Note that

a_{1} + ∑_{i=1}^{ℓ} d_{i} = n.  (1)

By Lemma 13, the number of sets satisfying Equation (1) is

\binom{n − (ℓ + 1 + kℓ) + (ℓ + 1) − 1}{(ℓ + 1) − 1} = \binom{n − kℓ − 1}{ℓ}.

Therefore, the number of sets containing n that are k-Zeckendorf and weak-Schreier is

H_{k,n} = \begin{matrix}⌊ & \frac{n−1}{k+1} & ⌋ \\ ∑ \\ ℓ=1 \end{matrix} \binom{n − kℓ − 1}{ℓ} + 1.

The number 1 accounts for the set \{n\} and we only let ℓ run up to ⌊\frac{n−1}{k+1}⌋ to make sure that n − kℓ − 1 ≥ ℓ. It can be easily verified that H_{k,n} = 1 for 1 ≤ n ≤ k + 1 because ⌊\frac{n−1}{k+1}⌋ = 0 for 1 ≤ n ≤ k + 1. It suffices to show that for n ≥ k + 2, H_{k,n} = H_{k,n−1} + H_{k,n−(k+1)}. Equivalently,

\begin{matrix}⌊ & \frac{n−1}{k+1} & ⌋ \\ ∑ \\ ℓ=1 \end{matrix} \binom{n − kℓ − 1}{ℓ} = \begin{matrix}⌊ & \frac{n−2}{k+1} & ⌋ \\ ∑ \\ ℓ=1 \end{matrix} \binom{n − kℓ − 2}{ℓ} + \begin{aligned}⌊ & \frac{n−(k+1)−1}{k+1} & ⌋ \\ & ∑ \\ & ℓ=1 \end{aligned} \binom{n − kℓ − 1 − (k + 1)}{ℓ} + 1. (2)

Equivalently, noting that the +1 term cancels with the l = 1 term in the left hand side summation

\begin{matrix}⌊ & \frac{n−2}{k+1} & ⌋ \\ ∑ \\ ℓ=2 \end{matrix} (\binom{n − kℓ − 1}{ℓ} − \binom{n − kℓ − 2}{ℓ}) + \begin{matrix}⌊ & \frac{n−1}{k+1} & ⌋ \\ ∑ \\ ⌊\frac{n−2}{k+1}⌋+1 \end{matrix} \binom{n − kℓ − 1}{ℓ}  (3)

= \begin{aligned}⌊ & \frac{n−k−2}{k+1} & ⌋ \\ & ∑ \\ & ℓ=1 \end{aligned} \binom{n − k(ℓ + 1) − 2}{ℓ}.

We can simplify Equation (3) further by applying the binomial coefficient recurrence

\begin{matrix}⌊ & \frac{n−2}{k+1} & ⌋ \\ ∑ \\ ℓ=2 \end{matrix} \binom{n − kℓ − 2}{ℓ − 1} + \begin{matrix}⌊ & \frac{n−1}{k+1} & ⌋ \\ ∑ \\ ⌊\frac{n−2}{k+1}⌋+1 \end{matrix} \binom{n − kℓ − 1}{ℓ} = \begin{aligned}⌊ & \frac{n−k−2}{k+1} & ⌋ \\ & ∑ \\ & ℓ=1 \end{aligned} \binom{n − k(ℓ + 1) − 2}{ℓ}.

Reindexing ℓ in the first summation, we have

⌊\frac{n−2}{k+1}⌋−1 ; ∑ ; ℓ=1 \binom{n − k(ℓ + 1) − 2}{ℓ} + \begin{matrix}⌊ & \frac{n−1}{k+1} & ⌋ \\ ∑ \\ ⌊\frac{n−2}{k+1}⌋+1 \end{matrix} \binom{n − kℓ − 1}{ℓ} = \begin{aligned}⌊ & \frac{n−k−2}{k+1} & ⌋ \\ & ∑ \\ & ℓ=1 \end{aligned} \binom{n − k(ℓ + 1) − 2}{ℓ}.

Subtract the first summation from both sides to have

\begin{matrix}⌊ & \frac{n−1}{k+1} & ⌋ \\ ∑ \\ ⌊\frac{n−2}{k+1}⌋+1 \end{matrix} \binom{n − kℓ − 1}{ℓ} = \begin{matrix}⌊ & \frac{n−k−2}{k+1} & ⌋ \\ ∑ \\ ℓ=⌊\frac{n−2}{k+1}⌋ \end{matrix} \binom{n − k(ℓ + 1) − 2}{ℓ}.  (4)

We now prove that Equation (4) is correct, which implies that Equation (2) is correct.

Case 1: ⌊\frac{n−k−2}{k+1}⌋ < ⌊\frac{n−2}{k+1}⌋. Then ⌊\frac{n−2}{k+1}⌋ + 1 > ⌊\frac{n−1}{k+1}⌋ by Proposition 12. Therefore, two sides of Equation (4) are identically 0.

Case 2: ⌊\frac{n−k−2}{k+1}⌋ = ⌊\frac{n−2}{k+1}⌋. Then ⌊\frac{n−2}{k+1}⌋ + 1 = ⌊\frac{n−1}{k+1}⌋ and \frac{n−k−2}{k+1} = ⌊\frac{n−2}{k+1}⌋ by Proposition 12. Therefore, the left side of Equation (4) is

\binom{n − k(⌊\frac{n−2}{k+1}⌋ + 1) − 1}{⌊\frac{n−2}{k+1}⌋ + 1} = 1

because \frac{n−k−2}{k+1} = ⌊\frac{n−2}{k+1}⌋. Similarly, the right side is also equal to 1.

In both cases, Equation (4) is correct. This completes our proof.

5 Proof of Theorem 8—A new way to generate the Fibonacci sequence

Proof of Theorem 8. First, we prove item (1). Let P_{n} be the number of subsets of {1, 2, …, n} that contain n and whose difference sets contain only odd numbers.

Base cases: For n = 1, we have {1} to be the only subset of {1} that satisfies our requirement. So, P_{1} = 1 = F_{2}. For n = 2, we have {2} and {1, 2} to be the only two subsets of {1, 2} that satisfy our requirement. So, P_{2} = 2 = F_{3}.

Inductive hypothesis: Suppose that there exists k ≥ 2 such that for all n ≤ k, P_{n} = F_{n+1}. We show that P_{k+1} = F_{k+2}. Let O_{n} denote the set of subsets of {1, 2, …, n} that satisfy our requirement. Observe that unioning a set in O_{n−1−2i} (for i ≥ 0) with n produces a set in O_{n} and any set in O_{n} is of the form of a set in O_{n−1−2i} plus the element n. Therefore,

P_{k+1} = |O_{k+1}| = ∑_{{1≤i≤k \atop 2∤i}} |O_{k+1−i}| + 1 = P_{k} + ∑_{{3≤i≤k \atop 2∤i}} |O_{k+1−i}| + 1.

The number 1 accounts for the set {n}. If k is odd,

∑_{{3≤i≤k \atop 2∤i}} |O_{k+1−i}| = |O_{1}| + |O_{3}| + ⋯ + |O_{k−2}|

= |F_{2}| + |F_{4}| + ⋯ + |F_{k−1}| = F_{k} − 1 = P_{k−1} − 1.

If k is even,

∑_{{3≤i≤k \atop 2∤i}} |O_{k+1−i}| = |O_{2}| + |O_{4}| + ⋯ + |O_{k−2}|

= |F_{3}| + |F_{5}| + ⋯ + |F_{k−1}| = F_{k} − 1 = P_{k−1} − 1.

In both cases, we have ∑_{{3≤i≤k \atop 2∤i}} |O_{k+1−i}| = P_{k−1} − 1. Therefore, P_{k+1} = P_{k} + P_{k−1} = F_{k+1} + F_{k} = F_{k+2}, as desired.

Next, we prove item (2). Let Q_{n} be the number of subsets of {1, 2, …, n} whose difference sets contain only odd numbers is Q_{n} (the empty set and sets with exactly one element vacuously satisfy this requirement). Note that by definition of P_{n} and Q_{n}, we have

Q_{n} = 1 + ∑_{k=1}^{n} |P_{k}| = 1 + ∑_{k=1}^{n} F_{k+1} = ∑_{k=1}^{n+1} F_{k} = F_{n+3} − 1,

as desired. (The +1 before the first summation accounts for the empty set.)

6 Acknowledgments

The author would like to thank the anonymous referee and the editor for various helpful comments that clarify several points made in this paper. Thanks to Kevin Beanland at Washington and Lee University for useful comments on earlier drafts.

References

[1] E. Burger, D. Clyde, C. Colbert, G. Shin, and Z. Wang, Canonical diophantine representations of natural numbers with respect to quadratic “bases”, J. Number Theory 133 (2013), 1372–1388.

[2] O. Beckwith, A. Bower, L. Gaudet, R. Insoft, S. Li, S. Miller, and P. Tosteson, The average gap distribution for generalized Zeckendorf decompositions, Fibonacci Quart. 51 (2013), 13–27.

[3] A. Best, P. Dynes, X. Edelsbrunner, B. McDonald, S. Miller, C. Turnage-Butterbaugh, and M. Weinstein, Benford behavior of Zeckendorf decompositions, Fibonacci Quart. 52 (2014), 35–46.

[4] P. Demontigny, T. Do, A. Kulkarni, S. Miller, D. Moon, and U. Varma, Generalizing Zeckendorf’s theorem to f-decompositions, J. Number Theory 141 (2014), 136–158.

[5] T. J. Keller, Generalizations of Zeckendorf’s theorem, Fibonacci Quart. 10 (1972), 95– 102.

[6] G. S. Kopp, M. Kologlu, S. Miller, and Y. Wang, On the number of summands in Zeckendorf decompositions, Fibonacci Quart. 49 (2011), 116–130.

[7] E. Lucas. Theorie Des Nombres, Gauthier-Villars, 1891.

[8] C. G. Lekkerkerker, Voorstelling van natuurlyke getallen door een som van getallen van Fibonacci, Simon Stevin 29 (1951–1952), 190–195.

[9] A. Ostrowski, Bemerkungen zur Theorie der diophantischen Approximationen, Hambg. Abh. 1 (1922), 77–98.

[10] J. Schreier, Ein Gegenbeispiel zur Theorie der schwachen Konvergentz, Studia Math. 2 (1962), 58–62.

[11] E. Zeckendorf, Representation des nombres naturels par une somme de nombres de Fibonacci ou de nombres de Lucas, Bull. Soc. Roy. Sci. Liege 41 (1972), 179–182.

[12] Unknown author, Jozef Schreier, Schreier sets and the Fibonacci sequence,

2012. Available at https://outofthenormmaths.wordpress.com/2012/05/13/
jozef-schreier-schreier-sets-and-the-fibonacci-sequence/.

2010 Mathematics Subject Classification: 11B39. Keywords: Fibonacci sequence, linear recurrence, combinatorics, Schreier set.

(Concerned with sequences \underline{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.