Linear Recurrences of Generalized Schreier Sets Revisited

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

Department of Mathematics Washington and Lee University Lexington, VA 24450 USA

                     hchu@wlu.edu

Zachary Louis Vasseur Department of Mathematics Texas A&M University College Station, TX 77843 USA

                 zachary.l.v@tamu.edu

Abstract

For p, q ∈ ℕ, a finite nonempty set F is said to be (p, q)-Schreier (or maximal (p, q)- Schreier, respectively) if q min F ≥ p|F | (or q min F = p|F |, respectively). Using the inclusion-exclusion principle, Beanland et al. proved a linear recurrence for the counts of (p, q)-Schreier sets of the natural numbers. We show that the counts are taken periodically from Padovan-like sequences that satisfy simple recurrence relations. As an application, we obtain an alternative proof of Beanland et al.’s result. Furthermore, a similar result holds for the counts of maximal (p, q)-Schreier sets. We end with a discussion of the relation between (p, q)-Schreier and maximal (p, q)-Schreier sets.

1 Introduction

A finite nonempty subset F of natural numbers is called Schreier if min F ≥ |F | and is called maximal Schreier if min F = |F |. Bird [3] observed that for all n ≥ 1, we have

|{F ⊂ ℕ : F is Schreier and max F = n}| = F_{n},  (1)

where F_{n} is the n^{th} Fibonacci number defined as F_{−1} = 1, F_{0} = 0 and F_{m} = F_{m−1} + F_{m−2} for m ≥ 1. Similarly, [4, Theorem 1] states that

|{F ⊂ ℕ : F is maximal Schreier and max F = n}| = F_{n−2}, for all n ≥ 1.  (2)

Previous work has generalized these results in various directions: Beanland et al. studied the more general condition q min F ≥ p|F | and discovered linear recurrences of higher order; Chu et al. [5] connected Schreier multisets to higher-order Fibonacci sequences; more recently, Beanland et al. [2] counted unions of Schreier sets and provided a family of recursively defined sequences.

A set F of natural numbers is said to be (p, q)-Schreier (or maximal (p, q)-Schreier, respectively) if q min F ≥ p|F | (or q min F = p|F |, respectively). Let us recall [1, Theorem 1.1], which states that if

S_{n}^{p/q} := {F ⊂ ℕ : F is (p, q)-Schreier and max F = n}, with p, q, n ∈ ℕ,

then

|S_{n}^{p/q}| = ∑_{i=1}^{q}(−1)^{i+1}\binom{q}{i}|S_{n−i}^{p/q}| + |S_{n−(p+q)}^{p/q}|.  (3)

Continuing the work of Beanland et al. [1], we investigate the family of sequences (|S_{n}^{p/q}|)_{n=1}^{∞}. While (|S_{n}^{1/3}|)_{n=1}^{∞} and (|S_{n}^{1/4}|)_{n=1}^{∞} were only recently added by the authors of the present paper to the On-Line Encyclopedia of Integer Sequences (OEIS) [6], these sequences are not far from the existing ones. Our main result shows that each (|S_{n}^{p/q}|)_{n=1}^{∞} is a subsequence of a Padovan-like sequence whose linear recurrence is much simpler than (3). This relation reveals an alternative proof of (3), which employs characteristic polynomials instead of the inclusion-exclusion principle.

We are also interested in maximal (p, q)-Schreier sets: let

M_{n}^{p/q} := {F ⊂ ℕ : F is maximal (p, q)-Schreier and max F = n}, with p, q, n ∈ ℕ.

Tables 1 and 2 collect the initial values of (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} for different (p, q)’s.

Keen observation reveals that the terms of (|S_{n}^{p/q}|)_{n=1}^{∞} are periodically taken from certain Padovan-like sequences. For (p, q) ∈ ℕ^{2} with p ≥ q, define the sequence (a_{p,q,n})_{n=0}^{∞} (Table 3) as follows:

a_{p,q,0} = ⋯ = a_{p,q,p−q−1} = 0,
a_{p,q,p−q} = ⋯ = a_{p,q,p+q−1} = 1, and
a_{p,q,n} = a_{p,q,n−q} + a_{p,q,n−p−q}, for n ≥ p + q.

If p < q, let

a_{p,q,0} = ⋯ = a_{p,q,2p−1} = 1,
a_{p,q,2p} = ⋯ = a_{p,q,p+q−1} = 2, and
a_{p,q,n} = a_{p,q,n−q} + a_{p,q,n−p−q}, for n ≥ p + q.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ |S_{n}^{1/1}| & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 \\ |S_{n}^{1/2}| & 1 & 2 & 3 & 5 & 9 & 16 & 28 & 49 & 86 & 151 & 265 & 465 & 816 & 1432 & 2513 \\ |S_{n}^{1/3}| & 1 & 2 & 4 & 7 & 12 & 21 & 38 & 70 & 129 & 236 & 429 & 778 & 1412 & 2567 & 4672 \\ |S_{n}^{1/4}| & 1 & 2 & 4 & 8 & 15 & 27 & 48 & 86 & 157 & 292 & 549 & 1034 & 1939 & 3613 & 6697 \\ |S_{n}^{2/1}| & 0 & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19 & 28 & 41 & 60 & 88 \\ |S_{n}^{2/3}| & 1 & 1 & 2 & 4 & 7 & 12 & 20 & 33 & 55 & 93 & 159 & 273 & 468 & 799 & 1359 \end{matrix}

