# Counting Unions of Schreier Sets

Kevin Beanland  ,  Dmitriy Gorovoy  ,  Jȩdrzej Hodor  and  Daniil Homza  (K.
Beanland) Department of Mathematics, Washington and Lee University, Lexington,
VA 24450<EMAIL_ADDRESS>(D. Gorovoy, J. Hodor, D. Homza) Mathematics
Department, Faculty of Mathematics and Computer Science, Jagiellonian
University, Kraków, Poland.
dimgor2003@gmail.com,jedrzej.hodor<EMAIL_ADDRESS>
###### Abstract.

A subset of positive integers $F$ is a Schreier set if it is non-empty and
$|F|\leqslant\min F$ (here $|F|$ is the cardinality of $F$). For each positive
integer $k$, we define $k\mathcal{S}$ as the collection of all the unions of
at most $k$ Schreier sets. Also, for each positive integer $n$, let
$(k\mathcal{S})^{n}$ be the collection of all sets in $k\mathcal{S}$ with the
maximum element equal to $n$. It is well-known that the sequence
$(|(1\mathcal{S})^{n}|)_{n=1}^{\infty}$ is the Fibbonacci sequence. In
particular, the sequence satisfies a linear recurrence. We generalize this
statement, namely, we show that the sequence
$(|(k\mathcal{S})^{n}|)_{n=1}^{\infty}$ satisfies a linear recurrence for
every positive $k$.

2010 Mathematics Subject Classification. Primary:

Key words:

J. Hodor is partially supported by a Polish National Science Center grant
(BEETHOVEN; UMO-2018/31/G/ST1/03718).

##  1\. Introduction

A subset $F$ of natural numbers***We write $\mathbb{N}$ for the set of all
positive integers, and we refer to members of $\mathbb{N}$ as natural numbers.
is called a _Schreier set_ if it is non-empty and $|F|\leqslant\min F$ (here
$|F|$ is the cardinality of the set $F$). Let $\mathcal{S}$ denote the family
of all Schreier sets and $\mathcal{S}^{n}$ be the set of Schreier sets $F$
with $\max F=n$. The family $\mathcal{S}$, which we call the _Schreier family_
, was introduced in the 1930s in a seminal paper of Józef Schreier [10]. In
this paper, Schreier solved a problem in Banach space theory posed to Banach
and Saks. It is now well-established that Schreier sets and their
generalizations have deep connections to the norm convergence of convex
combinations of weakly null sequences [1, 2, 9] and are thus of fundamental
importance in Banach space theory.

In this paper, we focus on the combinatorial properties of the Schreier sets.
Recently, counting various generalizations of Schreier sets has received a lot
of attention and can be seen by H.V. Chu and coauthors’ work [3, 5, 6, 7].
Research in this direction began with the simple observation by an
anonymous†††The blogger was later to be revealed to be Alistair Bird who
discovered this connection while writing his Ph.D. thesis in Banach space
theory. blogger that $(|\mathcal{S}^{n}|)_{n=1}^{\infty}$ is the Fibonacci
sequence. This fact follows from the observation that the set elements of
$\mathcal{S}^{n}$ which contain $n-1$ can be put in bijection with
$\mathcal{S}^{n-1}$, and the set of elements of $\mathcal{S}^{n}$ not
containing $n-1$ can be put in bijection with $\mathcal{S}^{n-2}$.

It is natural to ask if, for various modified Schreier families, the analogous
sequence (counting members with a fixed maximal element) is a linear
recurrence sequence. A natural and nontrivial modification of $\mathcal{S}$ is
to fix natural numbers $p$ and $q$ and consider the family

$\mathcal{S}_{p,q}=\\{F\subseteq\mathbb{N}:q\min F\geqslant p|F|\\}$

In [3], Beanland, Chu, and Finch-Smith proved that the sequence
$(|\mathcal{S}^{n}_{p,q}|)_{n=1}^{\infty}$ is a linear recurrence sequence and
gave a compact recursive formula (this builds on the earlier work [8]).

In the current paper, we consider, for each natural number $k$, the set
$k\mathcal{S}$ of all subsets of $\mathbb{N}$ that can be written as a union
of at most $k$ many Schreier sets. These sets were recently studied in a
Banach space theory context in [4] by the first and third authors of the
present paper.

In the present work, we prove that for each $k$ the sequence
$\\{|(k\mathcal{S})^{n}|\\}_{n=1}^{\infty}$ satisfies a specific recurrence
relation that is generated by the Fibonacci recurrence in a natural way. In
order to describe these recurrences we recall a few basic notions. A sequence
$(a_{n})_{n=1}^{\infty}$ satisfies the linear recurrence with coefficients
$c_{k},c_{k-1},\cdots,c_{0}$ (we assume that $c_{k}\not=0$) if for each
$n\in\mathbb{N}$, we have

$c_{k}a_{n+k}+c_{k-1}a_{n+k-1}+\cdots+c_{1}a_{n+1}+c_{0}a_{n}=0$

The characteristic polynomial of the linear recurrence is given by

$p(x)=c_{k}x^{k}+c_{k-1}x^{k-1}+\cdots+c_{1}x+c_{0}.$

We now introduce a sequence of polynomials $(p_{k}(x))_{k=1}^{\infty}$ that
will enable us to state our main result. Let $p_{0}(x)=x-1$. This is the
characteristic polynomial of the constant sequence. Suppose that $p_{k}(x)$
has been defined for some non-negative integer $k$, and let

$p_{k+1}(x):=p_{k}(x(x-1)).$ (1)

