1 Introduction
A subset F of positive integers is called a Schreier set if it is nonempty and
$|F| \leq \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$
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 Schreier [Reference Schreier10]. In that paper, Schreier solved a problem in Banach space theory posed by Banach and Saks. It is now well established that Schreier sets and their generalisations have deep connections to the norm convergence of convex combinations of weakly null sequences [Reference Alspach and Argyros1, Reference Argyros and Todorcevic2, Reference Odell9] and are thus of fundamental importance in Banach space theory.
In this paper, we focus on the combinatorial properties of Schreier sets. Recently, counting various generalisations of Schreier sets has attracted attention (see [Reference Beanland, Chu and Finch-Smith3, Reference Chu5, Reference Chu6, Reference Chu7]. Research in this direction began with the simple observation by an anonymous blogger that
$(|\mathcal {S}^n|)_{n=1}^\infty $
is the Fibonacci sequence. This fact follows from the observation that the set of 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}$
. The blogger was later revealed to be Alistair Bird who discovered this connection while writing his PhD thesis in Banach space theory.
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
$$ \begin{align*}\mathcal{S}_{p, q}=\{F \subset \mathbb{N}: q \min F \geqslant p |F|\}.\end{align*} $$
In [Reference Beanland, Chu and Finch-Smith3], Beanland et al. proved that the sequence
$(|\mathcal {S}^n_{p,q}|)_{n=1}^\infty $
is a linear recurrence sequence and gave a compact recursive formula (building on the earlier work [Reference Chu, Miller and Xiang8]).
We write
$\mathbb {N}$
for the set of all positive integers and we refer to members of
$\mathbb {N}$
as natural numbers. 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 [Reference Beanland and Hodor4] by the first and third authors.
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},\ldots ,c_0$
(we assume that
$c_k\not =0$
) if for each
$n \in \mathbb {N}$
,
$$ \begin{align*} c_k a_{n+k}+c_{k-1}a_{n+k-1} + \cdots + c_1 a_{n+1}+ c_0 a_n = 0.\end{align*} $$
The characteristic polynomial of the linear recurrence is given by
$$ \begin{align*} p(x)=c_kx^k +c_{k-1}x^{k-1} + \cdots +c_1 x +c_0.\end{align*} $$
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 nonnegative integer k, and let
$$ \begin{align*} p_{k+1}(x):= p_k(x(x-1)). \end{align*} $$
Below we have computed
$p_k(x)$
for each
$k \in \{1,2,3\}$
:
-
(1)
$p_1(x) = x(x-1)-1= x^2-x-1$
, the characteristic polynomial of the Fibonacci recursion; -
(2)
$p_2(x) = x^2(x-1)^2-x(x-1) - 1= x^4-2x^3+x -1$
; -
(3)
$p_3(x) = x^8 - 4 x^7 + 4 x^6 + 2 x^5 - 5 x^4 + 2 x^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.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 $
in a nonobvious but elegant way. In addition, we obtain an interesting corollary to the proof of Theorem 1.1. In order to state it, we need some more notation. For two sets
$E,F \subset \mathbb {N}$
, we write
$E<F$
if
$\max E < \min F$
. We say that sets
$E_1,\dots ,E_m \subset \mathbb {N}$
are successive if
$E_1 < E_2 < \cdots < 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 successive maximal Schreier sets. Let
$\mathcal {R}_{k,n}^0\subset (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 1.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.1
Let
$F\subset \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
$$ \begin{align*}E_{k+1}(F) = E_1\bigg(F \setminus \bigcup_{i=1}^k E_i(F)\bigg).\end{align*} $$
Observe that
$E_1(F), E_2(F),\ldots $
is a partition of F into consecutive Schreier sets, where all nonempty sets are maximal except possibly for the last nonempty one.
Let
$k\in \mathbb {N}$
and
$F \in k\mathcal {S}$
. Let
$d_k(F)$
be the greatest nonnegative integer d so that there is a set
$G\subset \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)
$d_k(F)<\infty $
if and only if
$E_k(F)\not =\emptyset $
; -
(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
$$ \begin{align*} \mathcal{R}_{k,n}^d := \{ F \in (kS)^n : d_k(F) = d \} \quad \mbox{and} \quad r_{k,n}^d := |\mathcal{R}_{k,n}^d|. \end{align*} $$
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.
The left table contains initial values of
$(r_{1,n}^d)$
; the right table contains initial values of
$(r_{2,n}^d)$
.
For example, for the
$k=1$
table, the value
$r^0_{1,n}$
is the cardinality of the set of all F so that
$\max F=n$
and F is a maximal Schreier set (that is,
$\min F=|F|$
). For the second column, the value
$r^1_{1,n}$
is the number of sets F with
$\max F =n$
so that
$F\cup \{n+1\}$
is a maximal Schreier set. For the
$k=2$
table, the value
$r^1_{2,n}$
is the number of sets F so that
$F=F_1\cup F_2$
with
$F_1<F_2$
,
$F_1$
being a maximal Schreier set,
$\max F_2=n$
, and
$F_2\cup \{n+1\}$
being a maximal Schreier set. For example
$$ \begin{align*}r^1_{2,6}=|\mathcal{R}^1_{2,6}|=|\{\{1,3,6\},\{1,4,5,6\},\{2,3,4,5,6\}\}|=3.\end{align*} $$
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 that this holds in general (Lemma 5.2).
(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 4.1 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 5.1). 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
$k=1$
table, 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
$$ \begin{align} s_{k,n} = 2s_{k,n-1} - r_{k,n-1}^0. \end{align} $$
3 Initial values of the sequences
This section contains several computations related to the initial values of the sequences we are considering.
Lemma 3.1. For all
$k \in \mathbb {N}$
with
$k\geqslant 2$
and for each
$n \in \{1,\ldots , 2^k-2\}$
, we have
$r_{k,n}^0 = 0$
. Moreover,
$$ \begin{align*}r_{k,2^k-1}^0 = 1 , \quad r_{k,2^k}^0 = 2^{k-1}-1, \quad r_{k,2^k+1}^0= \binom{2^{k-1}}{2} + 2^{k-2}. \end{align*} $$
Proof. Since
$\{1,\ldots , 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,\ldots , 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,\ldots , 2^k\}\setminus \{n\}$
is a maximal k-Schreier set for each
$n \in \{2^{k-1}+1,\ldots , 2^k-1\}$
, and every such set is of this form. To compute
$r_{k,2^k+1}^0$
, one can easily check 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, \ldots , 2^{k}\}$
or deleting one number from
$\{2^{k-2}+1,\ldots ,2^{k-1}\}$
.
The next lemma follows trivially from Lemma 3.1. For all
$n, k \in \mathbb {N}$
, set
$$ \begin{align*} t_{k,n} := \sum_{i=1}^{n} r_{k,i}^0.\end{align*} $$
Lemma 3.2. For all
$k \in \mathbb {N}$
with
$k \geqslant 2$
and for each
$n \in \{1,\ldots , 2^k-2\}$
, we have
$t_{k,n} = 0$
. Moreover,
$$ \begin{align*}t_{k,2^k-1} = 1 , \quad t_{k,2^k} = 2^{k-1}, \quad t_{k,2^k+1}= 2^{k-1} + \binom{2^{k-1}}{2} + 2^{k-2}. \end{align*} $$
Lemma 3.3. For all
$k \in \mathbb {N}$
and for each
$n \in \{1,\ldots , 2^k-1\}$
, we have
$s_{k,n} = 2^{n-1}$
. Moreover,
$$ \begin{align*}s_{k,2^k}^0 = 2^{2^k-1}-1 , \quad s_{k,2^k+1} = 2^{2^k}-(2^{k-1}+1). \end{align*} $$
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 a 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 each of its proper subsets is 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$
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}\} \subset 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$
, which is a contradiction. Therefore,
$\min E_k(F)=2^{k-1}$
, and since
$2^k-1 \leq \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}$
, define
$(d^k_{i})_{i=0}^{2^k}$
by
$$ \begin{align*}p_k(x)= \sum_{i=0}^{2^k} d^k_i x^i.\end{align*} $$
Lemma 3.4. Let
$k \in \mathbb {N}$
with
$k \geqslant 2$
. Then
$$ \begin{align*}d_{2^k-2}^k = \binom{2^{k-1}}{2} -2^{k-2}, \quad d^k_{2^k-1}=-2^{k-1}, \quad d^k_{2^k}=1. \end{align*} $$
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
$$ \begin{align*}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 .\end{align*} $$
By inspection of the leading coefficients and using the binomial theorem, we have
$$ \begin{align*}p_k(x) = x^{2m} -mx^{2m-1} + \bigg(\, \binom{m}{2} - \frac{m}{2}\bigg)x^{2m-2} + \cdots .\end{align*} $$
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.1.
Lemma 3.5. For each
$k \in \mathbb {N}$
,
$$ \begin{align*}\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.\end{align*} $$
Proof. Direct calculation using the above lemmas shows 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 3.3 and 3.4,
$$ \begin{align*} 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}.\\[-46.2pt] \end{align*} $$
4 Pascal-like sets and recursions
A set
$\{r^j_{i}:i \in \mathbb {N}, j\in \{0,\ldots , i-1\}\}$
is Pascal-like if for every
$i \in \mathbb {N}$
with
$i\geqslant 3$
and every
$j \in \{0,\ldots , 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.
An initial fragment of a Pascal-like set. The cells of a table are filled with the numbers
$r_i^j$
, for example,
$r_6^1 = 7$
. The set is determined by two main diagonals highlighted with shading.
Lemma 4.1. Let
$\{r_{i}^{j}:i \in \mathbb {N}, j\in \{0,\ldots , i-1\}\}$
be a Pascal-like set. Then for each
$n \in \mathbb {N}$
,
$$ \begin{align} r_{n}^{n-1} = \sum_{j=0}^{n-1} (-1)^{n-1-j} \binom{n-1}{j} r^0_{n+j}. \end{align} $$
Proof. We proceed by induction. We shall prove that for each
$n\in \mathbb {N}$
, any Pascal-like set satisfies (4.1). For
$n = 1$
, the assertion is clearly satisfied. Fix
$n \geqslant 2$
and assume that (4.1) 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,\ldots , i-1\}\}$
and define
$b_{i}^{j} = r_{i+1}^{j+1}$
. Then
$\{b_{i}^{j}:i \in \mathbb {N}, j\in \{0,\ldots , i-1\}\}$
is also a Pascal-like set. By the inductive assumption,
$$ \begin{align*} r_{n}^{n-1} = b_{n-1}^{n-2} &= \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} \\ &= \sum_{j=0}^{n-2} (-1)^{n-2-j} \binom{n-2}{j} (r^0_{n+j+1} - r^0_{n+j}) \\ &= \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} \\ &= \sum_{j=0}^{n-1} (-1)^{n-1-j} \binom{n-1}{j} r^0_{n+j}. \end{align*} $$
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 4.2 we show how recursive relations are transferred between diagonals and in Lemma 4.3 we show how recursive relations are transferred from the main diagonals to the first column (see Figure 2 for intuition). Next, in Lemma 4.4, we relate the recursive relation on the main diagonals to the partial sums of the first column.
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 4.2. Let
$\{r_{i}^{j}:i \in \mathbb {N}, j\in \{0,\ldots , 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
$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.
Lemma 4.3. Suppose that
$\{r^j_{i}:i \in \mathbb {N}, j\in \{0,\ldots , 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_kx^k + c_{k-1}x^{k-1} + \cdots c_1x+ 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 nonnegative integer
$\ell $
,
$$ \begin{align*} \sum_{i=1}^{2k+1}d_{i-1}r^0_{\ell+i} =0. \end{align*} $$
Fix some nonnegative integer
$\ell $
. From the definition,
$\{r^j_{\ell +i}: i \in \mathbb {N}, j \in \{0, \ldots ,i-1\}\}$
is Pascal-like. Therefore, by Lemma 4.2,
$\sum _{i=0}^kc_ir^i_{\ell +i+1} = 0$
. Using Lemma 4.1, we rewrite this sum as
$$ \begin{align} 0=\sum_{i=0}^kc_ir^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}. \end{align} $$
Since (4.2) is satisfied, there are coefficients
$(d^{\prime }_i)_{i=0}^{2k}$
such that
$\sum _{i=1}^{2k+1}d^{\prime }_{i-1}r^0_{\ell +i}=0$
(for each nonnegative 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 (4.2) and apply the binomial theorem to obtain
$$ \begin{align*}\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}.\end{align*} $$
Therefore,
$d^{\prime }_i=d_i$
as desired.
Lemma 4.4. Let
$\{r^j_{i}:i \in \mathbb {N}, j\in \{0,\ldots , 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
$$ \begin{align} \sum_{j=1}^{2k+1}d_{j-1} t_j=0. \end{align} $$
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 nonnegative integer
$\ell $
,
$$ \begin{align} \sum_{j=1}^{2k+1}d_{j-1} t_{\ell+j}=0. \end{align} $$
The base case of the induction
$\ell =0$
is just (4.3).
Suppose that for some
$\ell \geqslant 0$
, (4.4) holds. We will show that (4.4) holds for
$\ell +1$
. By Lemma 4.3,
$(r^0_i)_{i=1}^\infty $
satisfies the recurrence relation with characteristic polynomial
$p(x(x-1))$
. Using this fact and the induction hypothesis,
$$ \begin{align*} \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} \end{align*} $$
This completes the proof.
5 Proof of Theorem 1.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 (2.1) holds in general.
Lemma 5.1. Let
$n,k \in \mathbb {N}$
. Then
$$ \begin{align*}r_{k+1,n+1}^{n} = t_{k,n}:= \sum_{i=1}^{n} r_{k,i}^0.\end{align*} $$
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 map
$$ \begin{align*} \mathcal{R}_{k+1,n+1}^{n} \ni F \mapsto F \backslash \{n+1\} \in \bigcup_{i=1}^{n} \mathcal{R}_{k,i}^0.\end{align*} $$
The map is clearly bijective (i can be interpreted as the second largest element of F) and the families under the union in the codomain are pairwise disjoint.
Lemma 5.2. Let
$k \in \mathbb {N}$
,
$n \in \mathbb {N}$
with
$n\geqslant 3$
and
$d \in \{0,\ldots , n-3\}$
. Then
$$ \begin{align*} r_{k,n}^d = r_{k,n-1}^d + r_{k,n-1}^{d+1}. \end{align*} $$
Hence, the set
$\{r_{k,i}^{j}:i\in \mathbb {N}, j\in \{0,\ldots i-1\}\}$
is Pascal-like. Moreover,
$r^{j-1}_{k,j+1}=0$
for each
$j \in \mathbb {N}$
.
Proof. Define
$$ \begin{align*} \mathcal{T}_1 := \{F \in \mathcal{R}_{k,n}^{d} :n-1 \in F\}, & \quad \mathcal{T}_2 := \{F \in \mathcal{R}_{k,n}^{d} : n-1 \notin F\},\\ \mathcal{T}_1' := \{F \backslash \{n\} : F \in \mathcal{T}_1 \}, & \quad \mathcal{T}_2' := \{F \backslash \{n\} \cup \{n-1\} :F \in \mathcal{T}_2 \}. \end{align*} $$
Clearly, we have
$|\mathcal {T}_1|=|\mathcal {T}_1'|$
and
$|\mathcal {T}_2|=|\mathcal {T}_2'|$
. Hence,
$r_{k,n}^d = |\mathcal {T}_1| + |\mathcal {T}_2| = |\mathcal {T}_1'| + |\mathcal {T}_2'|$
. 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')$
, where
$F'$
is the set F modified in one of two presented ways, it can be easily checked that
$\mathcal {T}_1' = \mathcal {R}_{k,n-1}^{d+1}$
and
$\mathcal {T}_2' = \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
$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 5.3. Let
$k,n \in \mathbb {N}$
with
$n \geqslant 2$
. We have
$$ \begin{align*}s_{k,n}=2s_{k,n-1}-r_{k,n-1}^0.\end{align*} $$
Proof. Define
$$ \begin{align*} \mathcal{T}_1 := \{F \cup \{n\} : F \in (k\mathcal{S})^{n-1} \backslash \mathcal{R}_{k,n-1}^0 \}, \quad \mathcal{T}_2 := \{F \backslash \{n-1\} \cup \{n\} : F \in (k\mathcal{S})^{n-1} \}. \end{align*} $$
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
$$ \begin{align*}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}.\end{align*} $$
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$
, then
$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$
, then
$G \in T_2$
. It follows that
$(k\mathcal {S})^n \subset \mathcal {T}_1 \cup \mathcal {T}_2$
. The inclusion
$\mathcal {T}_2 \subset (k\mathcal {S})^n$
is obvious. It suffices to prove that
$\mathcal {T}_1 \subset (k\mathcal {S})^n$
; however, this is almost obvious. Adding one element larger than the maximum to a nonmaximal k-Schreier set produces a k-Schreier set.
We are now ready to proceed to the proof of Theorem 1.1.
Proof of Theorem 1.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 the 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.
-
(P k ): 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 5.2). Therefore, by Lemma 4.3,
$(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 (4.3) is satisfied by Lemma 3.5 for
$k=1$
. Therefore, we may apply Lemma 4.4 to see that
$(t_{1,i})_{i=1}^\infty $
satisfies a linear recurrence with characteristic polynomial
$p_1(x)$
. Therefore, (P
$_1$
) holds.
Fix a positive integer k and assume that (P
$_k$
) holds; we will prove that (P
$_{k+1}$
) holds. By Lemma 5.1,
$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 3.5,
$$ \begin{align*}\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.\end{align*} $$
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 5.2,
$r_{k+1,i+1}^{i-1}=0$
for each
$i \in \mathbb {N}$
. Thus we may apply Lemma 4.3 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 3.5, the assumptions of Lemma 4.4 are satisfied, so
$(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 nonnegative integer
$\ell $
,
$$ \begin{align} \sum_{i=0}^{2^k}d^k_{i} s_{k,\ell+i+1} =0. \end{align} $$
By Lemma 3.5, the
$\ell =0$
case holds. Suppose (5.1) holds for some nonnegative
$\ell $
. Using Lemma 5.3 and the statement (P
$_k$
), we have
$$ \begin{align*} \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. \end{align*} $$
This finishes the proof of the theorem. Note that Corollary 1.2 follows from the initial induction in the proof for the statements (P
$_k$
).
6 Concluding remarks
It seems there are many interesting open problems similar to the one we have 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
$$ \begin{align*} \bigcup_{i=1}^\ell E_i = F \quad\mathrm{and} \quad {\{\min E_i : i \in \{1, \ldots, \ell\}\}} \in \mathcal{S}. \end{align*} $$
The family
$\mathcal {S}_2$
also appears naturally in Banach space theory [Reference Alspach and Argyros1].
Problem 6.1. Is the sequence
$(|\mathcal {S}_2^n|)_{n=1}^\infty $
a linear recurrence sequence? If yes, then what is the recursive relation?