Table 1: The first 15 values of (|S_{n}^{p/q}|)_{n=1}^{∞} with different values of (p, q). The sequences (|S_{n}^{1/1}|)_{n=1}^{∞}, (|S_{n}^{1/2}|)_{n=1}^{∞}, (|S_{n}^{2/1}|)_{n=1}^{∞}, and (|S_{n}^{2/3}|)_{n=1}^{∞} are \underline{A000045}, \underline{A005314}, \underline{A078012}, and \underline{A099558}, respectively; the sequences (|S_{n}^{1/3}|)_{n=1}^{∞} and (|S_{n}^{1/4}|)_{n=1}^{∞} were newly added as \underline{A385106} and \underline{A385107}, respectively.

\begin{matrix}n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 \\ |M_{n}^{1/1}| & 1 & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 \\ |M_{n}^{1/2}| & 0 & 1 & 1 & 1 & 2 & 4 & 7 & 12 & 21 & 37 & 65 & 114 & 200 & 351 & 616 \\ |M_{n}^{1/3}| & 0 & 0 & 1 & 2 & 3 & 4 & 6 & 11 & 22 & 43 & 80 & 144 & 257 & 462 & 839 \\ |M_{n}^{1/4}| & 0 & 0 & 0 & 1 & 3 & 6 & 10 & 15 & 22 & 35 & 64 & 129 & 265 & 529 & 1013 \\ |M_{n}^{2/1}| & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19 & 28 \\ |M_{n}^{2/3}| & 0 & 0 & 0 & 1 & 2 & 3 & 4 & 5 & 7 & 12 & 23 & 44 & 80 & 138 & 230 \end{matrix}

Table 2: The first 15 values of (|M_{n}^{p/q}|)_{n=1}^{∞} with different values of (p, q). These sequences are \underline{A212804}, \underline{A005251}, \underline{A375169}, \underline{A385142} (newly added), \underline{A078012}, and \underline{A137357}, respectively.

By changing the initial condition of the Padovan-like sequences (a_{p,q,n})_{n=0}^{∞}, we arrive at a similar result for maximal (p, q)-Schreier sets. For (p, q) ∈ ℕ^{2} and p ≥ q, define the sequence (a_{p,q,n}^{(m)})_{n=0}^{∞} (Table 4) recursively as follows:

a_{p,q,0}^{(m)} = ⋯ = a_{p,q,p−q−1}^{(m)} = 0, a_{p,q,p−q}^{(m)} = 1,
a_{p,q,p−q+1}^{(m)} = ⋯ = a_{p,q,p+q−1}^{(m)} = 0, and
a_{p,q,n}^{(m)} = a_{p,q,n−q}^{(m)} + a_{p,q,n−p−q}^{(m)}.

If p < q, then

a_{p,q,0}^{(m)} = ⋯ = a_{p,q,2p−1}^{(m)} = 0, a_{p,q,2p}^{(m)} = 1,
a_{p,q,2p+1}^{(m)} = ⋯ = a_{p,q,p+q−1}^{(m)} = 0, and
a_{p,q,n}^{(m)} = a_{p,q,n−q}^{(m)} + a_{p,q,n−p−q}^{(m)},

where the superscript (m) indicates that these sequences correspond to maximal (p, q)- Schreier sets.

For (p, q) ∈ ℕ^{2} and n ≥ 0, define

Ψ(p, q, n) := \begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i}

and

Φ(p, q, n) := ⌊\frac{n}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2} + \begin{cases}1, & if n = p − q; \\ 0, & otherwise. \end{cases}

We show later that

a_{p,q,n} = Ψ(p, q, n)  (4)

and

a_{p,q,n}^{(m)} = Φ(p, q, n).  (5)

Tables 3 and 4 record the first few values of (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞} for different (p, q)’s.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 \\ a_{1,1,n} & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 & 987 & 1597 \\ a_{1,2,n} & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 & 9 & 12 & 16 & 21 & 28 & 37 & 49 & 65 & 86 \\ a_{1,3,n} & 1 & 1 & 2 & 2 & 2 & 3 & 4 & 4 & 5 & 7 & 8 & 9 & 12 & 15 & 17 & 21 & 27 \\ a_{1,4,n} & 1 & 1 & 2 & 2 & 2 & 2 & 3 & 4 & 4 & 4 & 5 & 7 & 8 & 8 & 9 & 12 & 15 \\ a_{2,1,n} & 0 & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19 & 28 & 41 & 60 & 88 & 129 & 189 \\ a_{2,3,n} & 1 & 1 & 1 & 1 & 2 & 2 & 2 & 3 & 3 & 4 & 5 & 5 & 7 & 8 & 9 & 12 & 13 \end{matrix}

Table 3: The first 17 values of (a_{p,q,n})_{n=0}^{∞} with different values of (p, q). Note that for n ≥ 0, we have a_{1,1,n} = \underline{A000045}(n + 1), a_{1,2,n} = \underline{A000931}(n + 6), a_{1,3,n} = \underline{A079398}(n + 3), a_{1,4,n} = \underline{A103372}(n + 4), a_{2,1,n} = \underline{A078012}(n + 2), and a_{2,3,n} = \underline{A226503}(n + 2).

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 \\ a_{1,1,n}^{(m)} & 1 & 0 & 1 & 1 & 2 & 3 & 5 & 8 & 13 & 21 & 34 & 55 & 89 & 144 & 233 & 377 & 610 & 987 \\ a_{1,2,n}^{(m)} & 0 & 0 & 1 & 0 & 1 & 1 & 1 & 2 & 2 & 3 & 4 & 5 & 7 & 9 & 12 & 16 & 21 & 28 \\ a_{1,3,n}^{(m)} & 0 & 0 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 2 & 1 & 1 & 3 & 3 & 2 & 4 & 6 & 5 \\ a_{1,4,n}^{(m)} & 0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 & 2 & 1 & 0 & 1 & 3 & 3 & 1 \\ a_{2,1,n}^{(m)} & 0 & 1 & 0 & 0 & 1 & 1 & 1 & 2 & 3 & 4 & 6 & 9 & 13 & 19 & 28 & 41 & 60 & 88 \\ a_{2,3,n}^{(m)} & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 2 & 1 & 1 & 3 & 1 & 3 \end{matrix}