Below we have computed $p_{k}(x)$ for each $k\in\\{1,2,3\\}$.

  1. (1)

$p_{1}(x)=x(x-1)-1=x^{2}-x-1$, the characteristic polynomial of the Fibonacci
recursion.

  2. (2)

$p_{2}(x)=x^{2}(x-1)^{2}-x(x-1)-1=x^{4}-2x^{3}+x-1$.

  3. (3)

$p_{3}(x)=x^{8}-4x^{7}+4x^{6}+2x^{5}-5x^{4}+2x^{3}+x^{2}-x-1.$

Notice that $p_{k}(x)$ has degree $2^{k}$. For all natural numbers $k$ and
$n$, set $s_{k,n}:=|(k\mathcal{S})^{n}|$. We can now state our main theorem.

######  Theorem 1.

For each $k\in\mathbb{N}$, the sequence $(s_{k,n})_{n=1}^{\infty}$ satisfies
the linear recurrence with characteristic polynomial $p_{k}(x)$.

Unlike the proof in the $k=1$ case, our proof for general $k$ is quite
involved and requires connecting the sequences $(s_{k-1,n})_{n=1}^{\infty}$
with $(s_{k,n})_{n=1}^{\infty}$ is a non-obvious but elegant way. In addition,
we obtain an interesting corollary to the proof Theorem 1. In order to state
it, we need some more notation. For two sets $E,F\subseteq\mathbb{N}$ we write
$E<F$ if $\max E<\min F$. We say that sets
$E_{1},\dots,E_{m}\subseteq\mathbb{N}$ are _successive_ if
$E_{1}<E_{2}<\dots<E_{m}$. A set $F\in\mathcal{S}$ is called a _maximal
Schreier set_ if $|F|=\min F$. Furthermore, $F\in k\mathcal{S}$ is a _maximal
$k$-Schreier set_, if it can be decomposed as the disjoint union of $k$-many
successive maximal Schreier sets. Let
$\mathcal{R}_{k,n}^{0}\subseteq(k\mathcal{S})^{n}$ be the collection of all
maximal $k$-Schreier sets in $(k\mathcal{S})^{n}$ and
$r^{0}_{k,n}:=|\mathcal{R}^{0}_{k,n}|$.

######  Corollary 2.

For each $k\in\mathbb{N}$, the sequence $(r^{0}_{k,n})_{n=1}^{\infty}$
satisfies a linear recurrence with characteristic polynomial $p_{k}(x)$.

##  2\. Notation and overview of the proof of Theorem 1

Let $F\subseteq\mathbb{N}$. We will inductively define a subset $E_{k}(F)$ of
$F$ for each $k\in\mathbb{N}$. Let $E_{1}(F)$ be the initial segment of $F$
that is a maximal Schreier set, and if no such set exists, let $E_{1}(F)=F$.
Assuming $E_{k}(F)$ has been defined for some positive integer $k$, let

$E_{k+1}(F)=E_{1}(F\setminus\bigcup_{i=1}^{k}E_{i}(F)).$

Observe that $E_{1}(F),E_{2}(F),\ldots$ is a partition of $F$ into consecutive
Schreier sets, where all non-empty sets are maximal except possibly for the
last non-empty one.

Let $k\in\mathbb{N}$ and $F\in k\mathcal{S}$. Let $d_{k}(F)$ be the greatest
non-negative integer $d$ so that there is a set $G\subseteq\mathbb{N}$ with
$F<G$, $|G|=d$, and $F\cup G\in k\mathcal{S}$. If no such $d$ exists, we let
$d_{k}(F)=\infty$. Note that

  1. (1)

$d_{k}(F)<\infty$ if and only if $E_{k}(F)\not=\emptyset$.

  2. (2)

$F$ is a maximal $k$-Schreier set if and only if $d_{k}(F)=0$.

For each $n,k\in\mathbb{N}$ and $d$, we define

$\mathcal{R}_{k,n}^{d}:=\\{F\in(kS)^{n}\ :\ d_{k}(F)=d\\}\ \ \ \mbox{ and }\ \
\ r_{k,n}^{d}:=|\mathcal{R}_{k,n}^{d}|.$ (2)

Also, let $r_{k,n}^{d}:=0$ for all
$k,n\in\mathbb{Z},d\in\mathbb{Z}\cup\\{\infty\\}$ such that the value was not
defined above. As a visual aid see the initial values of $r_{k,n}^{d}$ for
$k\in\\{1,2\\}$ in Table 1.

$k=1$ | $k=2$
---|---
|  $n\backslash d$ |  $0$ |  $1$ |  $2$ |  $3$ |  $4$ |  $5$ |  $6$ |  7 |  $\cdots$
---|---|---|---|---|---|---|---|---|---
2.7 1 |  1 |  |  |  |  |  |  |  |
2 |  0 |  1 |  |  |  |  |  |  |
3 |  1 |  0 |  1 |  |  |  |  |  |
4 |  1 |  1 |  0 |  1 |  |  |  |  |
5 |  2 |  1 |  1 |  0 |  1 |  |  |  |
6 |  3 |  2 |  1 |  1 |  0 |  1 |  |  |
7 |  5 |  3 |  2 |  1 |  1 |  0 |  1 |  |
8 |  8 |  5 |  3 |  2 |  1 |  1 |  0 |  1 |
$\vdots$ |  $\vdots$ |  |  |  |  |  |  |  |  $\ddots$
|  $n\backslash d$ |  $0$ |  $1$ |  $2$ |  $3$ |  $4$ |  $5$ |  $6$ |  7 |  $\cdots$
---|---|---|---|---|---|---|---|---|---
2.7 1 |  0 |  |  |  |  |  |  |  |
2 |  0 |  1 |  |  |  |  |  |  |
3 |  1 |  0 |  1 |  |  |  |  |  |
4 |  1 |  1 |  0 |  2 |  |  |  |  |
5 |  2 |  1 |  2 |  0 |  3 |  |  |  |
6 |  3 |  3 |  2 |  3 |  0 |  5 |  |  |
7 |  6 |  5 |  5 |  3 |  5 |  0 |  8 |  |
8 |  11 |  10 |  8 |  8 |  5 |  8 |  0 |  13 |
$\vdots$ |  $\vdots$ |  |  |  |  |  |  |  |  $\ddots$