Table 4: The first 18 values of (a_{p,q,n}^{(m)})_{n=0}^{∞} with different values of (p, q). For n ≥ 0, we have a_{1,1,n}^{(m)} = \underline{A212804}(n), a_{1,2,n}^{(m)} = \underline{A000931}(n+1), a_{1,3,n+2}^{(m)} = \underline{A017817}(n), a_{1,4,n+2}^{(m)} = \underline{A017827}(n), a_{2,1,n}^{(m)} = \underline{A135851}(n + 1), and a_{2,3,n+4}^{(m)} = \underline{A052920}(n).

Theorem 1. For (p, q, n) ∈ ℕ^{3}, we have

|S_{n}^{p/q}| = a_{p,q,(n−1)q}  (6)

and

|M_{n}^{p/q}| = a_{p,q,(n−1)q}^{(m)}.  (7)

Corollary 2. For (p, q) ∈ ℕ^{2}, the first (p + q) terms of the sequence (|S_{n}^{p/q}|)_{n=1}^{∞} are

|S_{n}^{p/q}| = \begin{aligned}⌊ & \frac{(n+1)q}{p+q} & ⌋ \\ & ∑ \\ & i=1 \end{aligned} \binom{n − ⌈\frac{ni}{q}⌉}{i − 1}, for 1 ≤ n ≤ p + q.

Later terms satisfy the recurrence

|S_{n}^{p/q}| = ∑_{i=1}^{q}(−1)^{i+1}\binom{q}{i}|S_{n−i}^{p/q}| + |S_{n−(p+q)}^{p/q}|, for n ≥ p + q + 1.

Corollary 3. For (p, q) ∈ ℕ^{2}, the first (p + q) terms of the sequence (|M_{n}^{p/q}|)_{n=1}^{∞} are

|M_{n}^{p/q}| = \begin{aligned}⌊ & \frac{n+1}{p′+q′} & ⌋ \\ & ∑ \\ & k=1 \end{aligned} \binom{n − p′k − 1}{q′k − 2},

where p′ = p/ gcd(p, q) and q′ = q/ gcd(p, q). Later terms satisfy the recurrence

|M_{n}^{p/q}| = ∑_{i=1}^{q}(−1)^{i+1}\binom{q}{i}|M_{n−i}^{p/q}| + |M_{n−(p+q)}^{p/q}|, for n ≥ p + q + 1.

Our paper is structured as follows: Section 2 establishes Formulas (4) and (5) for the sequences (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞}; Section 3 proves Theorem 1, which states that (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} are subsequences taken q-periodically out of (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞}, respectively. This enables us to obtain the recurrence of (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} using characteristic polynomials; Section 4 investigates the relation between (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} when either p or q is equal to 1 and suggests some problems for future studies.

2 Formulas for (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞}

In this section, we prove Formulas (4) and (5) by first confirming that these formulas produce the initial values of (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞}, respectively then showing that later values satisfy the recurrence given by the characteristic polynomial 1 − x^{q} − x^{p+q}.

Proof of (4). First, we verify that Ψ(p, q, n) = a_{p,q,n} for 0 ≤ n ≤ p + q − 1. Case 1 : p ≥ q. When n ≤ p − q − 1, the sum

\begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i}

is empty and thus, is equal to 0. When p − q ≤ n ≤ p + q − 1, we obtain

\begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} = ∑_{i=0}^{0} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} = \binom{⌊\frac{n−p}{q}⌋ + 1}{0} = 1.

Case 2 : p < q. When n ≤ 2p − 1, we have

\begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} = ∑_{i=0}^{0} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} = \binom{⌊\frac{n−p}{q}⌋ + 1}{0} = 1;

when 2p ≤ n ≤ p + q − 1, we have

\begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} = ∑_{i=0}^{1} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i}

= \binom{⌊\frac{n−p}{q}⌋ + 1}{0} + \binom{⌊\frac{n−2p}{q}⌋ + 1}{1}

= 1 + 1 = 2.

It remains to prove that (Ψ(p, q, n))_{n=1}^{∞} and (a_{p,q,n})_{n=1}^{∞} satisfy the same recurrence: for all n ≥ p + q, we verify the following identity

\begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} = \begin{matrix}⌊ & \frac{n−p}{p+q} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋}{i} + \begin{aligned}⌊ & \frac{n−2p}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}.

We have

\begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} − \begin{matrix}⌊ & \frac{n−p}{p+q} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋}{i}

= \begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=1 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} − \begin{matrix}⌊ & \frac{n−p}{p+q} & ⌋ \\ ∑ \\ i=1 \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋}{i}

= \begin{matrix}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ ∑ \\ i=⌊\frac{n−p}{p+q}⌋+1 \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} + \begin{matrix}⌊ & \frac{n−p}{p+q} & ⌋ \\ ∑ \\ i=1 \end{matrix} (\binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} − \binom{⌊\frac{n−p(i+1)}{q}⌋}{i})

= \begin{matrix}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ ∑ \\ i=⌊\frac{n+q}{p+q}⌋ \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} + \begin{matrix}⌊ & \frac{n−p}{p+q} & ⌋ \\ ∑ \\ i=1 \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋}{i − 1}

= \begin{matrix}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ ∑ \\ i=⌊\frac{n+q}{p+q}⌋ \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} + \begin{aligned}⌊ & \frac{n−2p−q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}.  (8)

Write n − p = (p + q)j + k for some j ≥ 0 and 0 ≤ k ≤ p + q − 1 and proceed by case analysis.

If 0 ≤ k ≤ p − 1, then (8) is equal to

∑_{i=j+1}^{j} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} + ∑_{i=0}^{j−1} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i} = ∑_{i=0}^{j−1} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}

= \begin{aligned}⌊ & \frac{n−2p}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}.

If p ≤ k ≤ p + q − 1, then (8) is equal to

∑_{i=j+1}^{j+1} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} + ∑_{i=0}^{j−1} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}

= 1 + ∑_{i=0}^{j−1} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}

= ∑_{i=0}^{j} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i} = \begin{aligned}⌊ & \frac{n−2p}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}.

We have shown the identity

\begin{aligned}⌊ & \frac{n−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+1)}{q}⌋ + 1}{i} − \begin{matrix}⌊ & \frac{n−p}{p+q} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{⌊\frac{n−p(i+1)}{q}⌋}{i} = \begin{aligned}⌊ & \frac{n−2p}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{n−p(i+2)}{q}⌋}{i}

holds for all n ≥ p + q.

Proof of (5). First, we verify that Φ(p, q, n) = a_{p,q,n} for 0 ≤ n ≤ p + q − 1.

Case 1 : p ≥ q. For n ≤ p + q − 1, we have

\frac{n − iq}{p} − 2 ≤ \frac{p + q − 1 − iq}{p} − 2 ≤ \frac{q − 1}{p} − 1 < 0, for all i ≥ 0.

Hence, we have

⌊\frac{n}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2} + \begin{cases}1, & if n = p − q; \\ 0, & otherwise \end{cases} = \begin{cases}1, & if n = p − q; \\ 0, & if 0 ≤ n ≤ p + q − 1 and n ≠ p − q. \end{cases}

Case 2 : p < q. For n ≤ 2p − 1, we have

\frac{n − iq}{p} − 2 ≤ \frac{2p − 1}{p} − 2 < 0, for all i ≥ 0,

which implies that

⌊\frac{n}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2} = 0.

For n = 2p, we have

⌊\frac{n}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2} = ⌊\frac{2p}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ p|(qi) \end{matrix} \binom{i}{\frac{−iq}{p}} = \binom{0}{0} = 1

because every positive i makes \binom{i}{−iq/p} = 0. For 2p + 1 ≤ n ≤ p + q − 1, we have

\frac{n − iq}{p} − 2 ≤ \frac{p + q − 1 − iq}{p} − 2 = \frac{(1 − i)q − 1}{p} − 1 < 0, for all i ≥ 1,

which implies that

⌊\frac{n}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2} = \begin{cases}\binom{0}{\frac{n}{p} −2}, & if p|n \\ 0, & otherwise \end{cases} = 0

because if p|n, then n/p ≥ 3.

Next, we show that (Φ(p, q, n))_{n=0}^{∞} follows the same recurrence as (a_{p,q,n}^{(m)})_{n=0}^{∞}, namely

Φ(p, q, n) = Φ(p, q, n − q) + Φ(p, q, n − p − q),  (9)

for n ≥ p + q. To do so, we consider the two cases when n = 2p and n ≠ 2p. Case A: n = 2p. We have

Φ(p, q, n − p − q) = Φ(p, q, p − q) = ∑_{\begin{matrix}i=0 \\ p|((i+1)q) \end{matrix}}^{⌊\frac{p}{q}⌋−1} \binom{i}{\frac{−(i+1)q}{p} − 1} + 1 = 1

because −(i + 1)q/p − 1 < 0 for all i ≥ 0. Then

Φ(p, q, 2p) = Φ(p, q, 2p − q) + Φ(p, q, p − q)

can be rewritten as

⌊\frac{2p}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ p|(qi) \end{matrix} \binom{i}{\frac{−iq}{p}} = ∑_{\begin{matrix}i=0 \\ p|((i+1)q) \end{matrix}}^{⌊\frac{2p}{q}⌋−1} \binom{i}{\frac{−(i+1)q}{p}} + 1.  (10)

On the left side of (10), only i = 0 contributes a nonzero term to the sum, so

⌊\frac{2p}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ p|(qi) \end{matrix} \binom{i}{\frac{−iq}{p}} = 1.

On the right side of (10), each binomial in the sum is zero because i ≥ 0 > −(i + 1)q/p. This confirms (9) when n = 2p. Case B: n ≠ 2p. We write (9) as

⌊\frac{n}{q}⌋ ; ∑ ; \begin{matrix}i=0 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2}
= ∑_{\begin{matrix}i=0 \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n}{q}⌋−1} \binom{i}{\frac{n−(i+1)q}{p} − 2} + ∑_{\begin{matrix}i=0 \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n−p}{q}⌋−1} \binom{i}{\frac{n−(i+1)q}{p} − 3}.  (11)

The right side of (11) is

∑_{\begin{matrix}i=⌊\frac{n−p}{q}⌋ \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n}{q}⌋−1} \binom{i}{\frac{n−(i+1)q}{p} − 2} + ∑_{\begin{matrix}i=0 \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n−p}{q}⌋−1} (\binom{i}{\frac{n−(i+1)q}{p} − 2} + \binom{i}{\frac{n−(i+1)q}{p} − 3})

= ∑_{\begin{matrix}i=⌊\frac{n−p}{q}⌋ \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n}{q}⌋−1} \binom{i}{\frac{n−(i+1)q}{p} − 2} + ∑_{\begin{matrix}i=0 \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n−p}{q}⌋−1} \binom{i + 1}{\frac{n−(i+1)q}{p} − 2}

= ∑_{\begin{matrix}i=⌊\frac{n−p}{q}⌋ \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n}{q}⌋−1} \binom{i}{\frac{n−(i+1)q}{p} − 2} + ⌊\frac{n−p}{q}⌋ ; ∑ ; \begin{matrix}i=1 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2}.  (12)