Table 1. The left are the initial values of $(r_{1,n}^{d})$, and the right are
the initial values of $(r_{2,n}^{d})$.

We now record a few observations regarding the above tables.

  * (O1)

Each entry below the first two main diagonals is computed by adding the entry
directly north to the northeast entry. We call this the Pascal-like property.
Consequently, the two main diagonals determine the rest of the table. Note
also that the second main diagonal is constantly zero; we will show this holds
in general (Lemma 13).

  * (O2)

Due to the Pascal-like property of the tables, if the first two main diagonals
satisfy the same recursion, each diagonal satisfies that recursion. Moreover,
we can express each term of the diagonal in terms of the first column and use
this to compute the recursion for the first column (Lemma 8 and Figure 2).

  * (O3)

In the $k=2$ table, the sequence starting at the second entry of the main
diagonal is equal to the partial sums of the first column of $k=1$ (Lemma 12).
Consequently, these sequences satisfy the exact same recursions. In this case,
both sequences satisfy the Fibonacci linear recurrence.

Taken together, these observations outline an inductive process to compute all
of the entries in the tables up to any given $k$. As we can see from the table
$k=1$, the sequence $(r_{1,n}^{0})_{n=1}^{\infty}$ satisfies the Fibonacci
recursion. As we mentioned in the introduction, the sequence
$(s_{1,n})_{n=1}^{\infty}$ also satisfies the Fibonacci recursion. This led to
the conjecture that this holds for each $k$, namely, that
$(r_{k,n}^{0})_{n=1}^{\infty}$ and $(s_{k,n})_{n=1}^{\infty}$ satisfy the same
recursion relation. We verify this in the affirmative. The main step is to
note and prove that for all natural numbers $k,n$, we have

$s_{k,n}=2s_{k,n-1}-r_{k,n-1}^{0}.$ (3)

##  3\. Initial values of the sequences

This section contains several computations related to the initial values of
the sequences we are considering.

######  Lemma 3.

For all $k\in\mathbb{N}$ with $k\geqslant 2$ and for each
$n\in\\{1,\cdots,2^{k}-2\\}$ we have $r_{k,n}^{0}=0$. Moreover,

$r_{k,2^{k}-1}^{0}=1,\ \ \ \ r_{k,2^{k}}^{0}=2^{k-1}-1,\ \ \
r_{k,2^{k}+1}^{0}=\binom{2^{k-1}}{2}+2^{k-2}.$

###### Proof.

Since $\\{1,\cdots,2^{k}-1\\}$ is a maximal $k$-Schreier set, no proper subset
can be a maximal $k$-Schreier set. This proves that for each
$n\in\\{1,\cdots,2^{k}-2\\}$, we have $r_{k,n}^{0}=0$ and
$r_{k,2^{k}-1}^{0}=1$. The equality $r_{k,2^{k}}^{0}=2^{k-1}-1$ follows from
the fact that $\\{1,\cdots,2^{k}\\}\setminus\\{n\\}$ is a maximal $k$-Schreier
set for each $n\in\\{2^{k-1}+1,\cdots,2^{k}-1\\}$, and every such set is of
this form. To compute $r_{k,2^{k}+1}^{0}$, one easily checks that any set
$F\in\mathcal{R}_{k,2^{k}+1}^{0}$ has initial segment $\\{1,\ldots,2^{k-2}\\}$
and is made by either deleting two numbers from the set
$\\{2^{k-1}+1,\cdots,2^{k}\\}$ or deleting one number from
$\\{2^{k-2}+1,\ldots,2^{k-1}\\}$. ∎

For all $n,k\in\mathbb{N}$, set the following notation

$t_{k,n}:=\sum_{i=1}^{n}r_{k,i}^{0}.$

The next lemma follows trivially from Lemma 3.

######  Lemma 4.

For all $k\in\mathbb{N}$ with $k\geqslant 2$ and for each
$n\in\\{1,\cdots,2^{k}-2\\}$ we have $t_{k,n}=0$. Moreover,

$t_{k,2^{k}-1}=1,\ \ \ \ t_{k,2^{k}}=2^{k-1},\ \ \
t_{k,2^{k}+1}=2^{k-1}+\binom{2^{k-1}}{2}+2^{k-2}.$

######  Lemma 5.

For all $k\in\mathbb{N}$, and for each $n\in\\{1,\cdots,2^{k}-1\\}$, we have
$s_{k,n}=2^{n-1}$. Moreover,

$s_{k,2^{k}}^{0}=2^{2^{k}-1}-1,\ \ \ \ s_{k,2^{k}+1}=2^{2^{k}}-(2^{k-1}+1).$

###### Proof.