By (11) and (12), we need to prove

⌊\frac{n}{q}⌋ ; ∑ ; \begin{matrix}i=⌊\frac{n−p}{q}⌋+1 \\ qi ≡ n (mod p) \end{matrix} \binom{i}{\frac{n−iq}{p} − 2} = ∑_{\begin{matrix}i=⌊\frac{n−p}{q}⌋ \\ q(i+1) ≡ n (mod p) \end{matrix}}^{⌊\frac{n}{q}⌋−1} \binom{i}{\frac{n−(i+1)q}{p} − 2}.  (13)

Note that we discard \binom{0}{n/p−2} on the left side of (11) because the term is nonzero only when n = 2p. We claim that both sides of (13) vanish. On the left, we have

\frac{n − p}{q} < i ≤ \frac{n}{q} and qi ≡ n (mod p),

which give

−p < qi − n ≤ 0 and qi ≡ n (mod p).

Hence, we obtain qi − n = 0, and the corresponding binomial is \binom{i}{−2} = 0 because i ≥ 1. Similarly, the right side of (13) is also 0.

3 Subsequences of Padovan-like sequences

3.1 Proof of Theorem 1

In this section, we show that the terms of (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} are taken q-periodically from the sequences (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞}. This allows us to deduce a linear recurrence for (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞}.

First, we find a formula for |S_{n}^{p/q}|. For 1 ≤ i ≤ n, let F be an i-element set in S_{n}^{p/q}; that is, we have F ⊂ {1, 2, …, n}, n ∈ F, |F | = i, and q min F ≥ pi. Hence, to form F, we choose i − 1 elements in \{⌈\frac{pi}{q}⌉ , …, n − 1\}. Therefore, the number of i-element sets in |S_{n}^{p/q}| is

\binom{n − ⌈\frac{pi}{q}⌉}{i − 1}.

Here we require that n − ⌈pi/q⌉ ≥ i − 1, or equivalently, we require that i ≤ ⌊\frac{(n+1)q}{p+q}⌋. Therefore, we have

|S_{n}^{p/q}| = \begin{aligned}⌊ & \frac{(n+1)q}{p+q} & ⌋ \\ & ∑ \\ & i=1 \end{aligned} \binom{n − ⌈\frac{pi}{q}⌉}{i − 1}.  (14)

Next, we give a formula for |M_{n}^{p/q}|. Let p′ = p/ gcd(p, q) and q′ = q/ gcd(p, q). Consider a (p, q)-maximal Schreier set F ⊂ {1, …, n} with n ∈ F and |F | = i. Since q min F = p|F | = pi, we know that i is a multiple of q′. Let i = q′k. Then min F = p′k, and F = {p′k, n} ∪ F′, where F′ ⊂ \{p′k + 1, p′k + 2, …, n − 1\} and |F′| = q′k − 2. Hence, there are \binom{n−p′k−1}{q′k−2} such sets F. Here we require n−p′k −1 ≥ q′k −2, or equivalently, we require k ≤ (n+1)/(p′ +q′). Therefore, we obtain

|M_{n}^{p/q}| = \begin{aligned}⌊ & \frac{n+1}{p′+q′} & ⌋ \\ & ∑ \\ & k=1 \end{aligned} \binom{n − p′k − 1}{q′k − 2}.  (15)

Proof of Theorem 1. First, we prove (6). We have

Ψ(p, q, (n − 1)q) = \begin{aligned}⌊ & \frac{(n−1)q−p+q}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{⌊\frac{(n−1)q−p(i+1)}{q}⌋ + 1}{i}

= \begin{aligned}⌊ & \frac{nq−p}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{n + ⌊\frac{−p(i+1)}{q}⌋}{i}

= \begin{aligned}⌊ & \frac{nq−p}{p+q} & ⌋ \\ & ∑ \\ & i=0 \end{aligned} \binom{n − ⌈\frac{p(i+1)}{q}⌉}{i}

= \begin{aligned}⌊ & \frac{(n+1)q}{p+q} & ⌋ \\ & ∑ \\ & i=1 \end{aligned} \binom{n − ⌈\frac{pi}{q}⌉}{i − 1} = |S_{n}^{p/q}|.

Next, we prove (7). Let p′ = p/ gcd(p, q) and q′ = q/ gcd(p, q). Letting n − i − 1 = p′k in the equations below, we have

Φ(p, q, (n − 1)q)
= ∑_{\begin{matrix}i=0 \\ p′|(n−i−1) \end{matrix}}^{n−1} \binom{i}{\frac{q′(n−i−1)}{p′} − 2} + \begin{cases}1, & if (n, q′) = (p′, 1), \\ 0, & otherwise, \end{cases}

= \begin{matrix}⌊ & \frac{n−1}{p′} & ⌋ \\ ∑ \\ k=0 \end{matrix} \binom{n − p′k − 1}{q′k − 2} + \begin{cases}1, & if (n, q′) = (p′, 1), \\ 0, & otherwise, \end{cases} (with n − i − 1 = p′k)

= \begin{matrix}⌊ & \frac{n−1}{p′} & ⌋ \\ ∑ \\ k=1 \end{matrix} \binom{n − p′k − 1}{q′k − 2} + \begin{cases}1, & if (n, q′) = (p′, 1), \\ 0, & otherwise. \end{cases}  (16)

Thanks to (15) and (16), it suffices to verify that for n ∈ ℕ, we have

\begin{aligned}⌊ & \frac{n+1}{p′+q′} & ⌋ \\ & ∑ \\ & k=1 \end{aligned} \binom{n − p′k − 1}{q′k − 2} = \begin{matrix}⌊ & \frac{n−1}{p′} & ⌋ \\ ∑ \\ k=1 \end{matrix} \binom{n − p′k − 1}{q′k − 2} + \begin{cases}1, & if (n, q′) = (p′, 1), \\ 0, & otherwise. \end{cases}  (17)