Fix $k\in\mathbb{N}$. The set $\\{1,\ldots,2^{k}-1\\}$ is a maximal
$k$-Schreier set. Therefore, every subset of $\\{1,\ldots,2^{k}-1\\}$ is
$k$-Schreier set. Consequently, for each $n\in\\{1,\ldots,2^{k}-1\\}$, we have
$s_{k,n}=2^{n-1}$. On the other hand, $\\{1,\ldots,2^{k}\\}$ is not a
$k$-Schreier set, but every of its proper subset is a $k$-Schreier. Thus,
$s_{k,2^{k}}=2^{2^{k}-1}-1$

We compute $s_{k,2^{k}+1}$. We will show there are exactly $2^{k}+1$ many
subsets of $\\{1,\ldots,2^{k}+1\\}$ with maximum element $2^{k}+1$ that are
not in $k\mathcal{S}$. Let $F$ be such a set and assume the case that
$F\not=\\{1,\ldots,2^{k}+1\\}$.

First observe that $\\{1,\ldots,2^{k-1}\\}\subseteq F$. Indeed, if this were
not the case, then $\min E_{k}(F)>2^{k-1}$, which implies that $\max
E_{k}(F)\geqslant 2^{k}+1$. Hence, since $F\not\in k\mathcal{S}$, $\max
F>2^{k}+1$, a contradiction. Therefore, $\min E_{k}(F)=2^{k-1}$, and since
$2^{k}-1\leqslant\max E_{k}(F)<2^{k}+1$, it follows that
$F=\\{1,\ldots,2^{k}+1\\}\setminus\\{n\\}$ for each
$n\in\\{2^{k-1}+1,\ldots,2^{k}\\}$. Including the case that
$F=\\{1,\ldots,2^{k}+1\\}$. We have a total of $2^{k}+1$ many such sets. This
is the desired result. ∎

For each $k\in\mathbb{N}$, let $(d^{k}_{i})_{i=0}^{2^{k}}$ be so that

$p_{k}(x)=\sum_{i=0}^{2^{k}}d^{k}_{i}x^{i}.$

######  Lemma 6.

Let $k\in\mathbb{N}$ with $k\geqslant 2$. Then

$d_{2^{k}-2}^{k}=\binom{2^{k-1}}{2}-2^{k-2},\ \ \ \ d^{k}_{2^{k}-1}=-2^{k-1}\
\ ,d^{k}_{2^{k}}=1$

###### Proof.

We proceed by induction on $k$. Since $p_{2}(x)=x^{4}-2x^{3}+x-1$, the base
case $k=2$ holds. Fix some integer $k$ with $k\geqslant 3$ and assume the
identities hold for $k-1$. Let $m=2^{k-1}$. Then

$p_{k}(x)=p_{k-1}(x(x-1))=x^{m}(x-1)^{m}-\frac{m}{2}x^{m-1}(x-1)^{m-1}+\cdots.$

By inspection of the leading coefficients and using the binomial theorem, we
have

$p_{k}(x)=x^{2m}-mx^{2m-1}+\bigg{(}\binom{m}{2}-\frac{m}{2}\bigg{)}x^{2m-2}+\cdots.$

This completes the inductive step of the proof. ∎

The next lemma verifies that the recursions are satisfied for the initial
$2^{k}+1$ values of the sequence. This lemma will be repeatedly used as the
base case of the induction in the proof of Theorem 1.

######  Lemma 7.

For each $k\in\mathbb{N}$, we have

$\sum_{i=1}^{2^{k}+1}d^{k}_{i-1}r^{0}_{k,i}=\sum_{i=0}^{2^{k}}d^{k}_{i}t_{k,i+1}=\sum_{i=1}^{2^{k}}d^{k}_{i}t_{k,i}=\sum_{i=0}^{2^{k}}d^{k}_{i}s_{k,i+1}=0.$

###### Proof.

Direct calculation using the above lemmas show that the first three sums are
0. For the final identity, notice first that $p_{k}(2)=1$ for each
$k\in\mathbb{N}$. Thus using the identities in Lemmas 5 and 6, we have

$\begin{split}0=p_{k}(2)-1&=d^{k}_{0}+d^{k}_{1}2+\cdots+d^{k}_{2^{k}-1}(2^{2^{k}-1}-1)+d^{k}_{2^{k}}2^{2^{k}}-1+d^{k}_{2^{k}-1}\\\
&=d^{k}_{0}+d^{k}_{1}2+\cdots+d^{k}_{2^{k}-1}(2^{2^{k}-1}-1)+d^{k}_{2^{k}}(2^{2^{k}}-2^{k-1}-1)\\\
&=\sum_{i=0}^{2^{k}}d^{k}_{i}s_{k,i+1}\qed\end{split}$ (4)

##  4\. Pascal-like sets and recursions

A set $\\{r^{j}_{i}:i\in\mathbb{N},j\in\\{0,\cdots,i-1\\}\\}$ is _Pascal-like_
if for every $i\in\mathbb{N}$ with $i\geqslant 3$ and every
$j\in\\{0,\cdots,i-3\\}$ we have $r_{i}^{j}=r_{i-1}^{j}+r_{i-1}^{j+1}.$ By
definition, the Pascal-like set is determined by the values of the two main
diagonals $(r^{i-1}_{i})_{i=1}^{\infty}$ and $(r^{i-1}_{i+1})_{i=1}^{\infty}$.
See Figure 1 for an illustration. In the next lemma, we express each element
of the main diagonal in terms of the first column.

Figure 1. An initial fragment of a Pascal-like set. The cells of a table are
filled with the numbers $r_{i}^{j}$, e.g. $r_{6}^{1}=7$. The set is determined
by the yellow and orange diagonals.

######  Lemma 8.

Let $\\{r_{i}^{j}:i\in\mathbb{N},j\in\\{0,\cdots,i-1\\}\\}$ be Pascal-like
set. Then for each $n\in\mathbb{N}$, we have

$r_{n}^{n-1}=\sum_{j=0}^{n-1}(-1)^{n-1-j}\binom{n-1}{j}r^{0}_{n+j}.$ (5)

###### Proof.

We proceed by induction. We shall prove that for each $n\in\mathbb{N}$, any
Pascal-like set satisfies (5). For $n=1$, the assertion is clearly satisfied.
Fix $n\geqslant 2$ and assume that (5) holds replacing $n$ with $n-1$ for any
Pascal-like set. Fix a Pascal-like set
$\\{r_{i}^{j}:i\in\mathbb{N},j\in\\{1,\cdots,i-1\\}\\}$ and define
$b_{i}^{j}=r_{i+1}^{j+1}$. Then
$\\{b_{i}^{j}:i\in\mathbb{N},j\in\\{0,\cdots,i-1\\}\\}$ is also a Pascal-like
set. By the inductive assumption, we have

$\displaystyle r_{n}^{n-1}=b_{n-1}^{n-2}$
$\displaystyle=\sum_{j=0}^{n-2}(-1)^{n-2-j}\binom{n-2}{j}b_{n-1+j}^{0}=\sum_{j=0}^{n-2}(-1)^{n-2-j}\binom{n-2}{j}r^{1}_{n+j}$
$\displaystyle=\sum_{j=0}^{n-2}(-1)^{n-2-j}\binom{n-2}{j}(r^{0}_{n+j+1}-r^{0}_{n+j})$
$\displaystyle=\sum_{j=1}^{n-1}(-1)^{n-1-j}\binom{n-2}{j-1}r^{0}_{n+j}+\sum_{j=0}^{n-2}(-1)^{n-1-j}\binom{n-2}{j}r^{0}_{n+j}$
$\displaystyle=\sum_{j=0}^{n-1}(-1)^{n-1-j}\binom{n-1}{j}r^{0}_{n+j}.$

Notice that, in the fourth equality, we used the definition of a Pascal-like
set. ∎

The properties of Pascal-like sets allow transferring recursive relations
between diagonals and columns. In Lemma 9 we show how recursive relations are
transferred between diagonals and in Lemma 10 we show how recursive relations
are transferred from the main diagonals to the first column (see Figure 2 for
intuition). Next, in Lemma 11, we relate the recursive relation on the main
diagonals with the partial sums of the first column.

######  Lemma 9.

Let $\\{r_{i}^{j}:i\in\mathbb{N},j\in\\{0,\cdots,i-1\\}\\}$ be a Pascal-like
set. If $(r_{i}^{i-1})_{i=1}^{\infty}$ and $(r_{i+1}^{i-1})_{i=1}^{\infty}$
both satisfy a linear recurrence with characteristic polynomial $p(x)$, then
for each integer $\ell$ with $\ell\geqslant 2$, the sequence
$(r_{\ell+i}^{i-1})_{i=1}^{\infty}$ satisfies a linear recurrence with
characteristic polynomial $p(x)$.

###### Proof.

We sketch the easy proof. The Pascal-like property yields that
$r^{i-1}_{i+2}=r^{i-1}_{i+1}+r^{i}_{i+1}$ for each $i\in\mathbb{N}$. It is
clear that $(r^{i-1}_{i+2})_{i=1}^{\infty}$ must satisfy the same recursions
as both $(r_{i}^{i-1})_{i=1}^{\infty}$ and $(r_{i+1}^{i-1})_{i=1}^{\infty}$.
Using this observation as the base case for an inductive argument, the general
case follows. ∎

Figure 2. The goal is to relate the main diagonal entries with the first
column entries. Knowing the entries $a_{4,1},a_{5,1},a_{6,1},a_{7,1}$ we can
restore the value of $a_{4,4}$ using the equation
$a_{i,j}=a_{i+1,j-1}-a_{i,j-1}$, which is illustrated on the left hand-side.

######  Lemma 10.

Suppose that $\\{r^{j}_{i}:i\in\mathbb{N},j\in\\{0,\cdots,i-1\\}\\}$ is
_Pascal-like_ and $(r_{i}^{i-1})_{i=1}^{\infty}$ and
$(r_{i+1}^{i-1})_{i=1}^{\infty}$ both satisfy a linear recurrence with
characteristic polynomial $p(x)$. Then the sequence
$(r^{0}_{i})_{i=1}^{\infty}$ satisfies the linear recurrence with
characteristic polynomial $p(x(x-1))$.

###### Proof.

Let $p(x)=c_{k}x^{k}+c_{k-1}x^{k-1}+\cdots c_{1}x+c_{0}$. Let
$(d_{i})_{i=0}^{2k}$ be defined by $p(x(x-1))=\sum_{i=0}^{2k}d_{i}x^{i}$. It
suffices to show that for each non-negative integer $\ell$

$\sum_{i=1}^{2k+1}d_{i-1}r^{0}_{\ell+i}=0.$ (6)

Fix some non-negative integer $\ell$. It follows from the definition that
$\\{r^{j}_{\ell+i}:i\in\mathbb{N},j\in\\{0,\cdots,i-1\\}\\}$ is Pascal-like.
Therefore, by Lemma 9, we know that $\sum_{i=0}^{k}c_{i}r^{i}_{\ell+i+1}=0$.
Using Lemma 8, we rewrite this sum as

$0=\sum_{i=0}^{k}c_{i}r^{i}_{\ell+i+1}=\sum_{i=0}^{k}c_{i}\sum_{j=0}^{i}(-1)^{i-j}\binom{i}{j}r^{0}_{\ell+i+1+j}.$
(7)