We proceed by case analysis.

Case 1 : (n−1)/p′ ≥ (n+1)/(p′+q′) which is equivalent to nq′ ≥ 2p′+q′. Then (n, q′) ≠ (p′, 1). We have

\begin{matrix}⌊ & \frac{n−1}{p′} & ⌋ \\ ∑ \\ k=1 \end{matrix} \binom{n − p′k − 1}{q′k − 2} − \begin{aligned}⌊ & \frac{n+1}{p′+q′} & ⌋ \\ & ∑ \\ & k=1 \end{aligned} \binom{n − p′k − 1}{q′k − 2} = \begin{matrix}⌊ & \frac{n−1}{p′} & ⌋ \\ ∑ \\ k=⌊ \frac{n+1}{p′+q′} ⌋+1 \end{matrix} \binom{n − p′k − 1}{q′k − 2}.

For each k ≥ ⌊\frac{n+1}{p′+q′} ⌋ + 1, we have n − p′k − 1 < q′k − 2, so the binomial \binom{n−p′k−1}{q′k−2} is zero unless q′k = 2, which occurs when either (q′, k) = (2, 1) or (q′, k) = (1, 2).

a) Case 1.1 : (q′, k) = (2, 1). That k = 1 implies that ⌊\frac{n+1}{p′+q′} ⌋ = 0, which in turn implies n < p′ + 1. However, the inequality nq′ ≥ 2p′ + q′ gives 2n ≥ 2p′ + 2, which contradicts n < p′ + 1.

b) Case 1.2 : (q′, k) = (1, 2). Then ⌊\frac{n+1}{p′+q′} ⌋ = 1, which implies

n < 2p′ + 2q′ − 1 = 2p′ + 1.

However, the inequality nq′ ≥ 2p′ + q′ gives n ≥ 2p′ + 1, which contradicts n < 2p′ + 1.

Case 2 : (n − 1)/p′ < (n + 1)/(p′ + q′) which is equivalent to n < 1 + 2p′/q′. Then (n + 1)/(p′ + q′) < 2.

If ⌊\frac{n+1}{p′+q′} ⌋ = 0, then (n, q′) ≠ (p′, 1), and (n − 1)/p′ < (n + 1)/(p′ + q′) implies that

⌊\frac{n−1}{p′}⌋ = 0. Hence, both sides of (17) are zero.

If ⌊\frac{n+1}{p′+q′} ⌋ = 1, then ⌊\frac{n−1}{p′}⌋ ∈ \{0, 1\}.

a) Case 2.1 : If ⌊\frac{n−1}{p′}⌋ = 1, then n ≠ p′, and (17) holds.

b) Case 2.2 : If ⌊\frac{n−1}{p′}⌋ = 0, then n < p′+1. On the other hand, we deduce from ⌊\frac{n+1}{p′+q′} ⌋ = 1 that n ≥ p′ + q′ − 1. Hence, we obtain

p′ + 1 > n ≥ p′ + q′ − 1 ⟹ q′ = 1.

Then (17) becomes

∑_{k=1}^{1} \binom{n − p′k − 1}{k − 2} = ∑_{k=1}^{0} \binom{n − p′k − 1}{k − 2} + \begin{cases}1, & if n = p′, \\ 0, & otherwise, \end{cases}

or equivalently, we have

\binom{n − p − 1}{−1} = \begin{cases}1, & if n = p, \\ 0, & otherwise, \end{cases}

which is true.

3.2 Recurrence of (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞}

By Theorem 1, the recurrence of (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} is the same as the recurrence of subsequences taken q-periodically out of (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞}, respectively. Definition 4. Let p(x) = c_{0} + c_{1}x + ⋯ + c_{r}x^{r} be a polynomial with real coefficients (c_{i})_{i=0}^{r}. A sequence (a_{n})_{n=0}^{∞} is said to satisfy p(x) if

c_{0}a_{n} + c_{1}a_{n−1} + ⋯ + c_{r}a_{n−r} = 0, for all n ≥ r.

Trivially, all sequences satisfy the zero polynomial.

We need the following lemma, whose proof is straightforward and therefore omitted. Lemma 5. If a sequence (a_{n})_{n=0}^{∞} satisfies p(x) and p(x) divides q(x), then (a_{n})_{n=0}^{∞} satisfies q(x). Proof of Corollaries 2 and 3. We verify initial terms and prove the linear recurrence for (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞}. The formulas for initial terms are due to (14) and (15). We prove the recurrence relation. By definition, both (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞} satisfy g_{p,q}(x) := 1 − x^{q} − x^{p+q}. Define

h_{p,q}(x) := 1 − ∑_{i=1}^{q}(−1)^{i+1}\binom{q}{i}x^{i} − x^{p+q}.

We have

h_{p,q}(x^{q}) = 1 + ∑_{i=1}^{q}(−1)^{i}\binom{q}{i}x^{qi} − x^{q(p+q)}

= ∑_{i=0}^{q}(−1)^{i}\binom{q}{i}x^{qi} − x^{q(p+q)}

= (1 − x^{q})^{q} − (x^{p+q})^{q}

= (1 − x^{q} − x^{p+q}) ∑_{i=0}^{q−1}(1 − x^{q})^{q−1−i}x^{(p+q)i},