Since (7) is satisfied, we know there are coefficients
$(d^{\prime}_{i})_{i=0}^{2k}$ so that
$\sum_{i=1}^{2k+1}d^{\prime}_{i-1}r^{0}_{\ell+i}=0$ (for each non-negative
integer $\ell$). We wish to show that $d^{\prime}_{i}=d_{i}$. Rather than a
messy calculation, a simple way to see this is by converting to the
characteristic polynomial and matching the coefficients. That is, replace
$r^{0}_{\ell+\alpha}$ by $x^{\alpha-1}$ in (7) and apply the binomial theorem
to obtain

$\sum_{i=0}^{k}c_{i}\sum_{j=0}^{i}(-1)^{i-j}\binom{i}{j}x^{i+j}=\sum_{i=0}^{k}c_{i}x^{i}(x-1)^{i}=p(x(x-1))=\sum_{i=0}^{2k}d_{i}x^{i}.$

Therefore $d^{\prime}_{i}=d_{i}$ as desired. ∎

######  Lemma 11.

Let $\\{r^{j}_{i}:i\in\mathbb{N},j\in\\{0,\cdots,i-1\\}\\}$ be Pascal-like so
that $(r_{i}^{i-1})_{i=1}^{\infty}$ and $(r_{i+1}^{i-1})_{i=1}^{\infty}$ both
satisfy a linear recurrence with characteristic polynomial $p(x)$. Let
$(d_{i})_{i=0}^{2k}$ be the coefficients of the polynomial $p(x(x-1))$ and
$t_{j}=\sum_{i=1}^{j}r^{0}_{i}$ for $j\in\mathbb{N}$. Suppose

$\sum_{j=1}^{2k+1}d_{j-1}t_{j}=0.$ (8)

Then $(t_{j})_{j=1}^{\infty}$ is a linear recurrence relation with
characteristic polynomial $p(x(x-1))$.

###### Proof.

Set all the notation as in the statement of the lemma. We proceed by induction
to show that for each non-negative integer $\ell$.

$\sum_{j=1}^{2k+1}d_{j-1}t_{\ell+j}=0$ (9)

The base case of the induction $\ell=0$ is assumed – (8).

Suppose that for some $\ell\geqslant 0$, (9) holds. We will show that (9)
holds for $\ell+1$. By Lemma 10, $(r^{0}_{i})_{i=1}^{\infty}$ satisfies the
recurrence relation with characteristic polynomial $p(x(x-1))$. Using this
fact and the induction hypothesis, we have the following

$\begin{split}\sum_{j=1}^{2k+1}d_{j-1}t_{\ell+1+j}&=\sum_{i=1}^{2k+1}d_{j-1}(t_{\ell+1+j}-t_{\ell+j})+\sum_{i=1}^{2k+1}d_{j-1}t_{\ell+j}\\\
&=\sum_{j=1}^{2k+1}d_{j-1}r^{0}_{\ell+1+j}+\sum_{j=1}^{2k+1}d_{j-1}t_{\ell+j}=0+0=0\end{split}$
(10)

This completes the proof. ∎

##  5\. Proof of Theorem 1

In the previous section, we made some general observations on Pascal-like
sets. Now, in order to use them, we show that the numbers $r_{k,n}^{d}$ form
Pascal-like sets – as in (O1). Next, in order to formally prove (O3), we prove
that (3) holds in general.

######  Lemma 12.

Let $n,k\in\mathbb{N}$. Then

$r_{k+1,n+1}^{n}=t_{k,n}:=\sum_{i=1}^{n}r_{k,i}^{0}.$

###### Proof.

First, recall that the upper index $0$ in the expression $r_{k,n}^{0}$
indicates counting maximal $k\mathcal{S}$ sets. Observe that every element of
$\mathcal{R}_{k+1,n+1}^{n}$ is the union of two sets: The first is a maximal
$k\mathcal{S}$ set with a maximum at most $n-1$. The second is $\\{n+1\\}$.
Consider the following map

$\mathcal{R}_{k+1,n+1}^{n}\ni F\mapsto
F\backslash\\{n+1\\}\in\bigcup_{i=1}^{n}\mathcal{R}_{k,i}^{0}.$

The map is clearly bijective ("$i$" can be interpreted as the second largest
element of $F$) and the families under the union in the co-domain are pairwise
disjoint. ∎

######  Lemma 13.

Let $k\in\mathbb{N}$, $n\in\mathbb{N}$ with $n\geqslant 3$, and
$d\in\\{0,\cdots,n-3\\}$. Then

$r_{k,n}^{d}=r_{k,n-1}^{d}+r_{k,n-1}^{d+1}.$

Hence, the set $\\{r_{k,i}^{j}:i\in\mathbb{N},j\in\\{0,\cdots i-1\\}\\}$ is a
Pascal-like. Moreover, $r^{j-1}_{k,j+1}=0$ for each $j\in\mathbb{N}$.

###### Proof.

Define

$\displaystyle\mathcal{T}_{1}:=\\{F\in\mathcal{R}_{k,n}^{d}\ :\ n-1\in F\\},$
$\displaystyle\ \ \ \ \ \ \mathcal{T}_{2}:=\\{F\in\mathcal{R}_{k,n}^{d}\ :\
n-1\notin F\\},$
$\displaystyle\mathcal{T}_{1}^{\prime}:=\\{F\backslash\\{n\\}\ :\
F\in\mathcal{T}_{1}\\},$ $\displaystyle\ \ \ \ \ \
\mathcal{T}_{2}^{\prime}:=\\{F\backslash\\{n\\}\cup\\{n-1\\}\ :\
F\in\mathcal{T}_{2}\\}.$

Clearly, we have $|\mathcal{T}_{1}|=|\mathcal{T}_{1}^{\prime}|$ and
$|\mathcal{T}_{2}|=|\mathcal{T}_{2}^{\prime}|$. Hence,
$r_{k,n}^{d}=|\mathcal{T}_{1}|+|\mathcal{T}_{2}|=|\mathcal{T}_{1}^{\prime}|+|\mathcal{T}_{2}^{\prime}|$.
Consider some $F\in\mathcal{R}_{k,n}^{d}$, we claim that $|E_{k}(F)|>1$. If
$E_{k}(F)=\\{n\\}$, then $d_{k}(F)=n-1$, but we assumed that $d<n-1$, which is
a contradiction. Comparing the sets $E_{k}(F)$ and $E_{k}(F^{\prime})$, where
$F^{\prime}$ is the set $F$ modified in one of two presented ways, it can be
easily checked that $\mathcal{T}_{1}^{\prime}=\mathcal{R}_{k,n-1}^{d+1}$ and
$\mathcal{T}_{2}^{\prime}=\mathcal{R}_{k,n-1}^{d}$. This concludes the proof
of the first part.

We will show that for each $n\in\mathbb{N}$, we have
$\mathcal{R}_{k,n+1}^{n-1}=\emptyset$. We know that if
$F\in\mathcal{R}_{k,n+1}^{n-1}$ we have $n+1\in E_{k}(F)$ and, by definition,
$d_{k}(F)=n-1$. We obtain contradictions for all possible values of $\min
E_{k}(F)$. If $\min E_{k}(F)\leqslant n$, using that $n+1\in E_{k}(F)$, we
have $d_{k}(F)\leqslant n-2$. If $n+1=\min E_{k}(F)$, then $d_{k}(F)=n$. ∎

######  Lemma 14.

Let $k,n\in\mathbb{N}$ with $n\geqslant 2$. We have

$s_{k,n}=2s_{k,n-1}-r_{k,n-1}^{0}.$

###### Proof.

Define

$\displaystyle\mathcal{T}_{1}$ $\displaystyle:=\\{F\cup\\{n\\}\ :\
F\in(k\mathcal{S})^{n-1}\backslash\mathcal{R}_{k,n-1}^{0}\\},$
$\displaystyle\mathcal{T}_{2}$
$\displaystyle:=\\{F\backslash\\{n-1\\}\cup\\{n\\}\ :\
F\in(k\mathcal{S})^{n-1}\\}.$

We claim that $(k\mathcal{S})^{n}=\mathcal{T}_{1}\cup\mathcal{T}_{2}$. Then,
by the fact that $\mathcal{T}_{1}\cap\mathcal{T}_{2}=\emptyset$, we obtain

$s_{k,n}=|(k\mathcal{S})^{n}|=|\mathcal{T}_{1}|+|\mathcal{T}_{2}|=(s_{k,n-1}-r_{k,n-1}^{0})+s_{k,n-1}.$

For each $G\in(k\mathcal{S})^{n}$ we have
$F=G\backslash\\{n\\}\cup\\{n-1\\}\in(k\mathcal{S})^{n-1}$. If $n-1\in G$,
$F=G\setminus\\{n\\}$. Since $G\in(k\mathcal{S})^{n}$, $F$ is not a maximal
$k$-Schreier set. Hence, $G\in T_{1}$. If $n-1\not\in G$, $G\in T_{2}$. It
follows that $(k\mathcal{S})^{n}\subseteq\mathcal{T}_{1}\cup\mathcal{T}_{2}$.
The inclusion $\mathcal{T}_{2}\subseteq(k\mathcal{S})^{n}$ is obvious. It
suffices to prove that $\mathcal{T}_{1}\subseteq(k\mathcal{S})^{n}$, however,
this is almost obvious – adding one element larger than the maximum to a non-
maximal $k$-Schreier produces a $k$-Schreier set. ∎

We are now ready to proceed to the proof of Theorem 1.

###### Proof of Theorem 1.

We claim that for each $k\in\mathbb{N}$, the sequence $(s_{k,n})$ satisfies a
linear recurrence with characteristic polynomial $p_{k}(x)$. This claim has
already been established in previous work for $k=1$; however, we will not use
this statement directly. Instead, we prove the following statement holds for
each natural number $k$.

  * (Pk):

The sequences $(r^{0}_{k,i})_{i=1}^{\infty},(t_{k,i})_{i=1}^{\infty}$ satisfy
a linear recurrence with characteristic polynomial $p_{k}(x)$.

Consider the base case $k=1$. Note that $r_{1,n}^{n-1}=1$ for each
$n\in\mathbb{N}$ since $F\in\mathcal{R}_{1,n}^{n-1}$ if and only if
$F=\\{n\\}$. Therefore $(r_{1,n}^{n-1})$ satisfies a linear recurrence with
characteristic polynomial $p_{0}(x)=x-1$ and the same holds for
$(r_{1,n+1}^{n-1})_{n=1}^{\infty}$ since this sequence is identically 0 (Lemma
13). Therefore by Lemma 10, $(r^{0}_{1,i})_{i=1}^{\infty}$ satisfies a linear
recurrence with characteristic polynomial $p_{0}(x(x-1))=x(x-1)-1=p_{1}(x)$.
Notice that (8) is satisfied by Lemma 7 for $k=1$. Therefore we may apply
Lemma 11 to see that $(t_{1,i})_{i=1}^{\infty}$ satisfies a linear recurrence
with characteristic polynomial $p_{1}(x)$. Therefore (P1) holds.