so g_{p,q}(x) divides h_{p,q}(x^{q}). By Lemma 5, both (a_{p,q,n})_{n=0}^{∞} and (a_{p,q,n}^{(m)})_{n=0}^{∞} satisfy h_{p,q}(x^{q}). By Theorem 1, we have (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} satisfy h_{p,q}(x). Here we use the obvious fact that for a fixed k ∈ ℕ, if (b_{n})_{n=1}^{∞} satisfies c_{0} + c_{k}x^{k} + c_{2k}x^{2k} + ⋯ + c_{nk}x^{nk}, then the subsequence (b_{(n−1)k})_{n=1}^{∞} satisfies c_{0} + c_{k}x + c_{2k}x^{2} + ⋯ + c_{nk}x^{n}.

Remark 6. While one goal of the present paper is to establish the recurrence relation of (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} without using the inclusion-exclusion principle as in [1], we can use the same argument in the proof of Corollaries 2 and 3 to show that (6) is a corollary of [1, Theorem 1.1]. Indeed, Equality (3) states that (|S_{n}^{p/q}|)_{n=1}^{∞} satisfies

h_{p,q}(x) = 1 + ∑_{i=1}^{q}(−1)^{i}\binom{q}{i}x^{i} − x^{p+q} = (1 − x)^{q} − x^{p+q}.

The definition of (a_{p,q,n})_{n=0}^{∞} gives that (a_{p,q,n})_{n=0}^{∞} satisfies g_{p,q}(x) = 1−x^{q} −x^{p+q}. Since g_{p,q}(x) divides h_{p,q}(x^{q}) = (1 − x^{q})^{q} − x^{q(p+q)}, we know that (a_{p,q,n})_{n=0}^{∞} satisfies h_{p,q}(x^{q}). Hence, the sequence (a_{p,q,(n−1)q})_{n=1}^{∞} satisfies h_{p,q}(x). Since (|S_{n}^{p/q}|)_{n=1}^{∞} and (a_{p,q,(n−1)q})_{n=1}^{∞} satisfy the same polynomial and have the same initial terms, the two sequences are identical.

4 Relation between (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞} and future investigations

It is natural to ask about the relation between the two sequences (|S_{n}^{p/q}|)_{n=1}^{∞} and (|M_{n}^{p/q}|)_{n=1}^{∞}: given one of the sequences, can we compute the other? This section presents the two special cases when p = 1 or q = 1 of the following problem.

Problem 7. For (p, q) ∈ ℕ^{2}, find the constants (c_{i})_{i=1}^{∞} (if any) such that

|M_{n}^{p/q}| = ∑_{i=1}^{∞} c_{i}|S_{i}^{p/q}|, for all n ∈ ℕ.

Theorem 8. For p, n ∈ ℕ, we have

|S_{n}^{p/1}| = |M_{n+p+1}^{p/1}|.

Proof. By (14) and (15), we have

|S_{n}^{p/1}| = \begin{matrix}⌊ & \frac{n+1}{p+1} & ⌋ \\ ∑ \\ i=1 \end{matrix} \binom{n − pi}{i − 1} and |M_{n}^{p/1}| = \begin{matrix}⌊ & \frac{n+1}{p+1} & ⌋ \\ ∑ \\ i=1 \end{matrix} \binom{n − pi − 1}{i − 2}.

Hence, we obtain

|M_{n+p+1}^{p/1}| = \begin{aligned}⌊ & \frac{n+p+2}{p+1} & ⌋ \\ & ∑ \\ & i=1 \end{aligned} \binom{n + p + 1 − pi − 1}{i − 2} = ∑_{i=1}^{⌊\frac{n+1}{p+1}⌋+1} \binom{n − p(i − 1)}{i − 2}

= \begin{matrix}⌊ & \frac{n+1}{p+1} & ⌋ \\ ∑ \\ i=0 \end{matrix} \binom{n − pi}{i − 1}

= \begin{matrix}⌊ & \frac{n+1}{p+1} & ⌋ \\ ∑ \\ i=1 \end{matrix} \binom{n − pi}{i − 1} = |S_{n}^{p/1}|.

Theorem 9. For q, n ∈ ℕ, we have

|M_{n}^{1/q}| = 2|S_{n}^{1/q}| − |S_{n+1}^{1/q}|.  (18)

Proof. Let n ∈ ℕ. When q = 1, we have |S_{n}^{1/1}| = F_{n}, |S_{n+1}^{1/1}| = F_{n+1}, and |M_{n}^{1/1}| = F_{n−2} (see (1) and (2)). Then (18) holds. For the rest of the proof, assume that q ≥ 2.

We need to bijectively map two copies of S_{n}^{1/q} to S_{n+1}^{1/q} ∪ M_{n}^{1/q}. Observe that

ϕ : S_{n}^{1/q} → S_{n+1}^{1/q}
F ↦ F + q

maps S_{n}^{1/q} injectively into S_{n+1}^{1/q}. Furthermore, we know from the definition that M_{n}^{1/q} ⊂ S_{n}^{1/q}. Hence, it suffices to show that

|S_{n}^{1/q}\M_{n}^{1/q}| = |S_{n+1}^{1/q}\ϕ(S_{n}^{1/q})|.  (19)

The left side of (19) is the cardinality of

L_{q,n} := {F ⊂ {1, 2, …, n} : q min F > |F | and max F = n},

which can be partitioned into the collections

L_{q,n,i} := {F ⊂ {1, 2, …, n} : q min F > |F | = i and max F = n}, with i ≥ 1.

For i = 1, the only set in L_{q,n,1} is {n}, so we have |L_{q,n,1}| = 1. For i ≥ 2, to form sets in L_{q,n,i}, we first choose the minimum j with i/q < j ≤ n − 1 then choose i − 2 integers in [j + 1, n − 1], which requires i − 2 ≤ n − j − 1. Hence, for i ≥ 2, we obtain