Fix a positive integer $k$ and assume that (Pk) holds; we will prove that
(Pk+1) holds. By Lemma 12, we have that $t_{k,i}=r_{k+1,i+1}^{i}$ for each
$i\in\mathbb{N}$. Therefore, $(r_{k+1,i+1}^{i})_{i=1}^{\infty}$ satisfies a
linear recurrence with characteristic polynomial $p_{k}(x)$. We want to show
that $(r_{k+1,i}^{i-1})_{i=1}^{\infty}$ satisfies a linear recurrence with
characteristic polynomial $p_{k}(x)$; this is just the sequence in the
previous sentence starting with $r_{k+1,1}^{0}$. Notice that
$r_{k+1,1}^{0}=0$. Therefore, by Lemma 7,

$\sum_{i=0}^{2^{k}}d^{k}_{i}r_{k+1,i+1}^{i}=\sum_{i=1}^{2^{k}}d^{k}_{i}t_{k,i}=0.$

Therefore the initial conditions are satisfied and so
$(r_{k+1,i}^{i-1})_{i=1}^{\infty}$ satisfies a linear recurrence with
characteristic polynomial $p_{k}(x)$.

By Lemma 13, we have $r_{k+1,i+1}^{i-1}=0$ for each $i\in\mathbb{N}$. Thus we
may apply Lemma 10 to conclude that $(r^{0}_{k+1,i})_{i=1}^{\infty}$ satisfies
a linear recurrence with characteristic polynomial $p_{k+1}(x)$. In addition,
by Lemma 7, the assumptions of Lemma 11 are satisfied, and obtain that
$(t_{k+1,i})_{i=1}^{\infty}$ satisfies a linear recurrence with characteristic
polynomial $p_{k+1}(x)$. This concludes the inductive step.

Fix $k\in\mathbb{N}$. It remains to prove that $(s_{k,n})_{n=1}^{\infty}$
satisfies a linear recurrence with characteristic polynomial $p_{k}(x)$. It
suffices to show that for each non-negative integer $\ell$, we have

$\sum_{i=0}^{2^{k}}d^{k}_{i}s_{k,\ell+i+1}=0.$ (11)

By Lemma 7, the $\ell=0$ case holds. Suppose (11) holds for some non-negative
$\ell$. Using Lemma 14, and the statement (Pk), we have

$\sum_{i=0}^{2^{k}}d^{k}_{i}s_{k,\ell+i+2}=2\sum_{i=0}^{2^{k}}d^{k}_{i}s_{k,\ell+i+1}-\sum_{i=0}^{2^{k}}d^{k}_{i}r^{0}_{k,\ell+i+1}=0-0.$
(12)

This finishes the proof of the theorem. Note that Corollary 2 follows from the
initial induction in the proof – statements (Pk). ∎

##  6\. Concluding remarks

It seems there are many interesting open problems similar to the one we
studied. For example, there is another important regular family
$\mathcal{S}_{2}$, which is the convolution of $\mathcal{S}$ with itself. That
is, a subset of natural numbers $F$ is in $\mathcal{S}_{2}$ if there exist
disjoint nonempty sets $E_{1},\dots,E_{\ell}\in\mathcal{S}$ such that

$\bigcup_{i=1}^{\ell}E_{i}=F,\ \ \mathrm{and}\ \ \\{\min
E_{i}:i\in\\{1,\ldots,\ell\\}\\}\in\mathcal{S}.$

The family $\mathcal{S}_{2}$ also appears naturally in Banach space theory
[1].

######  Problem 15.

Is the sequence $(|\mathcal{S}_{2}^{n}|)_{n=1}^{\infty}$ a linear recurrence
sequence? If yes, then what is the recursive relation?

## References

  * [1] D. E. Alspach and S. Argyros.  Complexity of weakly null sequences.  Dissertationes Math. (Rozprawy Mat.), 321:44, 1992.
  * [2] S. A. Argyros and S. Todorcevic.  Ramsey methods in analysis.  Advanced Courses in Mathematics. CRM Barcelona. Birkhäuser Verlag, Basel, 2005.
  * [3] K. Beanland, H. V. Chu, and C. E. Finch-Smith.  Generalized Schreier sets, linear recurrence relation, and Turán graphs.  Fibonacci Quart., 60(4):352–356, 2022.
  * [4] K. Beanland and J. Hodor.  The depth of Tsirelson’s norm.  arXiv, 2023.  arXiv:2306.10344.
  * [5] H. V. Chu.  The Fibonacci sequence and Schreier-Zeckendorf sets.  J. Integer Seq., 22(6):Art. 19.6.5, 12, 2019.
  * [6] H. V. Chu.  Various sequences from counting subsets.  Fibonacci Quart., 59(2):152–157, 2021.
  * [7] H. V. Chu.  On a relation between Schreier-type sets and a modification of Turán graphs.  Integers, 23:Paper No. A20, 10, 2023.
  * [8] H. V. Chu, S. J. Miller, and Z. Xiang.  Higher order Fibonacci sequences from generalized Schreier sets.  Fibonacci Quart., 58(3):249–253, 2020.
  * [9] E. Odell.  Ordinal indices in Banach spaces.  Extracta Math., 19(1):93–125, 2004.
  * [10] J. Schreier.  Ein Gegenbeispiel zur Theorie der schwachen Konvergenz.  Studia Mathematica, 2(1):58–62, 1930.