|L_{q,n,i}| = ∑_{\begin{matrix}i+1≤jq≤(n−1)q \\ j≤n−i+1 \end{matrix}} \binom{n − j − 1}{i − 2} = ∑_{i+1≤jq≤(n−i+1)q} \binom{n − j − 1}{i − 2}.

The right side of (19) is the cardinality of

R_{q,n} := {F ⊂ {1, 2, …, n + 1} : q min F ≥ |F | > q min F − q, max F = n + 1},

which can be partitioned into

R_{q,n,i} := {F ⊂ {1, 2, …, n + 1} : q min F ≥ |F | = i > q min F − q,
max F = n + 1}, with i ≥ 1.

We have R_{q,n,1} = ∅ because a nonempty R_{q,n,1} requires 1 > (n + 1)q − q = nq ≥ 2. For i = 2, an F ∈ R_{q,n,2} must have the form F = {j, n + 1} with 1 ≤ j ≤ n and jq ≥ 2 > (j − 1)q. Since q ≥ 2, the inequality 2 > (j − 1)q implies that j = 1. Hence, the set F is {1, n + 1} and |R_{q,n,2}| = 1. To form sets in R_{q,n,i} with i ≥ 3, we first choose the minimum j with j − 1 < i/q ≤ j ≤ n then choose i − 2 integers in [j + 1, n], which requires n − j ≥ i − 2. Hence, for i ≥ 3, we obtain

|R_{q,n,i}| = ∑_{\begin{matrix}1+q(j−1)≤i≤jq≤nq \\ j≤n+2−i \end{matrix}} \binom{n − j}{i − 2} = ∑_{\begin{matrix}i≤jq≤i+q−1 \\ j≤n−i+2 \end{matrix}} \binom{n − j}{i − 2}.

To prove (19), we show that

|L_{q,n,i}| = |R_{q,n,i+1}|, for i ≥ 1.  (20)

The above analysis shows that (20) holds when i = 1. For i ≥ 2, Equality (20) is the same as

∑_{i+1≤jq≤(n−i+1)q} \binom{n − j − 1}{i − 2} = ∑_{\begin{matrix}i+1≤jq≤i+q \\ j≤n−i+1 \end{matrix}} \binom{n − j}{i − 1}.  (21)

Case 1 : (n − i + 1)q ≤ i + q. We have

∑_{i+1≤jq≤(n−i+1)q} \binom{n − j − 1}{i − 2} − ∑_{\begin{matrix}i+1≤jq≤i+q \\ j≤n−i+1 \end{matrix}} \binom{n − j}{i − 1}

= ∑_{i+1≤jq≤(n−i+1)q} \binom{n − j − 1}{i − 2} − ∑_{i+1≤jq≤(n−i+1)q} \binom{n − j}{i − 1}.  (22)

Since (n − i + 1)q ≤ i + q, we obtain

n ≤ i + \frac{i}{q} = i + \frac{(i + 1) − 1}{q} ≤ i + \frac{jq − 1}{q} < i + j,

which implies n ≤ i + j − 1, but (22) sums over j ≤ n − i + 1. Therefore, n = i + j − 1 in (22), which gives

∑_{i+1≤jq≤(n−i+1)q} \binom{n − j − 1}{i − 2} − ∑_{i+1≤jq≤(n−i+1)q} \binom{n − j}{i − 1}

= ∑_{i+1≤jq≤(n−i+1)q} 1 − ∑_{i+1≤jq≤(n−i+1)q} 1 = 0.

Case 2 : (n − i + 1)q > i + q. Then (21) is equivalent to

∑_{i+1≤jq≤(n−i+1)q} \binom{n − j − 1}{i − 2} = \binom{n − ⌈\frac{i+1}{q}⌉}{i − 1},

which is precisely the hockey-stick identity (see [7, Theorem 1.2.3, item (5)]).

We have verified (21) and thus completed the proof.

5 Acknowledgments

The authors would like to thank the anonymous referee for a careful reading of the paper and for the helpful suggestions.

This work is partially supported by the College of Arts & Sciences at Texas A&M University. The second named author is an undergraduate at Texas A&M University, working under the guidance of the first named author.

References

[1] K. Beanland, H. V. Chu, and C. E. Finch-Smith, Generalized Schreier sets, linear recurrence relation, and Turán graphs, Fibonacci Quart. 60 (2022), 352–356.

[2] K. Beanland, D. Gorovoy, J. Hodor, and D. Homza, Counting unions of Schreier sets, Bull. Aust. Math. Soc. 110 (2024), 19–31.

[3] A. Bird, 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/.

[4] H. V. Chu, The Fibonacci sequence and Schreier-Zeckendorf sets, J. Integer Sequences 19 (2019), 1–12.

[5] H. V. Chu, N. Irmak, S. J. Miller, L. Szalay, and S. X. Zhang, Schreier multisets and the s-step Fibonacci sequences, Integers 24A (2024), 1–11.

[6] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2025. Available

   at https://oeis.org.

[7] D. B. West, Combinatorial Mathematics, Cambridge University Press, 2021.

2020 Mathematics Subject Classification: Primary 05A19; Secondary 11B37, 11Y55, 05A15. Keywords: Schreier set, recurrence, Pascal triangle.

(Concerned with sequences \underline{A000045}, \underline{A000931}, \underline{A005251}, \underline{A005314}, \underline{A017817}, \underline{A017827}, \underline{A052920}, \underline{A078012}, \underline{A079398}, \underline{A099558}, \underline{A103372}, \underline{A135851}, \underline{A137357}, \underline{A212804}, \underline{A226503}, \underline{A375169}, \underline{A385106}, \underline{A385107}, and \underline{A385142}.)

Received June 23 2025; revised versions received December 23 2025; March 3 2026. Published in Journal of Integer Sequences, March 23 2026.

Return to Journal of Integer Sequences home page.