# How to bowl properly

Fabián Arias111Facultad de Ciencias Básicas, Universidad Tecnológica de
Bolívar, Colombia; email address<EMAIL_ADDRESS>Jerson
Borja222Departamento de Matemáticas, Universidad de Córdoba, Colombia; email
address<EMAIL_ADDRESS>
# The Frobenius problem for numerical semigroups generated by sequences that
satisfy a linear recurrence relation

Fabián Arias111Facultad de Ciencias Básicas, Universidad Tecnológica de
Bolívar, Colombia; email address<EMAIL_ADDRESS>Jerson
Borja222Departamento de Matemáticas, Universidad de Córdoba, Colombia; email
address<EMAIL_ADDRESS>
###### Abstract

Consider a sequence of positive integers of the form $ca^{n}-d$, $n\geq 1$,
where $a,c$ and $d$ are positive integers, $a>1$. For each $n\geq 1$, let
$S_{n}$ be the submonoid of $\mathbb{N}$ generated by
$\mathbf{s}_{j}=ca^{n+j}-d$, with $j\in\mathbb{N}$. We obtain a numerical
semigroup $(1/e)S_{n}$ by dividing every element of $S_{n}$ by
$e=\gcd(S_{n})$.

We characterize the embedding dimension of $S_{n}$ and describe a method to
find the minimal generating set of $S_{n}$. We also show how to find the
maximum element of the Apéry set ${\rm Ap}(S_{n},\mathbf{s}_{0})$,
characterize the elements of ${\rm Ap}(S_{n},\mathbf{s}_{0})$, and use these
results to compute the Frobenius number of the numerical semigroup
$(1/e)S_{n}$, where $e=\gcd(S_{n})$.

Keywords— Frobenius problem, numerical semigroup, recurrence relation.

##  1 Introduction

#### Numerical semigroups and submonoids of $\mathbb{N}$.

Let $\mathbb{N}=\\{0,1,\ldots\\}$ be the set of natural numbers and
$\mathbb{Z}$ be the set of integer numbers. A numerical semigroup is a subset
$S$ of $\mathbb{N}$ that is closed under addition, $0\in S$, and
$\mathbb{N}\setminus S$ is a finite set. For a subset $A$ of $\mathbb{N}$, we
denote by $\langle A\rangle$ the submonoid of $\mathbb{N}$ generated by $A$:

$\langle
A\rangle=\left\\{\sum_{j=1}^{n}c_{j}\mathbf{a}_{j}:n\in\mathbb{N}\setminus\\{0\\},c_{j}\in\mathbb{N},\mathbf{a}_{j}\in
A\text{ for }j=1,\ldots,n\right\\}.$

It is known that $\langle A\rangle$ is a numerical semigroup if and only if
${\gcd}(A)=1$ (see [6]).

Let $M$ be a nontrivial submonoid of $\mathbb{N}$. Then, $M$ is finitely
generated and, in fact, there exists a subset of $M$ that generates $M$ and
any other generating set of $M$ contains it; such generating set is called the
minimal generating set of $M$ and its elements, that are called the minimal
generators of $M$, are precisely the nonzero elements belonging to $M$ that
cannot be written as sum of two nonzero elements in $M$. We denote by $e(M)$
the number of minimal generators of $M$.

If $S$ is a numerical semigroup, we call $e(S)$ the embedding dimension of
$S$. The maximum element in $\mathbb{N}\setminus S$ is called the Frobenius
number of $S$, which is denoted ${\rm F}(S)$ and the cardinality of
$\mathbb{N}\setminus S$ is the genus of $S$, which is denoted by ${\rm g}(S)$.

Assume again that $M$ is a nontrivial submonoid of $\mathbb{N}$. If $x\in
M\setminus\\{0\\}$, the Apéry set of $x$ in $M$, denoted by ${\rm Ap}(M,x)$,
is defined by ${\rm Ap}(M,x)=\\{m\in M:m-x\notin M\\}$. If $d=\gcd(M)$ and $S$
is the numerical semigroup obtained by dividing every element in $M$ by $d$,
then we have the relation ${\rm Ap}(M,x)=\\{ds:s\in{\rm Ap}(S,x/d)\\}$. If $S$
is a numerical semigroup and $x\in S\setminus\\{0\\}$, then ${\rm
Ap}(S,x)=\\{w(0),\ldots,w(x-1)\\}$, where $w(i)$ is the least element in $S$
congruent to $i$ modulo $x$; we also have the following two properties:

  1. 1.

${\rm F}(S)=\max{\rm Ap}(S,x)-x$,

  2. 2.

$\displaystyle{\rm g}(S)=\frac{1}{x}\left(\sum_{s\in{\rm
Ap}(S,x)}s\right)-\frac{x-1}{2}$.

All these concepts and results can be consulted in [6].

#### Submonoids and numerical semigroups generated by tails of sequences.

Let us consider a sequence $(x_{n})_{n\geq 1}$ of positive integers, which we
will call the generating sequence. For each $n\geq 1$, the $n-$tail of
$(x_{n})_{n\geq 1}$ is the sequence $(x_{n},x_{n+1},\ldots)$, and we can
define a submonoid $S_{n}$ of $\mathbb{N}$ by
$S_{n}=\langle\\{x_{n+j}:j\in\mathbb{N}\\}\rangle$. As we know, $S_{n}$ is a
numerical semigroup if and only if $\gcd(x_{n},x_{n+1},\ldots)=1$. This way,
we can associate a family of submonoids of $\mathbb{N}$ with a given sequence
of positive integers.

In recent works on numerical semigroups [1, 2, 3, 4, 5, 8, 9], a particular
generating sequence (in some cases a a family of generating sequences)
$(x_{n})_{n\geq 1}$ is given, and for the associated numerical semigroups
$S_{n}$ they find

  1. 1.

the minimal generating set and the embedding dimension of $S_{n}$;

  2. 2.

the Apéry set ${\rm Ap}(S_{n},x_{n})$, the Frobenius number and genus of
$S_{n}$;

  3. 3.

the pseudo-Frobenius numbers and the type of $S_{n}$ (see [6] for the
definitions and related concepts).

In this work, we generalize some ideas and results found in those papers,
related to the calculation of the minimal generating set, embedding dimension,
the Apéry set ${\rm Ap}(S_{n},x_{n})$, the Frobenius number and genus of the
numerical semigroups $S_{n}$ associated with a generating sequence of the form
$x_{n}=ca^{n}-d$, where $a,c$ and $d$ are positive integers. In this work, we
do not tackle the problem of finding pseudo-Frobenius numbers and the type of
$S_{n}$ are given.

#### Presentation of the results.

We fix positive integers $a,c$ and $d$, with $a\geq 2$, and consider a
generating sequence $(x_{n})_{n\geq 1}$ of the form

$x_{n}=ca^{n}-d.$

One first condition on $a,c$ and $d$ is $d<ca$, since we need $x_{1}=ca-d>0$.
For each $n\geq 1$ we let

$S_{n}=\langle\\{x_{n+j}:j\in\mathbb{N}\\}\rangle.$

For simplicity, given $n\geq 1$, we set $\mathbf{s}_{j}=x_{n+j}$, for all
$j\in\mathbb{N}$. So,
$S_{n}=\langle\\{\mathbf{s}_{j}:j\in\mathbb{N}\\}\rangle$. For our purposes,
it will be enough to assume that $d$ is relatively prime to $a$ and $c$
(otherwise, we can divide by an adequate factor to reduce to this case). This
covers the sequences considered in [1, 2, 3, 4, 5, 8, 9] of the form
$ca^{n}-d$, and give us enough generality to unify some ideas, have many new
examples and results. To start, the following conjectures arise from those
known results:

  1. 1.

The minimal generating set of $S_{n}$ has the form $\\{\mathbf{s}_{j}:0\leq
j<m\\}$ for some $m>0$ and, of course, $e(S_{n})=m$. So, it is important to
have a method to determine such integer $m$.

  2. 2.

For all $n\geq 1$, $e(S_{n})\geq n$.

The sequence of generators of $S_{n}$ satisfy the linear recurrence relation

$\mathbf{s}_{j+1}=a\mathbf{s}_{j}+(a-1)d,$ (1)

for all $j\geq 0$. All sequences that appear in [1, 2, 3, 4, 5, 8, 9] satisfy
a relation like (1), which is crucial to the arguments in each case.

First, we show that for all $n\geq 1$, the minimal generating set of $S_{n}$
has the form $\\{\mathbf{s}_{j}:0\leq j<m\\}$, where $m=e(S_{n})$. We also
characterize $e(S_{n})$ as the unique positive integer $m$ such that
$\mathbf{s}_{m}\in\langle\\{\mathbf{s}_{j}:0\leq j<m\\}\rangle$ and
$\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq j<m-1\\}\rangle$. Then,
we describe a method to find a positive integer $m$ such that
$\mathbf{s}_{m}\in\langle\\{\mathbf{s}_{j}:0\leq j<m\\}\rangle$ and conditions
under which $\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq
j<m-1\\}\rangle$. We also prove that $e(S_{n})\geq n$, for all $n\geq 1$.

The characterization of the Apéry set ${\rm Ap}(S_{n},\mathbf{s}_{0})$ is
crucial for finding the Frobenius number and the genus of $S_{n}$. Given an
integer $r\geq 1$, a residual $r-$tuple (here, we use the terminology given in
[3] for such tuples) is a tuple of integer $(\alpha_{1},\ldots,\alpha_{r})$
such that

  1. 1.

$0\leq\alpha_{i}\leq a$ for all $i\in\\{1,\ldots,r\\}$ and

  2. 2.

if $\alpha_{i_{0}}=a$ for some $i_{0}\in\\{2,\ldots,r\\}$, then $\alpha_{i}=0$
for all $i\in\\{1,\dots,i_{0}-1\\}$.

The set of all residual $r-$tuples will be denoted by $A(r)$. The size of
$A(r)$ is $(a^{r+1}-1)/(a-1)$ (see [4, Theorem 12]). An important order
relation on $A(r)$ is the co-lexicographic order $\leq_{c}$ in which
$(\alpha_{1},\ldots,\alpha_{r})\leq_{c}(\beta_{1},\ldots,\beta_{r})$ if,
either, $(\alpha_{1},\ldots,\alpha_{r})=(\beta_{1},\ldots,\beta_{r})$ or there
is some $t\in\\{1,\ldots,r\\}$ such that $\alpha_{t}<\beta_{t}$ and
$\alpha_{j}=\beta_{j}$ for $j=t+1,\ldots,r$.

It is proved in all mentioned papers [1, 2, 3, 4, 5, 8, 9], with the exception
of some atypical cases, that if $m=e(S_{n})$ , then ${\rm
Ap}(S_{n},\mathbf{s}_{0})$ is a subset of the following set:

$\left\\{\sum_{j=1}^{m-1}\beta_{j}\mathbf{s}_{j}:(\beta_{1},\ldots,\beta_{m-1})\in
A(m-1)\right\\}$ (2)

For repunit numerical semigroups (this includes Mersenne numerical semigroups)
the set in (2) coincides with ${\rm Ap}(S_{n},\mathbf{s}_{0})$ in size, which
implies that they are equal. For other generating sequences, the set in (2)
has more elements than ${\rm Ap}(S_{n},\mathbf{s}_{0})$. Then, a subset
$R(m-1)$ of $A(m-1)$ must be appropriately defined so that ${\rm
Ap}(S_{n},\mathbf{s}_{0})$ is a subset of
$\\{\sum_{j=1}^{m-1}\beta_{j}\mathbf{s}_{j}:(\beta_{1},\ldots,\beta_{m-1})\in
R(m-1)\\}$ and the sizes of this last set and ${\rm Ap}(S_{n},\mathbf{s}_{0})$
coincide to conclude that they are equal. To define such subset $R(m-1)$ of
$A(m-1)$, a candidate for the maximum of ${\rm Ap}(S_{n},\mathbf{s}_{0})$ is
given, and a particular residual $(m-1)-$tuple
$(\alpha_{1},\ldots,\alpha_{m-1})$ such that $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=\sum_{j=1}^{m-1}\alpha_{j}\mathbf{s}_{0}$ is found;
and finally, $R(m-1)$ is defined as the set of all residual $(m-1)-$tuples
that are less that or equal to $(\alpha_{1},\ldots,\alpha_{m-1})$ with respect
to the co-lexicographic order. That solves the problem of characterizing the
elements of ${\rm Ap}(S_{n},\mathbf{s}_{0})$ in various of those works, but
they do not show natural way to arrive at such residual $(m-1)-$tuple
$(\alpha_{1},\ldots,\alpha_{m-1})$.

In this work, we show that if $m=e(S_{n})$, then there is a unique residual
$(m-1)-$tuple $(\alpha_{1},\ldots,\alpha_{m-1})$ such that ${\rm
Ap}(S_{n},\mathbf{s}_{0})$ is equal to

$\left\\{\sum_{j=1}^{m-1}\beta_{j}\mathbf{s}_{j}:(\beta_{1},\ldots,\beta_{m-1})\in
A(m-1),(\beta_{1},\ldots,\beta_{m-1})\leq_{c}(\alpha_{1},\ldots,\alpha_{m-1})\right\\}$

and $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=\sum_{j=1}^{m-1}\alpha_{j}\mathbf{s}_{j}$. Moreover,
we show that this residual $(m-1)-$tuple $(\alpha_{1},\ldots,\alpha_{m-1})$ is
the unique that satisfy the relation

$(\mathbf{s}_{0}/e)-1=\sum_{j=1}^{m-1}\alpha_{j}\frac{a^{j}-1}{a-1},$

where $e=\gcd(S_{n})$. This will allow us to determine the residual
$(m-1)-$tuple $(\alpha_{1},\ldots,\alpha_{m-1})$ in a very natural way, as we
will see later.

Finally, we test our results and methods to compute the minimal generating
set, embedding dimension, the Apéry set ${\rm Ap}(S_{n},\mathbf{s}_{0})$,
Frobenius number and genus, on some generating sequences. For instance, we
deal with the generating sequence $(2^{k}-1)2^{n}-1$, when $k>2^{n}$ (this
case was not treated in [2]); we also treat sequences of the form
$(a^{k}-1)a^{n}-1$, for $a\geq 3$ and $k\geq 1$.

##  2 The embedding dimension of $S_{n}$

In this section we prove that the embedding dimension of $S_{n}$ is the unique
positive integer $m$ such that
$\mathbf{s}_{m}\in\langle\\{\mathbf{s}_{j}:0\leq j<m\\}\rangle$ and
$\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq j<m-1\\}\rangle$. The
following lemma is the general version of the corresponding result in [1, 2,
3, 4, 5, 8, 9].

######  Lemma 2.1.

Let $A$ be a nonempty set of positive integers and set $M=\langle A\rangle$.
The following are equivalent:

  1. (1)

$as+(a-1)d\in M$ for all $s\in A$;

  2. (2)

$am+(a-1)d\in M$ for all $m\in M\setminus\\{0\\}$.

We note that if $j\geq 0$, then $a\mathbf{s}_{j}+(a-1)d=\mathbf{s}_{j+1}\in
S_{n}$. By Lemma 2.1, we conclude that $as+(a-1)d\in S_{n}$ for all $s\in
S_{n}\setminus\\{0\\}$.

######  Lemma 2.2.

Let $r>0$ be such that $\mathbf{s}_{r}\in\langle\\{\mathbf{s}_{j}:0\leq
j<r\\}\rangle$. Then $S_{n}=\langle\\{\mathbf{s}_{j}:0\leq j<r\\}\rangle$.

###### Proof.

Let $S=\langle\\{\mathbf{s}_{j}:0\leq j<r\\}\rangle$. We show that
$as+(a-1)d\in S$ for all $s\in S$. In fact, for $0\leq j<r-1$ we have
$a\mathbf{s}_{j}+(a-1)d=\mathbf{s}_{j+1}\in S$. Besides,
$a\mathbf{s}_{r-1}+(a-1)d=\mathbf{s}_{r}\in S$ by hypothesis. Lemma 2.1 gives
us that $as+(a-1)d\in S$ for all $s\in S\setminus\\{0\\}$.

Now, to prove that $S_{n}=S$, it suffices to prove that $\mathbf{s}_{j}\in S$
for all $j\geq 0$. For $j=0$ the result is obvious. Assume that the statement
is true for $j\geq 0$. Since $\mathbf{s}_{j+1}=a\mathbf{s}_{j}+(a-1)d$, we
have $\mathbf{s}_{j+1}\in S$. This ends the proof. ∎

Since $S_{n}$ is finitely generated, it is clear that there is some $m>0$ such
that $\mathbf{s}_{m}\in\langle\\{\mathbf{s}_{j}:0\leq j<m\\}\rangle$ and
$\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq j<m-1\\}\rangle$. The
following theorem is the main result of this section, in which we give the
first characterization of $e(S_{n})$.

######  Theorem 2.3.

Assume that for some $m>0$ it holds that
$\mathbf{s}_{m}\in\langle\\{\mathbf{s}_{j}:0\leq j<m\\}\rangle$ but
$\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq j<m-1\\}\rangle$. Then
$\\{\mathbf{s}_{j}:0\leq j<m\\}$ is the minimal generating set of $S_{n}$. In
particular, $m=e(S_{n})$.

###### Proof.

By Lemma 2.2, the set $\\{\mathbf{s}_{j}:0\leq j<m\\}$ generates $S_{n}$. If
this is not the minimal generating set of $S_{n}$, then there exists
$j_{0}\in\\{0,\ldots,m-1\\}$ such that
$\mathbf{s}_{j_{0}}\in\langle\\{\mathbf{s}_{j}:0\leq j<j_{0}\\}\rangle$. Note
that $j_{0}<m-1$ since $\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq
j<m-1\\}\rangle$. By Lemma 2.2 we have $S_{n}=\langle\\{\mathbf{s}_{j}:0\leq
j<j_{0}\\}\rangle$, but it follows that
$\mathbf{s}_{m-1}\in\langle\\{\mathbf{s}_{j}:0\leq
j<j_{0}\\}\rangle\subseteq\langle\\{\mathbf{s}_{j}:0\leq j<m-1\\}\rangle$,
which is a contradiction. We conclude that $\\{\mathbf{s}_{j}:0\leq j<m\\}$ is
the minimal generating set of $S_{n}$. ∎

It is clear that the positive integer $m$ in Theorem 2.3 is unique, so the
embedding dimension of $S_{n}$ can is the unique $m>0$ such that
$\mathbf{s}_{m}\in\langle\\{\mathbf{s}_{j}:0\leq j<m\\}\rangle$ but
$\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq j<m-1\\}\rangle$.

######  Remark 2.4.

In Theorem 2.3 we only use that $S_{n}$ is a submonoid of $\mathbb{N}$; we do
not need $S_{n}$ to be a numerical semigroup yet. The proofs of Lemmas 2.1 and
2.2, and Theorem 2.3 are true for a generating sequence of the form
$ca^{n}+d$, where $a,c$ and $d$ are positive integers, so the characterization
of $e(S_{n})$ given in Theorem 2.3 is also true for numerical semigroups of
the form $\langle\\{ca^{n+j}+d:j\geq 0\\}\rangle$, where $a,c$ and $d$ are
positive.

In Sections 4 and 5 below, we treat the problem of determining some $m>0$ such
that $\mathbf{s}_{m}$ can be written as linear combination with nonnegative
integer coefficients of $\mathbf{s}_{0},\ldots,\mathbf{s}_{m-1}$, and
$\mathbf{s}_{m-1}$ cannot be written as linear combination with nonnegative
integer coefficients of $\mathbf{s}_{0},\ldots,\mathbf{s}_{m-2}$.

We end this section with the following result that shows that the only way we
can have $e(S_{n})=1$ is that $n=1$.

######  Proposition 2.5.

If $e(S_{n})=1$, then $n=1$ and $ca-d$ divides $c-d$. Conversely, if $ca-d$
divides $c-d$, then $e(S_{1})=1$.

###### Proof.

If $e(S_{n})=1$, then $\\{\mathbf{s}_{0}\\}$ generates $S_{n}$. In particular,
$\mathbf{s}_{0}\mid\mathbf{s}_{1}$. So $\mathbf{s}_{0}$ divides
$\mathbf{s}_{1}-a\mathbf{s}_{0}=(a-1)d$, and since $\gcd(\mathbf{s}_{0},d)=1$,
we must have $\mathbf{s}_{0}\mid a-1$. Therefore, $\mathbf{s}_{0}\leq a-1$.
Since $d<ac$, we have $ca^{n}-ca<ca^{n}-d\leq a-1$, from which
$ca(a^{n-1}-1)/(a-1)<1$, and the only way this can happen is that $n=1$. Now,
the relation $ca-d=c(a-1)+c-d$ allows to conclude that $ca-d$ divides $c-d$,
since $\mathbf{s}_{0}=ca-d$ divides $a-1$.

Conversely, if $ca-d$ divides $c-d$, then by the relation $ca-d=c(a-1)+c-d$
and the fact that $ca-d$ and $c$ are relatively prime, we can conclude that
$ca-d$ divides $a-1$. Now, $ca^{2}-d=c(a^{2}-1)+c-d$, from which we see that
$\mathbf{s}_{0}=ca-d$ divides $\mathbf{s}_{1}=ca^{2}-d$ and by Theorem 2.3,
$e(S_{1})=1$. ∎

##  3 Repunit numbers and relations between the generators of $S_{n}$

From now on, $\mathbf{R}_{n}$ will represent the $n-$th repunit number in base
$a$, that is,

$\mathbf{R}_{n}=\frac{a^{n}-1}{a-1}=1+a+\cdots+a^{n-1},$

for $n\geq 1$. For convenience we define $\mathbf{R}_{0}=0$. This sequence of
positive integers satisfies the recurrence relation
$\mathbf{R}_{n+1}=a\mathbf{R}_{n}+1$, for all $n\geq 0$. By induction, it
follows that

$\mathbf{R}_{n}=(a-1)\sum_{j=m}^{n-1}\mathbf{R}_{j}+\mathbf{R}_{m}+n-m,$ (3)

whenever $0\leq m<n$. Repunit numbers are of interest in number theory (see
[7, 10]) and they appear naturally in representations of elements of $S_{n}$
in terms of the minimal generators.

Using the recurrence relation that the generators of $S_{n}$ satisfy, that is,
$\mathbf{s}_{j+1}=a\mathbf{s}_{j}+(a-1)d$, for all $j\geq 0$, we can derive a
formula like (3) that holds for the $\mathbf{s}_{j}$’s:

$\mathbf{s}_{t}=(a-1)\sum_{j=u}^{t-1}\mathbf{s}_{j}+\mathbf{s}_{u}+(t-u)(a-1)d,$
(4)

where $0\leq u<t$.

In the following lemma we give the fundamental relations between the
$\mathbf{s}_{j}$’s.

######  Lemma 3.1 (Minimal relations).

If $i$ and $j$ are nonnegative integers and $j>0$, then

$a\mathbf{s}_{i}+\mathbf{s}_{j}=\mathbf{s}_{i+1}+a\mathbf{s}_{j-1}.$

###### Proof.

We have
$a\mathbf{s}_{i}+\mathbf{s}_{j}=a\mathbf{s}_{i}+a\mathbf{s}_{j-1}+(a-1)d=\mathbf{s}_{i+1}+a\mathbf{s}_{j-1}.$
∎

The elements of $S_{n}$ can be represented as linear combinations of the
$\mathbf{s}_{j}$’s with nonnegative coefficients, but it is convenient to
consider linear combinations of the $\mathbf{s}_{j}$’s with integer
coefficients.

######  Proposition 3.2.

For all $j\geq 1$ and integers $\alpha$ and $\beta$, we have

$\alpha\mathbf{s}_{0}+\beta\mathbf{s}_{j}=\left(\alpha-a\beta\mathbf{R}_{j-1}\right)\mathbf{s}_{0}+\left(\beta\mathbf{R}_{j}\right)\mathbf{s}_{1}.$

###### Proof.

By induction on $j$. For $j=1$, the result is obvious. Assume the result is
true for $j\geq 1$ and all integers $\alpha$ and $\beta$. Then, by Lemma 3.1
we have

$\alpha\mathbf{s}_{0}+\beta\mathbf{s}_{j+1}=(\alpha-a\beta)\mathbf{s}_{0}+\beta\mathbf{s}_{1}+a\beta\mathbf{s}_{j}.$

Now, by applying the induction hypothesis to
$(\alpha-a\beta)\mathbf{s}_{0}+a\beta\mathbf{s}_{j}$, we get

$(\alpha-a\beta)\mathbf{s}_{0}+a\beta\mathbf{s}_{j}=\left(\alpha-a\beta-a^{2}\beta\mathbf{R}_{j-1}\right)\mathbf{s}_{0}+\left(a\beta\mathbf{R}_{j}\right)\mathbf{s}_{1}.$

Finally, by using the recurrence relation between the $\mathbf{R}_{j}$’s, we
obtain

$\displaystyle\alpha\mathbf{s}_{0}+\beta\mathbf{s}_{j+1}$
$\displaystyle=\left(\alpha-a\beta-a^{2}\beta\mathbf{R}_{j-1}\right)\mathbf{s}_{0}+\left(\beta+a\beta\mathbf{R}_{j}\right)\mathbf{s}_{1}$
$\displaystyle=\left(\alpha-a\beta\mathbf{R}_{j}\right)\mathbf{s}_{0}+\left(\beta\mathbf{R}_{j+1}\right)\mathbf{s}_{1}.$

This ends the proof. ∎

######  Corollary 3.3.

If $\alpha,\beta_{1},\beta_{2},\ldots,\beta_{r}$ are integers, then

$\alpha\mathbf{s}_{0}+\sum_{j=1}^{r}\beta_{j}\mathbf{s}_{j}=\left(\alpha-a\sum_{j=2}^{r}\beta_{j}\mathbf{R}_{j-1}\right)\mathbf{s}_{0}+\left(\sum_{j=1}^{r}\beta_{j}\mathbf{R}_{j}\right)\mathbf{s}_{1}$
(5)

Thus, any combination of the $\mathbf{s}_{j}$’s can be transformed into a
combination of $\mathbf{s}_{0}$ and $\mathbf{s}_{1}$. The sum of the
coefficients in both combinations is the same.

###### Proof.

Equality (5) follows by applying Proposition 3.2. The sum of coefficients in
the right hand side of (5) is

$\displaystyle\alpha-a\sum_{j=2}^{r}\beta_{j}\mathbf{R}_{j-1}+\sum_{j=1}^{r}\beta_{j}\mathbf{R}_{j}$
$\displaystyle=\alpha+\beta_{1}+\sum_{j=2}^{r}\beta_{j}\left(\mathbf{R}_{j}-a\mathbf{R}_{j-1}\right)$
$\displaystyle=\alpha+\beta_{1}+\sum_{j=2}^{r}\beta_{j}$
$\displaystyle=\alpha+\sum_{j=1}^{r}\beta_{j},$

which is the sum of the coefficients in the left hand side of (5). ∎

##  4 Representations of $\mathbf{s}_{m}$ as combination of $\mathbf{s}_{j}$,
where $0\leq j<m$

In this section we show how to find some $m>0$ such that $\mathbf{s}_{m}$ can
be represented as combination of the $\mathbf{s}_{j}$’s, where $0\leq j<m$. We
start by writing $c=a^{k}\pm\sum_{i=0}^{k-1}r_{i}a^{i}$ and then we take the
square of $\mathbf{s}_{0}$ to derive a representation of $\mathbf{s}_{n+k}$ or
$\mathbf{s}_{n+k+1}$, as we will see below. We distinguish two cases: $a=2$ or
$a\geq 3$.

###  4.1 The case $a=2$

Let $c=2^{k}+r$, where $0\leq r<2^{k}$. In this case,
$\mathbf{s}_{j}=c2^{n+j}-d$, for all $j\geq 0$. Then, we have

$\displaystyle\mathbf{s}_{0}^{2}$ $\displaystyle=(c2^{n}-d)^{2}$
$\displaystyle=\left(2^{k}+r\right)\left(c2^{2n}\right)-2d(c2^{n})+d^{2}$
$\displaystyle=c2^{2n+k}+rc2^{2n}-d(c2^{n+1})+d^{2}$
$\displaystyle=\mathbf{s}_{n+k}+d+r\mathbf{s}_{n}+rd-d(\mathbf{s}_{1}+d)+d^{2}$
$\displaystyle=\mathbf{s}_{n+k}+r\mathbf{s}_{n}-d\mathbf{s}_{1}+d\left(1+r\right).$

Thus,
$\mathbf{s}_{n+k}=\mathbf{s}_{0}^{2}+d\mathbf{s}_{1}-r\mathbf{s}_{n}-d(1+r)$.
If we substitute $d=\mathbf{s}_{1}-2\mathbf{s}_{0}$ and apply Corollary 3.3,
then

$\displaystyle\mathbf{s}_{n+k}$
$\displaystyle=\mathbf{s}_{0}^{2}+d\mathbf{s}_{1}-r\mathbf{s}_{n}-(\mathbf{s}_{1}-2\mathbf{s}_{0})(1+r)$
$\displaystyle=\left(\mathbf{s}_{0}+2(1+r)\right)\mathbf{s}_{0}+\left(d-1-r\right)\mathbf{s}_{1}-r\mathbf{s}_{n}$
$\displaystyle=\left(\mathbf{s}_{0}+2(1+r)+2r\mathbf{R}_{n-1}\right)\mathbf{s}_{0}+\left(d-1-r-r\mathbf{R}_{n}\right)\mathbf{s}_{1}.$

Observe that $2(1+r)+2r\mathbf{R}_{n-1}=2+2^{n}r=2+2^{n}(c-2^{k})$ and
$1+r+r\mathbf{R}_{n}=1+2^{n}r=1+2^{n}(c-2^{k})$. So, we get

$\mathbf{s}_{n+k}=\left(\mathbf{s}_{0}+2+2^{n}(c-2^{k})\right)\mathbf{s}_{0}+\left(d-1-2^{n}(c-2^{k})\right)\mathbf{s}_{1}.$

In this representation, the coefficient of $\mathbf{s}_{0}$ is nonnegative. We
have the following result.

######  Proposition 4.1.

If $k$ is a nonnegative integer such that $2^{k}\leq c$ and $d\geq
1+2^{n}(c-2^{k})$, then

$\mathbf{s}_{n+k}=\left(\mathbf{s}_{0}+2+2^{n}(c-2^{k})\right)\mathbf{s}_{0}+\left(d-1-2^{n}(c-2^{k})\right)\mathbf{s}_{1},$

where the coefficients of $\mathbf{s}_{0}$ and $\mathbf{s}_{1}$ are
nonnegative an their sum is $1+c2^{n}$.

Now, we give some examples of applications of this proposition.

######  Example 4.2.

Consider the generating sequence $x_{n}=2^{n}-1$. Here, we have $c=2^{0}+0$,
and it is obvious that $d=1\geq 1+2^{n}(c-2^{0})$, so that
$\mathbf{s}_{n}=(\mathbf{s}_{0}+2)\mathbf{s}_{0}$.

######  Example 4.3.

Let us fix $k\geq 1$, and consider the generating sequence
$x_{n}=(2^{k}+1)2^{n}-(2^{k}-1)$ (see [8]). Here, $d=2^{k}-1$ and $c=2^{k}+1$,
so $d\geq 1+2^{n}(c-2^{k})$ if and only if $2^{k}-1\geq 1+2^{n}$, which holds
if and only if $k>n$. From Proposition 4.1, we have

$\mathbf{s}_{n+k}=\left(\mathbf{s}_{0}+2+2^{n}\right)\mathbf{s}_{0}+\left(2^{k}-2^{n}-2\right)\mathbf{s}_{1}.$

Now, we return to the general treatment. If
$c=2^{k}-\sum_{i=0}^{k-1}r_{i}2^{i}$, where $r_{i}\in\\{0,1\\}$, for
$i=0,\ldots,k-1$ (we may have $k=0$ and $r_{i}=0$ for all $i$), then, with
similar computations as above, we get the following representation of
$\mathbf{s}_{n+k}$

$\mathbf{s}_{n+k}=\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i}+\left(d+\sum_{i=0}^{k-1}r_{i}-1\right)\mathbf{s}_{1}+\left(\mathbf{s}_{0}-2\sum_{i=0}^{k-1}r_{i}+2\right)\mathbf{s}_{0}.$

In this representation of $\mathbf{s}_{n+k}$, the coefficients of the
$\mathbf{s}_{n+i}$’s are nonnegative, and the coefficient of $\mathbf{s}_{1}$
is clearly nonnegative, because $d>0$. We have the following result.

######  Proposition 4.4.

Let $c=2^{k}-\sum_{i=0}^{k-1}r_{i}2^{i}$, where $r_{i}\in\\{0,1\\}$ for all
$i$. If $\mathbf{s}_{0}\geq 2\left(\sum_{i=0}^{k-1}r_{i}-1\right)$, then

$\mathbf{s}_{n+k}=\left(\mathbf{s}_{0}-2\left(\sum_{i=0}^{k-1}r_{i}-1\right)\right)\mathbf{s}_{0}+\left(d+\sum_{i=0}^{k-1}r_{i}-1\right)\mathbf{s}_{1}+\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i},$

where the coefficients are nonnegative and the sum of them is $1+c2^{n}$.

######  Example 4.5.

Let $k\geq 1$. For the generating sequence $x_{n}=(2^{k}+1)2^{n}-(2^{k}-1)$,
we have $c=2^{k+1}-\sum_{i=0}^{k-1}2^{i}$, so $\sum_{i}r_{i}=k$. Note that
$\mathbf{s}_{0}\geq x_{1}=(2^{k}+1)2-(2^{k}-1)=2^{k}+3>2(k-1)$, for all $k$.
By Proposition 4.4, we obtain the following representation of
$\mathbf{s}_{n+k+1}$:

$\mathbf{s}_{n+k+1}=\left(\mathbf{s}_{0}-2k+2\right)\mathbf{s}_{0}+\left(2^{k}+k-2\right)\mathbf{s}_{1}+\sum_{i=0}^{k-1}\mathbf{s}_{n+i}.$

######  Example 4.6.

For the generating sequence $x_{n}=(2^{k}-1)2^{n}-1$, where $k\geq 2$, we have
$c=2^{k}-1$ and $d=1$. Note that $\mathbf{s}_{0}\geq 2(1-1)=0$. In this
example, the representation of $\mathbf{s}_{n+k}$ we obtain is the following:

$\mathbf{s}_{n+k}=\mathbf{s}_{0}^{2}+\mathbf{s}_{1}+\mathbf{s}_{n}.$

###  4.2 The case $a\geq 3$

We only consider the case in which $c=a^{k}-\sum_{i=0}^{k-1}r_{i}a^{i}$, where
$r_{i}\in\\{0,1,\ldots,a-1\\}$ for all $i$. With similar arguments, as in
subsection 4.1, we can get the following equality:

$\mathbf{s}_{n+k}=\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i}+(\mathbf{s}_{0}+2d)\mathbf{s}_{0}+d\left(d-1+\sum_{i=0}^{k-1}r_{i}\right).$
(6)

To obtain a representation of $\mathbf{s}_{n+k}$ in terms of the
$\mathbf{s}_{j}$’s, $0\leq j<n+k$, we first consider the case in which
$d-1+\sum_{i=0}^{k-1}r_{i}$ is zero. This condition implies that $d=1$ and
$r_{i}=0$ for all $i$, which means that $c=a^{k}$ and
$\mathbf{s}_{0}=a^{n+k}-1$. Therefore, the representation of
$\mathbf{s}_{n+k}$ we obtain is the following:

$\mathbf{s}_{n+k}=(\mathbf{s}_{0}+2)\mathbf{s}_{0}.$ (7)

The sum of coefficients in this representation is
$\mathbf{s}_{0}+2=1+a^{n+k}=1+ca^{n}$. Returning to the general case in (6),
we can obtain a representation of $\mathbf{s}_{n+k+1}$ as follows:

$\displaystyle\mathbf{s}_{n+k+1}$ $\displaystyle=a\mathbf{s}_{n+k}+(a-1)d$
$\displaystyle=\mathbf{s}_{n+k}+(a-1)\mathbf{s}_{n+k}+(a-1)d$
$\displaystyle=\mathbf{s}_{n+k}+(a-1)\left[\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i}+(\mathbf{s}_{0}+2d)\mathbf{s}_{0}+d\left(d-1+\sum_{i=0}^{k-1}r_{i}\right)\right]+(a-1)d$
$\displaystyle=\mathbf{s}_{n+k}+(a-1)\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i}+(a-1)(\mathbf{s}_{0}+2d)\mathbf{s}_{0}+(a-1)d\left(d+\sum_{i=0}^{k-1}r_{i}\right)$
$\displaystyle=\mathbf{s}_{n+k}+(a-1)\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i}+(a-1)(\mathbf{s}_{0}+2d)\mathbf{s}_{0}+(\mathbf{s}_{1}-a\mathbf{s}_{0})\left(d+\sum_{i=0}^{k-1}r_{i}\right)$
$\displaystyle=\mathbf{s}_{n+k}+(a-1)\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i}+\left(d+\sum_{i=0}^{k-1}r_{i}\right)\mathbf{s}_{1}+\left[(a-1)\mathbf{s}_{0}+(a-2)d-a\sum_{i=0}^{k-1}r_{i}\right]\mathbf{s}_{0}.$

The sum of the coefficients in this representation is
$1+(a-1)(\mathbf{s}_{0}+d)=1+(a-1)ca^{n}$. We summary these ideas in the
following result.

######  Proposition 4.7.

Let $c=a^{k}-\sum_{i=0}^{k-1}r_{i}a^{i}$, for some integers $r_{i}$, where
$0\leq r_{i}<a$, for all $i$. Then

$\displaystyle\mathbf{s}_{n+k+1}=\mathbf{s}_{n+k}+(a-1)\sum_{i=0}^{k-1}r_{i}\mathbf{s}_{n+i}$
$\displaystyle+\left(d+\sum_{i=0}^{k-1}r_{i}\right)\mathbf{s}_{1}$
$\displaystyle+\left[(a-1)\mathbf{s}_{0}+(a-2)d-a\sum_{i=0}^{k-1}r_{i}\right]\mathbf{s}_{0}.$

The sum of coefficients in this representation is $1+(a-1)ca^{n}$.

We end this section with the following example.

######  Example 4.8.

Let us fix positive integers $a$ and $k$, with $a\geq 3$, and consider the
generating sequence $x_{n}=(a^{k}-1)a^{n}-1$. Then, $c=a^{k}-1$, $d=1$,
$r_{0}=1$ and the other $r_{i}$’s are zero. By Proposition 4.7, we have

$\mathbf{s}_{n+k+1}=\mathbf{s}_{n+k}+(a-1)\mathbf{s}_{n}+2\mathbf{s}_{1}+\left[(a-1)\mathbf{s}_{0}-2\right]\mathbf{s}_{0}.$

Note that all the coefficients are nonnegative, since $(a-1)\mathbf{s}_{0}\geq
2$.

##  5 Computation of $e(S_{n})$

In this section, we determine conditions on $m$ such that
$\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq j<m-1\\}\rangle$,
assuming $\mathbf{s}_{m}$ can be represented as linear combination of the
$\mathbf{s}_{j}$’s, $0\leq j<m$, and we show how to compute the embedding
dimension of $S_{n}$.

######  Lemma 5.1.

If
$\mathbf{s}_{m}=\alpha_{0}\mathbf{s}_{0}+\alpha_{1}\mathbf{s}_{1}+\cdots+\alpha_{m-1}\mathbf{s}_{m-1}$,
where $m>0$, then

$\sum_{j=0}^{m-1}\alpha_{j}=1+tca^{n}$

for some $t\in\mathbb{Z}$. If the $\alpha_{j}$’s are nonnegative, then $t>0$.

###### Proof.

The equation $\mathbf{s}_{m}=\sum_{j=0}^{m-1}\alpha_{j}\mathbf{s}_{j}$ implies
that

$ca^{n+m}-d=\sum_{j=0}^{m-1}\alpha_{j}ca^{n+j}-d\sum_{j=0}^{m-1}\alpha_{j},$

from which $d\left(\sum_{j=0}^{m-1}\alpha_{j}-1\right)=sca^{n}$, where
$s=\sum_{j=0}^{m-1}\alpha_{j}a^{j}-a^{m}$. Since $d$ is relatively prime to
$a$ and $c$, we have $d$ divides $s$. So,
$\sum_{j=0}^{m-1}\alpha_{j}=1+tca^{n}$, where $t=s/d$. Clearly, if the
$\alpha_{j}$’s are nonnegative, it must be $t>0$. ∎

######  Theorem 5.2.

For all $n\in\mathbb{Z}^{+}$, we have $e(S_{n})\geq n$.

###### Proof.

It suffices to show that $\mathbf{s}_{n-1}\notin\langle\\{\mathbf{s}_{j}:0\leq
j<n-1\\}\rangle$. If we had
$\mathbf{s}_{n-1}=\sum_{j=0}^{n-2}\alpha_{j}\mathbf{s}_{j}$, for some
nonnegative $\alpha_{j}$’s, then by Lemma 5.1, there is some $t>0$ such that
$\sum_{j=0}^{n-2}\alpha_{j}=1+tca^{n}$. Hence,

$\mathbf{s}_{n-1}=\sum_{j=0}^{n-2}\alpha_{j}\mathbf{s}_{j}\geq\left(\sum_{j=0}^{n-2}\alpha_{j}\right)\mathbf{s}_{0}=(1+tca^{n})\mathbf{s}_{0}\geq(1+ca^{n})\mathbf{s}_{0}.$

Now, since $d<ca$, we have $d\leq ca-1\leq a^{n-1}(ca-1)$, from which it
follows that $\mathbf{s}_{0}\geq a^{n-1}$, which is equivalent to
$(1+ca^{n})\mathbf{s}_{0}>\mathbf{s}_{n-1}$. This gives us a contradiction. ∎

Before our next lemma, we prove that
$\gcd(S_{n})=\gcd(\mathbf{s}_{0},\mathbf{s}_{1})=\gcd(\mathbf{s}_{0},a-1)$.
Since $d$ is relatively prime to $a$ and $c$, we have
$\mathbf{s}_{0}=ca^{n}-d$ is relatively prime to $a,c$ and $d$. The relation
$\mathbf{s}_{1}=a\mathbf{s}_{0}+(a-1)d$ implies that
$\gcd(\mathbf{s}_{0},\mathbf{s}_{1})=\gcd(\mathbf{s}_{0},(a-1)d)=\gcd(\mathbf{s}_{0},a-1)$,
where, for the last equality, we use the fact that $\gcd(\mathbf{s}_{0},d)=1$.
Now, using the relation $\mathbf{s}_{j}=a\mathbf{s}_{j-1}+(a-1)d$,
$j=1,2,\ldots,$ we find that every common divisor of $\mathbf{s}_{0}$ and
$a-1$ divides $\mathbf{s}_{j}$ for all $j\geq 0$. Thus,
$\gcd(\mathbf{s}_{0},a-1)$ divides $\gcd(S_{n})$. Clearly, $\gcd(S_{n})$
divides $\gcd(\mathbf{s}_{0},\mathbf{s}_{1})$. This ends the proof of our
claim.

######  Lemma 5.3.

Let $e=\gcd(S_{n})$. Assume that
$\mathbf{s}_{m}=\alpha_{0}\mathbf{s}_{0}+\cdots+\alpha_{m-1}\mathbf{s}_{m-1}$
for some $m>0$, where $\alpha_{j}$ is nonnegative, $j=0,1,\ldots,m-1$. If
$\sum_{j=0}^{m-1}\alpha_{j}=1+(a-1)ca^{n}$, then for any representation
$\mathbf{s}_{m}=\beta_{0}\mathbf{s}_{0}+\cdots+\beta_{m-1}\mathbf{s}_{m-1}$
with nonnegative $\beta_{j}$’s, there is a nonnegative $u$ such that

$\sum_{j=0}^{m-1}\beta_{j}=1+\left(\frac{u}{e}+1\right)(a-1)ca^{n}.$

###### Proof.

If
$\mathbf{s}_{m}=\beta_{0}\mathbf{s}_{0}+\cdots+\beta_{m-1}\mathbf{s}_{m-1}$,
where the $\beta_{j}$’s are nonnegative, then by Corollary 3.3, we can write
$\mathbf{s}_{m}=A\mathbf{s}_{0}+B\mathbf{s}_{1}$ for some integers $A,B$, and

$A+B=\sum_{j=0}^{m-1}\beta_{j}.$

By Lemma 5.1, there is an integer $t>0$ such that
$\sum_{j=0}^{m-1}\beta_{j}=1+tca^{n}$. So, $A+B=1+tca^{n}$. Again, by
Corollary 3.3, from the representation
$\mathbf{s}_{m}=\alpha_{0}\mathbf{s}_{0}+\cdots+\alpha_{m-1}\mathbf{s}_{m-1}$,
we can derive a representation
$\mathbf{s}_{m}=A_{0}\mathbf{s}_{0}+B_{0}\mathbf{s}_{1}$ such that
$A_{0}+B_{0}=1+(a-1)ca^{n}.$ Therefore, we have
$A\mathbf{s}_{0}+B\mathbf{s}_{1}=\mathbf{s}_{m}=A_{0}\mathbf{s}_{0}+B_{0}\mathbf{s}_{1}$,
so there is an integer $u$ such that $A-A_{0}=u\mathbf{s}_{1}/e$ and
$B-B_{0}=-u\mathbf{s}_{0}/e$ (here we use that
$\gcd(S_{n})=\gcd(\mathbf{s}_{0},\mathbf{s}_{1})$). Hence,

$(A+B)-(A_{0}+B_{0})=u(\mathbf{s}_{1}/e-\mathbf{s}_{0}/e)=uc[(a-1)/e]a^{n}.$

Then,

$A+B=uc[(a-1)/e]a^{n}+(A_{0}+B_{0})=1+(u/e+1)(a-1)ca^{n}.$

This implies that $t=(u/e+1)(a-1)$. Since $t\geq 1$, it must be $u\geq 0$.
This ends the proof. ∎

######  Proposition 5.4.

Let $e=\gcd(S_{n})$. Assume that
$\mathbf{s}_{m}=\alpha_{0}\mathbf{s}_{0}+\cdots+\alpha_{m-1}\mathbf{s}_{m-1}$
for some $m>0$, where $\alpha_{j}\geq 0$, $j=0,1,\ldots,m-1$, and
$\sum_{j=0}^{m-1}\alpha_{j}=1+tca^{n}$ for some $t>0$.

  1. 1.

If $t=1$ and $\mathbf{s}_{0}\geq a^{m-1}$, then $e(S_{n})=m$.

  2. 2.

If $t=a-1$ and $[(a-1)/e]\mathbf{s}_{0}\geq a^{m-1}$, then $e(S_{n})=m$.

###### Proof.

We prove only part 2; part 1 is similar. We want to prove that
$\mathbf{s}_{m-1}\notin\langle\\{\mathbf{s}_{j}:0\leq j<m-2\\}\rangle$. Assume
on the contrary that there is a representation
$\mathbf{s}_{m-1}=\sum_{j=0}^{m-2}b_{j}\mathbf{s}_{j}$, where the $b_{j}$’s
are nonnegative, and $b_{j_{0}}>0$ for some $j_{0}\in\\{0,\ldots,m-2\\}$.
Hence,

$\displaystyle\mathbf{s}_{m}$ $\displaystyle=a\mathbf{s}_{m-1}+(a-1)d$
$\displaystyle=\sum_{j=0}^{m-2}(ab_{j})\mathbf{s}_{j}+(a-1)d$
$\displaystyle=\sum_{j=0,j\neq
j_{0}}^{m-2}(ab_{j})\mathbf{s}_{j}+ab_{j_{0}}\mathbf{s}_{j_{0}}+(a-1)d$
$\displaystyle=\sum_{j=0,j\neq
j_{0}}^{m-2}(ab_{j})\mathbf{s}_{j}+a(b_{j_{0}}-1)\mathbf{s}_{j_{0}}+\mathbf{s}_{j_{0}+1}.$

The sum of coefficients in this representation of $\mathbf{s}_{m}$ is

$\sum_{j=0,j\neq
j_{0}}^{m-2}(ab_{j})+a(b_{j_{0}}-1)+1=a\sum_{j=0}^{m-2}b_{j}-a+1.$

By Lemma 5.3, there exists $u_{0}\geq 0$ such that
$a\sum_{j=0}^{m-2}b_{j}-a+1=1+(u_{0}/e+1)(a-1)ca^{n}$. Then,
$\sum_{j=0}^{m-2}b_{j}=1+(u_{0}/e+1)(a-1)ca^{n-1}$. On the other hand, by
Lemma 5.1, we have $\sum_{j=0}^{m-2}b_{j}=1+t_{1}ca^{n}$ for some $t_{1}>0$,
so that $1+(u_{0}/e+1)(a-1)ca^{n-1}=1+t_{1}ca^{n}$. It follows that
$(u_{0}+e)[(a-1)/e]=t_{1}a$; but, since $a$ and $(a-1)/e$ are relatively
prime, $a$ must divide $u_{0}+e$. Then, $u_{0}+e\geq a$ and
$\sum_{j=0}^{m-2}b_{j}=1+(u_{0}/e+1)(a-1)ca^{n-1}\geq 1+[(a-1)/e]ca^{n}$.
Therefore,

$\mathbf{s}_{m-1}=\sum_{j=0}^{m-2}b_{j}\mathbf{s}_{j}\geq\left(\sum_{j=0}^{m-2}b_{j}\right)\mathbf{s}_{0}=(1+[(a-1)/e]ca^{n})\mathbf{s}_{0}.$

Now, since the hypothesis that $[(a-1)/e]\mathbf{s}_{0}\geq a^{m-1}$ is
equivalent to $\mathbf{s}_{m-1}<(1+[(a-1)/e]ca^{n})\mathbf{s}_{0}$, we have a
contradiction. This ends the proof. ∎

The following result gives the embedding dimension of $S_{n}$ for generating
sequences of the form $x_{n}=c2^{n}-d$, where $d>0$. In this case, $S_{n}$ is
a numerical semigroup, since $\gcd(S_{n})=\gcd(\mathbf{s}_{0},1)=1$.

######  Theorem 5.5.

Consider a generating sequence of the form $x_{n}=c2^{n}-d$. If $d\leq 2^{n}$
and $k$ is the smallest nonnegative integer such that $c\leq 2^{k}$, then
$e(S_{n})=n+k$.

###### Proof.

Since $c\leq 2^{k}$, we can write $c=2^{k}-\sum_{i=0}^{k-1}r_{i}2^{i}$, where
$r_{i}\in\\{0,1\\}$, for all $i\in\\{0,\ldots,k-1\\}$. Here, $r_{k-1}=0$, for
if $r_{k-1}=1$, then $c=2^{k-1}-\sum_{i=0}^{k-2}r_{i}2^{i}$ and this
contradicts the minimality of $k$. Thus,

$c=2^{k}-\sum_{i=0}^{k-2}r_{i}2^{i}\geq 2^{k}-(2^{k-1}-1)=2^{k-1}+1.$

So, $\mathbf{s}_{0}=c2^{n}-d\geq 2^{n+k-1}+2^{n}-d\geq 2^{n+k-1}$. On the
other hand, note that $2(\sum_{i=0}^{k-2}r_{i}-1)\leq 2(k-2)$ and it is easy
to see that $2^{n+k-1}\geq 2(k-2)$. Therefore, $\mathbf{s}_{0}\geq
2(\sum_{i=0}^{k-2}r_{i}-1)$. By Proposition 4.4, we have

$\mathbf{s}_{n+k}=\left(\mathbf{s}_{0}-2\left(\sum_{i=0}^{k-2}r_{i}-1\right)\right)\mathbf{s}_{0}+\left(d+\sum_{i=0}^{k-2}r_{i}-1\right)\mathbf{s}_{1}+\sum_{i=0}^{k-2}r_{i}\mathbf{s}_{n+i}.$

The sum of coefficients in this representation is $1+c2^{n}$. Since
$\mathbf{s}_{0}\geq 2^{n+k-1}$, by Proposition 5.4, we have $e(S_{n})=n+k$. ∎

######  Corollary 5.6.

Consider a generating sequence of the form $x_{n}=c2^{n}-1$. If $k$ is the
smallest nonnegative integer such that $c\leq 2^{k}$, then $e(S_{n})=n+k$.

Now, in the following examples, we apply Proposition 5.4, Theorem 5.5 and
Corollary 5.6 to compute the embedding dimension of the semigroups $S_{n}$
associated with some families of generating sequences.

######  Example 5.7.

  1. 1.

For the sequence of Mersenne numbers $x_{n}=2^{n}-1$, the value of $k$ in
Corollary 5.6 is $k=0$, so $e(S_{n})=n$ (see [3]).

  2. 2.

Fix $k\geq 2$ and consider the generating sequence $x_{n}=(2^{k}-1)2^{n}-1$.
By Corollary 5.6, we have $e(S_{n})=n+k$ (see [2]).

  3. 3.

For $k\geq 1$, we consider the generating sequence
$x_{n}=(2^{k}+1)2^{n}-(2^{k}-1)$. In this case, the smallest power of $2$
greater than or equal to $c=2^{k}+1$ is $2^{k+1}$, and $d=2^{k}-1$. So, we
have $d\leq 2^{n}$ if and only if $k\leq n$. Thus, by Theorem 5.5, if $k\leq
n$, then $e(S_{n})=n+k+1$ (see [8]).

  4. 4.

Let $k\geq 1$ and $x_{n}=(2^{k}+1)2^{n}-(2^{k}-1)$, with $k>n$. Here, we have
$c=2^{k}+1$. By Example 4.3, there is a representation of $\mathbf{s}_{n+k}$,
where the sum of coefficients is $1+(2^{k}+1)2^{n}$. It is easy to see that
$\mathbf{s}_{0}\geq 2^{n+k-1}$; therefore, by Proposition 5.4, $e(S_{n})=n+k$
(see [8]).

  5. 5.

We consider $a\geq 3$, $k\geq 0$, and $x_{n}=a^{k+n}-1$. By (7), there is a
representation of $\mathbf{s}_{n+k}$, where the sum of coefficients is
$1+ca^{n}$. Clearly $\mathbf{s}_{0}\geq a^{n+k-1}$, so, by the first part of
Proposition 5.4, we obtain $e(S_{n})=n+k$.

  6. 6.

Let $a\geq 3$, $k\geq 1$, and consider the sequence $x_{n}=(a^{k}-1)a^{n}-1$.
By Proposition 4.7, there is a representation of $\mathbf{s}_{n+k+1}$, whose
sum of coefficients is $1+(a-1)ca^{n}$. It is easy to see that
$(a-1)\mathbf{s}_{0}\geq a^{n+k}$, so, by the second part of Proposition 5.4,
we have $e(S_{n})=n+k+1$.

######  Remark 5.8.

Note that Lemmas 5.1, 5.3, Theorem 5.2 and Proposition 5.4 hold for generating
sequences of the form $x_{n}=ca^{n}+d$, where $d>0$. Until now, we have not
needed $S_{n}$ to be a numerical semigroup.

##  6 Residual tuples and the Apéry set ${\rm Ap}(S_{n},\mathbf{s}_{0})$

In this section we describe a nice way of finding the maximum element of ${\rm
Ap}(S_{n},\mathbf{s}_{0})$, and we show a characterization of the elements of
${\rm Ap}(S_{n},\mathbf{s}_{0})$. Throughout this section, we assume the
embedding dimension of $S_{n}$ is greater than one. We start with the
following proposition, which is just a plain generalization of the
corresponding result in [1, 2, 3, 4, 5, 8, 9]. Recall that $A(m-1)$ stands for
the set of residual $(m-1)-$tuples.

######  Proposition 6.1.

Let $n$ be a positive integer and $m=e(S_{n})$. If $x\in{\rm
Ap}(S_{n},\mathbf{s}_{0})$, then there exists
$(\alpha_{1},\ldots,\alpha_{m-1})\in A(m-1)$ such that
$x=\alpha_{1}\mathbf{s}_{1}+\cdots+\alpha_{m-1}\mathbf{s}_{m-1}$.

###### Proof.

We proceed by induction on $x$. For $x=0$ we have the residual $(m-1)-$tuple
$(0,\ldots,0)$ such that $x=0\mathbf{s}_{1}+\cdots+0\mathbf{s}_{m-1}$. Suppose
that $x>0$ and let $j=\min\\{i\in\\{0,\ldots,m-1\\}:x-\mathbf{s}_{i}\in
S_{n}\\}$. Observe that $j\neq 0$ since $x\in{\rm Ap}(S_{n},\mathbf{s}_{0})$.
By induction, there exists $(\alpha_{1},\ldots,\alpha_{m-1})\in A(m-1)$ such
that
$x-\mathbf{s}_{j}=\alpha_{1}\mathbf{s}_{1}+\cdots+\alpha_{m-1}\mathbf{s}_{m-1}$.
Hence,
$x=\alpha_{1}\mathbf{s}_{1}+\cdots+(\alpha_{j}+1)\mathbf{s}_{j}+\cdots+\alpha_{m-1}\mathbf{s}_{m-1}$.
To conclude the proof, we only need to show that
$(\alpha_{1},\ldots,\alpha_{j}+1,\ldots,\alpha_{m-1})\in A(m-1)$. If
$\alpha_{j}+1=a+1$, then we get
$(\alpha_{j}+1)\mathbf{s}_{j}=(a+1)\mathbf{s}_{j}=\mathbf{s}_{j}+a\mathbf{s}_{j}=a\mathbf{s}_{j-1}+\mathbf{s}_{j+1}$.
Since $\mathbf{s}_{j+1}\in S_{n}$, we see that $x-\mathbf{s}_{j-1}\in S_{n}$,
contradicting the minimality of $j$. If there exists $k>j$ such that
$\alpha_{k}=a$, then we obtain that
$\mathbf{s}_{j}+a\mathbf{s}_{k}=a\mathbf{s}_{j-1}+\mathbf{s}_{k+1}$, so
$x-\mathbf{s}_{j-1}\in S_{n}$, which contradicts the minimality of $j$. Now,
by the minimality of $j$ we have $\alpha_{1}=\cdots=\alpha_{j-1}=0$, and
consequently, $(\alpha_{1},\ldots\alpha_{j}+1,\ldots,\alpha_{m-1})\in A(m-1)$.
∎

######  Lemma 6.2.

Let $t$ be a positive integer. Then
$\mathbf{s}_{t+1}>\sum_{j=1}^{t}\alpha_{j}\mathbf{s}_{j}$ for all residual
$t-$tuples $(\alpha_{1},\ldots,\alpha_{t})$.

###### Proof.

Let $(\alpha_{1},\ldots,\alpha_{t})$ be a residual $t-$tuple. If
$\alpha_{j_{0}}=a$ for some $j_{0}\in\\{1,\ldots,t\\}$, then

$\displaystyle\sum_{j=1}^{t}\alpha_{j}\mathbf{s}_{j}$
$\displaystyle\leq\mathbf{s}_{j_{0}}+(a-1)\sum_{j=j_{0}}^{t}\mathbf{s}_{j}$
$\displaystyle\leq\mathbf{s}_{j_{0}}+(a-1)\left(c\sum_{j=j_{0}}^{t}a^{n+j}-(t+1-j_{0})d\right)$
$\displaystyle=\mathbf{s}_{j_{0}}+(a-1)\left(ca^{n+j_{0}}\mathbf{R}_{t+1-j_{0}}-(t+1-j_{0})d\right)$
$\displaystyle=ca^{n+j_{0}}-d+ca^{n+j_{0}}\left(a^{t+1-j_{0}}-1\right)-(a-1)(t+1-j_{0})d$
$\displaystyle=ca^{n+t+1}-d-(a-1)(t+1-j_{0})d$
$\displaystyle=\mathbf{s}_{t+1}-(a-1)(t+1-j_{0})d$
$\displaystyle<\mathbf{s}_{t+1}$

In a similar way it can be shown that if $\alpha_{j}<a$ for all $j$, then
$\sum_{j=1}^{t}\alpha_{j}\mathbf{s}_{j}<\mathbf{s}_{t+1}$. ∎

Now, recall the colexicographic order $\leq_{c}$ on the set of residual
$r-$tuples $A(r)$:
$(\alpha_{1},\ldots,\alpha_{r})\leq_{c}(\beta_{1},\ldots,\beta_{r})$ if and
only if $(\alpha_{1},\ldots,\alpha_{r})=(\beta_{1},\ldots,\beta_{r})$ or there
exists $t\in\\{1,\ldots,t\\}$ such that $\alpha_{t}<\beta_{t}$ and
$\alpha_{i}=\beta_{i}$ for all $i>t$.

######  Proposition 6.3.

If $(\alpha_{1},\ldots,\alpha_{r})$ and $(\beta_{1},\ldots,\beta_{r})$ are
residual $r-$ tuples, then
$(\alpha_{1},\ldots,\alpha_{r})<_{c}(\beta_{1},\ldots,\beta_{r})$ if and only
if
$\sum_{j=1}^{r}\alpha_{j}\mathbf{s}_{j}<\sum_{j=1}^{r}\beta_{j}\mathbf{s}_{j}$.

###### Proof.

If $(\alpha_{1},\ldots,\alpha_{r})<_{c}(\beta_{1},\ldots,\beta_{r})$, then
there is some $t\in\\{1,\ldots,r\\}$ such that $\alpha_{t}<\beta_{t}$ and
$\alpha_{i}=\beta_{i}$ for $i=t+1,\ldots,r$. Thus,

$\displaystyle\sum_{j=1}^{r}\alpha_{j}\mathbf{s}_{j}$
$\displaystyle=\sum_{j=1}^{t-1}\alpha_{j}\mathbf{s}_{j}+\alpha_{t}\mathbf{s}_{t}+\sum_{j=t+1}^{r}\alpha_{j}\mathbf{s}_{j}$
$\displaystyle<\mathbf{s}_{t}+\alpha_{t}\mathbf{s}_{t}+\sum_{j=t+1}^{r}\alpha_{j}\mathbf{s}_{j}$
$\displaystyle\leq\beta_{t}\mathbf{s}_{t}+\sum_{j=t+1}^{r}\beta_{j}\mathbf{s}_{j}$
$\displaystyle\leq\sum_{j=1}^{r}\beta_{j}\mathbf{s}_{j}$

In the second line above we applied Lemma 6.2. For the converse, suppose that
$\sum_{j=1}^{r}\alpha_{j}\mathbf{s}_{j}<\sum_{j=1}^{r}\beta_{j}\mathbf{s}_{j}$.
Clearly, it cannot be
$(\alpha_{1},\ldots,\alpha_{r})=(\beta_{1},\ldots,\beta_{r})$. Now, if
$(\alpha_{1},\ldots,\alpha_{r})>(\beta_{1},\ldots,\beta_{r})$, then it follows
that
$\sum_{j=1}^{r}\alpha_{j}\mathbf{s}_{j}>\sum_{j=1}^{r}\beta_{j}\mathbf{s}_{j}$,
which is a contradiction. ∎

######  Corollary 6.4.

For all $r\geq 1$,

$\left\\{\sum_{j=1}^{r}\alpha_{j}\mathbf{R}_{j}:(\alpha_{1},\ldots,\alpha_{r})\in
A(r)\right\\}=\\{0,1,\ldots,\mathbf{R}_{r+1}-1\\}.$

###### Proof.

The minimum and maximum residual $r-$tuples with respect to the co-
lexicographic order are $(0,\ldots,0)$ and $(0,\ldots,0,a)$, respectively;
these $r-$ tuples correspond to the integers $0$ and
$a\mathbf{R}_{r}=\mathbf{R}_{r+1}-1$. So,

$\left\\{\sum_{j=1}^{r}\alpha_{j}\mathbf{R}_{j}:(\alpha_{1},\ldots,\alpha_{r})\in
A(r)\right\\}\subseteq\\{0,\ldots,\mathbf{R}_{r+1}-1\\}.$

Since both sets have $\mathbf{R}_{r+1}$ elements, they are equal. ∎

######  Corollary 6.5.

Let $r\geq 1$. For each integer $t$ such that $0\leq t<\mathbf{R}_{r+1}$,
there exists a unique residual $r-$tuple $(\alpha_{1},\ldots,\alpha_{r})$ such
that $t=\sum_{j=1}^{r}\alpha_{j}\mathbf{R}_{j}$.

######  Lemma 6.6.

Let $(\alpha_{1},\ldots,\alpha_{r})$ be a residual $r-$tuple. Then, the number
of residual $r-$tuples less than or equal to $(\alpha_{1},\ldots,\alpha_{r})$
with respect to the colexicographic order is

$1+\sum_{j=1}^{r}\alpha_{j}\mathbf{R}_{j}.$

###### Proof.

Let $B_{r}$ be the set of $r-$tuples less than or equal to
$(\alpha_{1},\ldots,\alpha_{r})$ with respect to the co-lexicographic order.
If $r=1$, then $|B_{1}|=1+\alpha_{1}=1+\alpha_{1}\mathbf{R}_{1}$. Assume the
result is true for $r\geq 1$. Let $(\alpha_{1},\ldots,\alpha_{r+1})$ be a
residual $(r+1)-$tuple. The set $B_{r+1}$ is the disjoint union of subsets
$C_{1}$ and $C_{2}$, where $C_{1}$ is the set of all residual $(r+1)-$tuples
$(\beta_{1},\ldots,\beta_{r+1})$ such that $\beta_{r+1}<\alpha_{r+1}$ and
$C_{2}$ is the set of all residual $(r+1)-$tuples
$(\beta_{1},\ldots,\beta_{r+1})$ such that $\beta_{r+1}=\alpha_{r+1}$. Each
element in $C_{1}$ can be represented uniquely in the form
$(\beta_{1},\ldots,\beta_{r+1})$, where $0\leq\beta_{r+1}<\alpha_{r+1}$ and
$(\beta_{1},\ldots,\beta_{r})$ is a residual $r-$tuple, so the set $C_{1}$ has
$\alpha_{r+1}\mathbf{R}_{r+1}$ elements.

Let us count the number of elements in $C_{2}$. If $\alpha_{r+1}=a$, then
$C_{2}$ only contains the $(r+1)-$tuple, $(0,\ldots,0,a)$. In this case, the
set $B_{r}$ only contains the $r-$tuple, $(0,\ldots,0)$. Now, if
$\alpha_{r+1}<a$, then the elements in $C_{2}$ are representable uniquely in
the form $(\beta_{1},\ldots,\beta_{r},\alpha_{r+1})$, where
$(\beta_{1},\ldots,\beta_{r})\in B_{r}$. In any case, $C_{2}$ has the same
number of elements as $B_{r}$. This number is
$1+\sum_{j=1}^{r}\alpha_{j}\mathbf{R}_{j}$, by the induction hypothesis. Thus,
$B_{r+1}$ has $1+\sum_{j=1}^{r+1}\alpha_{j}\mathbf{R}_{j}$ elements. ∎

The proof of Lemma 6.6 gives us also a good recursive description of the set
of residual $r-$tuples less than or equal to $(\alpha_{1},\ldots,\alpha_{r})$
with respect to the colexicographic order. In fact, those are precisely
residual $r-$tuples of the form $(\beta_{1},\ldots,\beta_{r-1},\beta)$, where
$0\leq\beta<\alpha_{r}$ and $(\beta_{1},\ldots,\beta_{r-1})$ is a residual
$(r-1)-$tuple (for each $\beta\in\\{0,\ldots,\alpha_{r}-1\\}$, there are
exactly $\mathbf{R}_{r}$ such tuples), along with residual $r-$tuples of the
form $(\beta_{1},\ldots,\beta_{r-1},\alpha_{r})$, where
$(\beta_{1},\ldots,\beta_{r-1})\leq_{c}(\alpha_{1},\ldots,\alpha_{r-1})$.

Now, we give a complete description of the Apéry set ${\rm
Ap}(S_{n},\mathbf{s}_{0})$ in terms of residual $r-$tuples. Let $m=e(S_{n})$.
By Proposition 6.1, we have $\mathbf{s}_{0}=|{\rm
Ap}(S_{n},\mathbf{s}_{0})|\leq\mathbf{R}_{m}$. So, if $e=\gcd(S_{n})$, then
$\mathbf{s}_{0}/e\leq\mathbf{R}_{m}$. Thus,
$0\leq\mathbf{s}_{0}/e-1<\mathbf{R}_{m}$ and, by Corollary 6.5, there is a
unique residual $(m-1)-$tuple $(\alpha_{1},\ldots,\alpha_{m-1})$ such that
$\mathbf{s}_{0}/e=1+\sum_{j=1}^{m-1}\alpha_{j}\mathbf{R}_{j}$.

######  Proposition 6.7.

Let $m=e(S_{n})$, $e=\gcd(S_{n})$ and $(\alpha_{1},\ldots,\alpha_{m-1})$ be
the unique $(m-1)-$tuple such that
$\mathbf{s}_{0}/e=1+\sum_{j=1}^{m-1}\alpha_{j}\mathbf{R}_{j}$. Then, ${\rm
Ap}(S_{n},\mathbf{s}_{0})$ coincides with the following set

$\left\\{\sum_{j=1}^{m-1}\beta_{j}\mathbf{s}_{j}:(\beta_{1},\ldots,\beta_{m-1})\in
A(m-1),(\beta_{1},\ldots,\beta_{m-1})\leq_{c}(\alpha_{1},\ldots,\alpha_{m-1})\right\\}.$
(8)

###### Proof.

Let us denote by $T(m)$ the set in (8). The size of $T(m)$ is precisely
$1+\sum_{j=1}^{m-1}\alpha_{j}\mathbf{R}_{j}=\mathbf{s}_{0}/e$. For any
$(m-1)-$tuple $(\beta_{1},\ldots,\beta_{m-1})$, where
$\beta_{1},\ldots,\beta_{m-1}$ are integers, we have

$\sum_{j=1}^{m-1}\beta_{j}\mathbf{s}_{j}\equiv(a-1)d\sum_{j=1}^{m-1}\beta_{j}\mathbf{R}_{j}\
({\rm mod}\ \mathbf{s}_{0}).$

Note that $e=\gcd(S_{n})=\gcd(\mathbf{s}_{0},a-1)$. Then,

$\sum_{j=1}^{m-1}\beta_{j}\left(\mathbf{s}_{j}/e\right)\equiv((a-1)/e)d\sum_{j=1}^{m-1}\beta_{j}\mathbf{R}_{j}\
({\rm mod}\ \mathbf{s}_{0}/e).$

Recall that $(1/e)S_{n}$ is a numerical semigroup and its Apéry set in
$\mathbf{s}_{0}/e$ is given by ${\rm
Ap}((1/e)S_{n},(1/e)\mathbf{s}_{0})=(1/e){\rm Ap}(S_{n},\mathbf{s}_{0})$.

Now, when $(\beta_{1},\ldots,\beta_{m-1})$ runs over the set of residual
$(m-1)-$tuples that are less than or equal to
$(\alpha_{1},\ldots,\alpha_{m-1})$ with respect to the colexicographic order,
we obtain $\mathbf{s}_{0}/e$ integers of the form
$\sum_{j=1}^{m-1}\beta_{j}(\mathbf{s}_{j}/e)$ that are mutually incongruent
modulo $\mathbf{s}_{0}/e$. In fact, if $(\beta_{1},\ldots,\beta_{m-1})$ and
$(\gamma_{1},\ldots,\gamma_{m-1})$ are less than or equal to
$(\alpha_{1},\ldots,\alpha_{m-1})$ and
$\sum_{j=1}^{m-1}\beta_{j}(\mathbf{s}_{j}/e)\equiv\sum_{j=1}^{m-1}\gamma_{j}(\mathbf{s}_{j}/e)\
({\rm mod}\ \mathbf{s}_{0}/e)$, then

$((a-1)/e)d\sum_{j=1}^{m-1}\beta_{j}\mathbf{R}_{j}\equiv((a-1)/e)d\sum_{j=1}^{m-1}\gamma_{j}\mathbf{R}_{j}\
({\rm mod}\ \mathbf{s}_{0}/e).$

Since $\mathbf{s}_{0}/e$ is relatively prime to $(a-1)/e$ and $d$, we obtain

$\sum_{j=1}^{m-1}\beta_{j}\mathbf{R}_{j}\equiv\sum_{j=1}^{m-1}\gamma_{j}\mathbf{R}_{j}\
({\rm mod}\ \mathbf{s}_{0}/e).$

Now, both $\sum_{j=1}^{m-1}\beta_{j}\mathbf{R}_{j}$ and
$\sum_{j=1}^{m-1}\gamma_{j}\mathbf{R}_{j}$ are less than or equal to
$\sum_{j=1}^{m-1}\alpha_{j}\mathbf{R}_{j}=\mathbf{s}_{0}/e-1$, so
$\sum_{j=1}^{m-1}\beta_{j}\mathbf{R}_{j}=\sum_{j=1}^{m-1}\gamma_{j}\mathbf{R}_{j}$.
Therefore, $(\beta_{1},\ldots,\beta_{m-1})=(\gamma_{1},\ldots,\gamma_{m-1})$.
We show now that $(1/e){\rm Ap}(S_{n},\mathbf{s}_{0})\subseteq(1/e)T(m)$. Let
$s\in(1/e){\rm Ap}(S_{n},\mathbf{s}_{0})$. Then, by Proposition 6.1, there is
a residual $(m-1)-$tuple $(\gamma_{1},\ldots,\gamma_{m-1})$ such that
$s=\sum_{j=1}^{m-1}\gamma_{j}(\mathbf{s}_{j}/e)$. We want to show that
$(\gamma_{1},\ldots,\gamma_{m-1})\leq_{c}(\alpha_{1},\ldots,\alpha_{m-1})$.
Suppose, on the contrary, that
$(\gamma_{1},\ldots,\gamma_{m-1})>_{c}(\alpha_{1},\ldots,\alpha_{m-1})$. There
exists an $(m-1)-$tuple $(\beta_{1},\ldots,\beta_{m-1})$ less than or equal to
$(\alpha_{1},\ldots,\alpha_{m-1})$ such that

$s\equiv\sum_{j=1}^{m-1}\beta_{j}(\mathbf{s}_{j}/e)\ ({\rm mod}\
\mathbf{s}_{0}/e).$

We also have
$s=\sum_{j=1}^{m-1}\gamma_{j}(\mathbf{s}_{j}/e)>\sum_{j=1}^{m-1}\beta_{j}(\mathbf{s}_{j}/e)$,
which contradicts that $s\in{\rm Ap}((1/e)S_{n},\mathbf{s}_{0}/e)$, for $s$
cannot be congruent to an element of $(1/e)S_{n}$ less than $s$. This
contradiction shows that $(1/e){\rm
Ap}(S_{n},\mathbf{s}_{0})\subseteq(1/e)T(m)$. Since both sets have
$\mathbf{s}_{0}/e$ elements, it results that $(1/e){\rm
Ap}(S_{n},\mathbf{s}_{0})=(1/e)T(m)$ and ${\rm
Ap}(S_{n},\mathbf{s}_{0})=T(m)$. ∎

Proposition 6.7 tells us that if we can find explicitly the residual
$(m-1)-$tuple $(\alpha_{1},\ldots,\alpha_{m-1})$ such that
$\mathbf{s}_{0}/e=1+\sum_{j=1}^{m-1}\alpha_{j}\mathbf{R}_{j}$, then we have an
explicit description of ${\rm Ap}(S_{n},\mathbf{s}_{0})$. In particular, we
have the following result.

######  Corollary 6.8.

If $m=e(S_{n})$, $e=\gcd(S_{n})$ and $(\alpha_{1},\ldots,\alpha_{m-1})$ is the
unique residual $(m-1)-$tuple such that
$\mathbf{s}_{0}/e=1+\sum_{j=1}^{m-1}\alpha_{j}\mathbf{R}_{j}$, then

$\max{\rm Ap}(S_{n},\mathbf{s}_{0})=\sum_{j=1}^{m-1}\alpha_{j}\mathbf{s}_{j}.$

Moreover, for the numerical semigroup $(1/e)S_{n}$, we have

${\rm
F}((1/e)S_{n})=\sum_{j=1}^{m-1}\alpha_{j}(\mathbf{s}_{j}/e)-\mathbf{s}_{0}/e.$

######  Example 6.9.

Consider the generating sequence $x_{n}=a^{k+n}-1$, where $a\geq 2$ and $k\geq
0$. We know that $e(S_{n})=n+k$. Now, $\gcd(S_{n})=a-1$ and we note that
$\mathbf{s}_{0}/(a-1)=1+a\mathbf{R}_{n+k-1}$ (this is valid if $n+k>1$). Thus,
${\rm Ap}(S_{n},\mathbf{s}_{0})$ is the set of all combinations
$\sum_{j=1}^{n+k-1}\beta_{j}\mathbf{s}_{j}$, where
$(\beta_{1},\ldots,\beta_{n+k-1})$ is a residual $(n+k-1)-$tuple less than or
equal to $(0,\ldots,0,a)$ in the co-lexicographic order. From Corollary 6.8 we
have

$\displaystyle{\rm F}((1/(a-1))S_{n})$
$\displaystyle=a\frac{\mathbf{s}_{n+k-1}}{a-1}-\frac{\mathbf{s}_{0}}{a-1}$
$\displaystyle=\frac{a^{2n+k}-a}{a-1}-\frac{a^{n}-1}{a-1}$
$\displaystyle=a^{n}\mathbf{R}_{n+k}-1.$

In the computation of the genus of $S_{n}$, it is important to compute sums of
the form

$\sum_{(\alpha_{1},\ldots,\alpha_{r})}\sum_{j=1}^{r}\alpha_{j}\mathbf{s}_{j},$

where the sum is taken over all residual $r-$tuples
$(\alpha_{1},\ldots,\alpha_{r})$. The following result gives us a nice formula
for this kind of sums.

######  Proposition 6.10.

For all $r\geq 1$, we have

$\sum_{(\alpha_{1},\ldots,\alpha_{r})}\sum_{j=1}^{r}\alpha_{j}\mathbf{s}_{j}=\frac{1}{2}\left(a\mathbf{R}_{r}\mathbf{s}_{r+1}+ra^{r+1}\mathbf{s}_{0}\right)$

###### Proof.

First, we have

$\sum_{(\alpha_{1},\ldots,\alpha_{r})}\sum_{j=1}^{r}\alpha_{j}\mathbf{s}_{j}=\frac{1}{2}\sum_{j=1}^{r}\left(a^{r+1}+a^{r+1-j}\right)\mathbf{s}_{j}.$

This formula follows exactly as in the proof of Theorem 25 in [4] where,
although that proof is for the generating sequence of repunit numbers
$\mathbf{R}_{n}=(a^{n}-1)/(a-1)$, it works for a general generating sequence.
Now,

$\displaystyle\sum_{j=1}^{r}\left(a^{r+1}+a^{r+1-j}\right)\mathbf{s}_{j}$
$\displaystyle=a^{r+1}\sum_{j=1}^{r}(ca^{n+j}-d)+\sum_{j=1}^{r}a^{r+1-j}(ca^{n+j}-d)$
$\displaystyle=a^{r+1}\left(ca^{n+1}\sum_{j=1}^{r}a^{j-1}-rd\right)+\left(rca^{r+n+1}-da\sum_{j=1}^{r}a^{r-j}\right)$
$\displaystyle=ca^{r+n+2}\mathbf{R}_{r}-rda^{r+1}+rca^{r+n+1}-da\mathbf{R}_{r}$
$\displaystyle=a\mathbf{R}_{r}\mathbf{s}_{r+1}+ra^{r+1}\mathbf{s}_{0}$

∎

##  7 Applications

In this section, we apply our results to some known generating sequences, as
well as to new families of sequences. Our main goal in these applications is
to determine the unique $(m-1)$-tuple that realizes $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})$, which is equivalent to determine the unique
residual $(m-1)-$tuple $(\alpha_{1},\ldots,\alpha_{m-1})$ such that
$(\mathbf{s}_{0}/e)-1=\sum_{j=1}^{m-1}\alpha_{j}\mathbf{R}_{j}$, where
$e=\gcd(S_{n})$. We know, by Corollary 6.8, that the Frobenius number of the
numerical semigroup $(1/e)S_{n}$ is given by
$\sum_{j=1}^{m-1}\alpha_{j}\mathbf{s}_{j}-\mathbf{s}_{0}$. This solves the
Frobenius problem for the numerical semigroup $(1/e)S_{n}$. Besides, we
compute the Frobenius number of $(1/e)S_{n}$ explicitly in some cases and show
how to compute the genus of $(1/e)S_{n}$ in our first application; in the
remaining cases, the computation of the genus involves complicated sums that
we will not show here.

###  7.1 The generating sequence $x_{n}=5\cdot 3^{n}-1$

We test our results on the generating sequence $x_{n}=5\cdot 3^{n}-1$. Since
$5=3^{2}-(1+3)$, by Proposition 4.7, we obtain the representation

$\mathbf{s}_{n+3}=\mathbf{s}_{n+2}+2\mathbf{s}_{n+1}+2\mathbf{s}_{n}+3\mathbf{s}_{1}+(2\mathbf{s}_{0}-6)\mathbf{s}_{0}.$

Now, $2\mathbf{s}_{0}=10\cdot 3^{n}-2=3^{n+2}+3^{n}-1\geq 3^{n+2}$, so that by
Proposition 5.4, $e(S_{n})=n+3$.

Now, since $\gcd(S_{n})=2$, for all $n\geq 1$, we represent $\mathbf{s}_{0}/2$
as follows:

$\frac{5\cdot 3^{n}-1}{2}=\frac{3^{n+1}+2\cdot
3^{n}-1}{2}=\frac{(3^{n+1}-1)+2(3^{n}-1)+2}{2}=\mathbf{R}_{n+1}+2\mathbf{R}_{n}+1.$

By Corollay 6.8, we obtain $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=\mathbf{s}_{n+1}+2\mathbf{s}_{n}$ and a direct
computation shows that

${\rm
F}((1/2)S_{n})=(1/2)(\mathbf{s}_{n+1}+2\mathbf{s}_{n}-\mathbf{s}_{0})=5\cdot
3^{n}\mathbf{R}_{n}+1.$

To find the genus of $S_{n}$, first we calculate the sum
$\sum_{(\beta_{1},\ldots,\beta_{n+2})}\left(\sum_{j=1}^{n+2}\beta_{j}\mathbf{s}_{j}\right)$
taken over all residual $(n+2)-$tuples $(\beta_{1},\ldots,\beta_{n+2})$ which
are less than or equal to $(0,\ldots,0,2,1,0)$ with respect to the
colexicographic order. We have

$\displaystyle\sum_{(\beta_{1},\ldots,\beta_{n+2})}\left(\sum_{j=1}^{n+2}\beta_{j}\mathbf{s}_{j}\right)$
$\displaystyle=\sum_{(\beta_{1},\ldots,\beta_{n+1})}\left(\sum_{j=1}^{n+1}\beta_{j}\mathbf{s}_{j}\right)$
$\displaystyle=\sum_{(\beta_{1},\ldots,\beta_{n})}\left(\sum_{j=1}^{n}\beta_{j}\mathbf{s}_{j}\right)+\sum_{(\beta_{1},\ldots,\beta_{n})}\left(\sum_{j=1}^{n}\beta_{j}\mathbf{s}_{j}+\mathbf{s}_{n+1}\right)$
$\displaystyle=\sum_{(\beta_{1},\ldots,\beta_{n})}\left(\sum_{j=1}^{n}\beta_{j}\mathbf{s}_{j}\right)+\sum_{(\beta_{1},\ldots,\beta_{n-1})}\left(\sum_{j=1}^{n-1}\beta_{j}\mathbf{s}_{j}+\mathbf{s}_{n+1}\right)$
$\displaystyle+\sum_{(\beta_{1},\ldots,\beta_{n-1})}\left(\sum_{j=1}^{n-1}\beta_{j}\mathbf{s}_{j}+\mathbf{s}_{n}+\mathbf{s}_{n+1}\right)+(2\mathbf{s}_{n}+\mathbf{s}_{n+1}).$

In the last expression, the sums are taken over all residual tuples, without
restriction. By Applying Proposition 6.10, we obtain

$\displaystyle\sum_{(\beta_{1},\ldots,\beta_{n+2})}\left(\sum_{j=1}^{n+2}\beta_{j}\mathbf{s}_{j}\right)$
$\displaystyle=\frac{1}{2}\left(3\mathbf{R}_{n}\mathbf{s}_{n+1}+n3^{n+1}\mathbf{s}_{0}\right)+\frac{1}{2}\left(3\mathbf{R}_{n-1}\mathbf{s}_{n}+(n-1)3^{n}\mathbf{s}_{0}\right)$
$\displaystyle+\mathbf{R}_{n}\mathbf{s}_{n+1}+\frac{1}{2}\left(3\mathbf{R}_{n-1}\mathbf{s}_{n}+(n-1)3^{n}\mathbf{s}_{0}\right)+\mathbf{R}_{n}(\mathbf{s}_{n}+\mathbf{s}_{n+1})$
$\displaystyle+(2\mathbf{s}_{n}+\mathbf{s}_{n+1})$
$\displaystyle=\frac{1}{2}\left((5n+6+25\mathbf{R}_{n})3^{n}+5\mathbf{R}_{n}+1\right)\mathbf{s}_{0}.$

Finally, we have

$\displaystyle g((1/2)S_{n})$
$\displaystyle=\frac{1}{(\mathbf{s}_{0}/2)}\sum_{(\beta_{1},\ldots,\beta_{n+2})}\left(\sum_{j=1}^{n+2}\beta_{j}(\mathbf{s}_{j}/2)\right)-\frac{\mathbf{s}_{0}/2-1}{2}$
$\displaystyle=\frac{1}{2}\left((5n+6+25\mathbf{R}_{n})3^{n}+5\mathbf{R}_{n}+1\right)-\frac{\mathbf{s}_{0}/2-1}{2}$
$\displaystyle=\frac{1}{2}(5n+6+25\mathbf{R}_{n})3^{n}.$

###  7.2 The generating sequence $x_{n}=(2^{k}-1)2^{n}-1$, where $k\geq 2$

In this case $S_{n}$ is a numerical semigroup for all $n\geq 1$. We know that
$e(S_{n})=n+k$. We also have

$\displaystyle\mathbf{s}_{0}-1=2^{n+k}-2^{n}-2=\mathbf{R}_{n+k}-\mathbf{R}_{n}-2.$

Since $\mathbf{R}_{n+k}=\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+\mathbf{R}_{n}+k$ (by
(3)), we get

$\mathbf{s}_{0}-1=\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+k-2.$

If we suppose $2\leq k\leq 2^{n}$, which is equivalent to $0\leq
k-2<\mathbf{R}_{n}$, then, by Corollary 6.5, there is a unique residual
$(n-1)-$tuple $(k_{1},\ldots,k_{n-1})$ such that
$k-2=\sum_{j=1}^{n-1}k_{j}\mathbf{R}_{j}$. Therefore,

$\mathbf{s}_{0}-1=\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+k-2=\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+\sum_{j=1}^{n-1}k_{j}\mathbf{R}_{j}.$

This representation was found in [2], and they gave a characterization of
${\rm Ap}(S_{n},\mathbf{s}_{0})$, computed ${\rm F}(S_{n})$ and gave a formula
for the genus of $S_{n}$. This characterization also can be obtained by our
methods. But we are interested in computing $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})$ and ${\rm F}(S_{n})$ in the case $k>2^{n}$, which
was not solved in [2].

Assume $k>2^{n}$. In this case, we cannot represent $k-2$ in the form
$k-2=\sum_{j=1}^{n-1}k_{j}\mathbf{R}_{j}$ for any residual $(n-1)-$tuple
$(k_{1},\ldots,k_{n-1})$. We proceed as follows. By (3), we have
$\mathbf{R}_{n+k-2^{n}-1}=\sum_{j=n}^{n+k-2^{n}-2}\mathbf{R}_{j}+\mathbf{R}_{n}+k-2^{n}-1$,
or, equivalently,
$k-2=\mathbf{R}_{n+k-2^{n}-1}-\sum_{j=n}^{n+k-2^{n}-2}\mathbf{R}_{j}$. Then,

$\displaystyle\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+k-2$
$\displaystyle=\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+\mathbf{R}_{n+k-2^{n}-1}-\sum_{j=n}^{n+k-2^{n}-2}\mathbf{R}_{j}$
$\displaystyle=\sum_{j=n+k-2^{n}}^{n+k-1}\mathbf{R}_{j}+2\mathbf{R}_{n+k-2^{n}-1}.$

We see that the residual $(n+k-1)-$tuple that realizes $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})$ is $(0,\ldots,0,2,1,\ldots,1)$, where the 2 is the
$(n+k-2^{n}-1)-$th coordinate. It follows that if $2^{n}<k$, then

$\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=2\mathbf{s}_{n+k-2^{n}-1}+\sum_{j=n+k-2^{n}}^{n+k-1}\mathbf{s}_{j}.$

By (4) we have
$2\mathbf{s}_{n+k-2^{n}-1}+\sum_{j=n+k-2^{n}}^{n+k-1}\mathbf{s}_{j}=\mathbf{s}_{n+k}-2^{n}-1$,
so we can compute the Frobenius number of $S_{n}$ as follows:

$\displaystyle{\rm F}(S_{n})$
$\displaystyle=\mathbf{s}_{n+k}-2^{n}-1-\mathbf{s}_{0}$
$\displaystyle=\mathbf{s}_{n+k}-2^{n}-1-2^{n+k}+2^{n}+1$
$\displaystyle=\mathbf{s}_{n+k}-2^{n+k}$
$\displaystyle=2^{2n+2k}-2^{2n+k}-2^{n+k}-1.$

###  7.3 The generating sequence $x_{n}=(2^{k}+1)2^{n}-(2^{k}-1)$, where
$k\geq 2$

This sequence is the generating sequence considered in [8]. The monoid $S_{n}$
is a numerical semigroup for all $n\geq 1$. Note that

$\mathbf{s}_{0}-1=2^{n+k}+2^{n}-2^{k}.$

We consider the following cases.

#### The case $k=n\geq 2$.

We have $e(S_{n})=n+k+1=2k+1$ and

$\mathbf{s}_{0}-1=2^{2k}=\mathbf{R}_{2k}+\mathbf{R}_{1}.$

Therefore, the residual $(2k)-$tuple that realizes $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})$ is $(1,0,\ldots,0,1)$ and $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=\mathbf{s}_{2k}+\mathbf{s}_{1}$. It is easily seen
that

${\rm
F}(S_{n})=\mathbf{s}_{2k}+\mathbf{s}_{1}-\mathbf{s}_{0}=2^{4k}+2^{3k}+2^{2k}+1.$

#### The case $2\leq k<n$.

Here, $e(S_{n})=n+k+1$ and

$\mathbf{s}_{0}-1=\mathbf{R}_{n+k}+\mathbf{R}_{n-1}+2^{n-1}-2^{k}+1.$

Note that $2^{n-1}-2^{k}+1<\mathbf{R}_{n-1}$, so there is a unique residual
$(n-2)-$tuple $(t_{1},\ldots,t_{n-2})$ such that
$2^{n-1}-2^{k}+1=\sum_{j=1}^{n-2}t_{j}\mathbf{R}_{j}$. Thus,

$\mathbf{s}_{0}-1=\mathbf{R}_{n+k}+\mathbf{R}_{n-1}+\sum_{j=1}^{n-2}t_{j}\mathbf{R}_{j}.$

Therefore, the residual $(n+k)-$tuple that realizes $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})$ is $(t_{1},\ldots,t_{n-2},1,0,\ldots,0,1)$ and we
can write

$\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=\mathbf{s}_{n+k}+\mathbf{s}_{n-1}+\sum_{j=1}^{n-2}t_{j}\mathbf{s}_{j}.$

#### The case $k>n$.

In this case $e(S_{n})=n+k$. We write

$\displaystyle\mathbf{s}_{0}-1$
$\displaystyle=2^{n+k-1}+2^{n}+2^{n+k-1}-2^{k}$
$\displaystyle=2^{n+k-1}+2^{n}+2^{n+k-2}+\cdots+2^{k}$
$\displaystyle=\mathbf{R}_{n+k-1}+\cdots+\mathbf{R}_{k}+2^{n}+n.$

We have $2^{n}+n<\mathbf{R}_{k}$, unless $n=1$ and $k=2$. So, if $n\neq 1$ or
$k\neq 2$, and $k>n$, then there is a unique residual $(k-1)-$tuple
$(t_{1},\ldots,t_{k-1})$ such that
$\sum_{j=1}^{k-1}t_{j}\mathbf{R}_{j}=2^{n}+n$. Therefore, the residual
$(n+k-1)-$tuple that realizes $\max{\rm Ap}(S_{n},\mathbf{s}_{0})$ is
$(t_{1},\ldots,t_{k-1},1,1,\ldots,1)$ and we get

$\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=\mathbf{s}_{n+k-1}+\cdots+\mathbf{s}_{k}+\sum_{j=1}^{k-1}t_{j}\mathbf{s}_{j}.$

We can go a little further: if $n>2$, then

$\mathbf{s}_{0}-1=\mathbf{R}_{n+k-1}+\cdots+\mathbf{R}_{k}+\mathbf{R}_{n}+n+1.$

Clearly, $n+1<\mathbf{R}_{n}$. So there is a residual $(n-1)-$tuple
$(u_{1},\ldots,u_{n-1})$ such that $n+1=\sum_{j=1}^{n-1}u_{j}\mathbf{R}_{j}$.
Thus, the residual $(n+k-1)-$tuple that realizes $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})$ is
$(u_{1},\ldots,u_{n-1},1,0,\ldots,0,1,1,\ldots,1)$ and

$\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=\mathbf{s}_{n+k-1}+\cdots+\mathbf{s}_{k}+\mathbf{s}_{n}+\sum_{j=1}^{n-1}u_{j}\mathbf{s}_{j}.$

When $n=1$ and $k=2$, we have $\mathbf{s}_{0}-1=7=2\mathbf{R}_{2}$, so
$\max{\rm Ap}(S_{1},\mathbf{s}_{0})=2\mathbf{s}_{2}$.

###  7.4 Sequences of type $x_{n}=(a^{k}-1)a^{n}-1$, where $a\geq 3$

Let $a\geq 3$ and $k\geq 1$. We consider the generating sequence
$x_{n}=(a^{k}-1)a^{n}-1$. Here, $S_{n}$ is a numerical semigroup for all
$n\geq 1$. We know that $e(S_{n})=n+k+1$. Now,

$\displaystyle\mathbf{s}_{0}-1$ $\displaystyle=a^{n+k}-a^{n}-2$
$\displaystyle=(a-1)\mathbf{R}_{n+k}-(a-1)\mathbf{R}_{n}-2$
$\displaystyle=(a-2)\mathbf{R}_{n+k}+\mathbf{R}_{n+k}-(a-1)\mathbf{R}_{n}-2$
$\displaystyle=(a-2)\mathbf{R}_{n+k}+(a-1)\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+\mathbf{R}_{n}+k-(a-1)\mathbf{R}_{n}-2$
$\displaystyle=(a-2)\mathbf{R}_{n+k}+(a-1)\sum_{j=n+1}^{n+k-1}\mathbf{R}_{j}+\mathbf{R}_{n}+k-2$

We consider some cases.

#### The case $k=1$.

If $n=1$, then $\mathbf{s}_{0}-1=(a-2)\mathbf{R}_{2}$, $\max{\rm
Ap}(S_{1},\mathbf{s}_{0})=(a-2)\mathbf{s}_{2}$ and, in this case, it is easy
to see that ${\rm
F}(S_{1})=(a-2)\mathbf{s}_{2}-\mathbf{s}_{0}=a^{5}-3a^{4}+2a^{3}-a^{2}+3$.

Now assume that $n>1$. Then,

$\mathbf{s}_{0}-1=(a-2)\mathbf{R}_{n+1}+\mathbf{R}_{n}-1=(a-2)\mathbf{R}_{n+1}+a\mathbf{R}_{n-1}.$

So the residual $(n+1)-$tuple that realizes $\max{\rm
Ap}(S_{1},\mathbf{s}_{0})$ is $(0,\ldots,0,a,0,a-2)$ and we have $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=(a-2)\mathbf{s}_{n+1}+a\mathbf{s}_{n-1}$. It is not
difficult to verify that

${\rm F}(S_{n})=a^{2n+3}-3a^{2n+2}+3a^{2n+1}-a^{2n}-a^{n+1}+a^{n}-2a+3.$

#### The case $n=1$ and $k>1$.

We have in this case

$\displaystyle\mathbf{s}_{0}-1$
$\displaystyle=(a-2)\mathbf{R}_{k+1}+(a-1)\sum_{j=2}^{k}\mathbf{R}_{j}+\mathbf{R}_{1}+k-2$
$\displaystyle=(a-2)\mathbf{R}_{k+1}+(a-1)\sum_{j=2}^{k}\mathbf{R}_{j}+k-1.$

If $k\leq a+1$, which is equivalent to $k-1<\mathbf{R}_{2}$, then the residual
$(k+1)-$tuple that realizes $\max{\rm Ap}(S_{1},\mathbf{s}_{0})$ is
$(k-1,a-1,a-1,\ldots,a-1,a-2)$ and

$\max{\rm
Ap}(S_{1},\mathbf{s}_{0})=(a-2)\mathbf{s}_{k+1}+(a-1)\sum_{j=2}^{k}\mathbf{s}_{j}+(k-1)\mathbf{s}_{1}.$

The Frobenius number of $S_{1}$ is given by the following formula:

${\rm
F}(S_{n})=a^{2k+3}-a^{2k+2}-2a^{k+3}+ka^{k+2}-a^{k+1}+a^{3}-(k-1)a^{2}-(k-1)a+3.$

Now, if $k>a+1$, then

$\displaystyle\mathbf{s}_{0}-1$
$\displaystyle=(a-2)\mathbf{R}_{k+1}+(a-1)\sum_{j=2}^{k}\mathbf{R}_{j}+k-1$
$\displaystyle=(a-2)\mathbf{R}_{k+1}+(a-1)\sum_{j=2}^{k}\mathbf{R}_{j}+\mathbf{R}_{2}+(k-2-a).$

By (3) we have
$\mathbf{R}_{k-a}=(a-1)\sum_{j=2}^{k-a-1}\mathbf{R}_{j}+\mathbf{R}_{2}+(k-2-a)$,
so we get

$\displaystyle\mathbf{s}_{0}-1$
$\displaystyle=(a-2)\mathbf{R}_{k+1}+(a-1)\sum_{j=k-a}^{k}\mathbf{R}_{j}+\mathbf{R}_{k-a}$
$\displaystyle=(a-2)\mathbf{R}_{k+1}+(a-1)\sum_{j=k-a+1}^{k}\mathbf{R}_{j}+a\mathbf{R}_{k-a}.$

Thus, the residual $(k+1)-$tuple that realizes $\max{\rm
Ap}(S_{1},\mathbf{s}_{0})$ is $(0,\ldots,0,a,a-1,\ldots,a-1,a-2)$, where $a$
is in the $(k-a)-$th coordinate. Therefore,

$\max{\rm
Ap}(S_{1},\mathbf{s}_{0})=(a-2)\mathbf{s}_{k+1}+(a-1)\sum_{j=k-a+1}^{k}\mathbf{s}_{j}+a\mathbf{s}_{k-a}.$

The Frobenius number of $S_{1}$ is given by

${\rm F}(S_{1})=a^{2k+3}-a^{2k+2}-a^{k+3}+a^{k+2}-a^{k+1}-a^{2}+3.$

#### The case $n>1$ and $k\geq 2$.

Here we have two cases. In the first one, $0\leq k-2<(a-1)\mathbf{R}_{n}$. By
the division algorithm there exist unique integers $q$ and $r$ such that
$0\leq q<a-1$, $0\leq r<\mathbf{R}_{n}$, and $k-2=q\mathbf{R}_{n}+r$. Thus,

$\mathbf{s}_{0}-1=(a-2)\mathbf{R}_{n+k}+(a-1)\sum_{j=n+1}^{n+k-1}\mathbf{R}_{j}+(q+1)\mathbf{R}_{n}+r.$

Note that $q+1<a$. Also, there is a unique residual $(n-1)-$tuple
$(t_{1},\ldots,t_{n-1})$ such that $r=\sum_{j=1}^{n-1}t_{j}\mathbf{R}_{j}$. So
the residual $(n+k)-$tuple that realizes $\max{\rm Ap}(S_{n},\mathbf{s}_{0})$
is $(t_{1},\ldots,t_{n-1},q+1,a-1,\ldots,a-1,a-2)$ and

$\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=(a-2)\mathbf{s}_{n+k}+(a-1)\sum_{j=n+1}^{n+k-1}\mathbf{s}_{j}+(q+1)\mathbf{s}_{n}+\sum_{j=1}^{n-1}t_{j}\mathbf{s}_{j}.$

In the case in which $k-2\geq(a-1)\mathbf{R}_{n}$, we have

$\displaystyle\mathbf{s}_{0}-1$
$\displaystyle=(a-2)\mathbf{R}_{n+k}+(a-1)\sum_{j=n+1}^{n+k-1}\mathbf{R}_{j}+a\mathbf{R}_{n}+k-2-(a-1)\mathbf{R}_{n}$
$\displaystyle=(a-2)\mathbf{R}_{n+k}+(a-1)\sum_{j=n}^{n+k-1}\mathbf{R}_{j}+\mathbf{R}_{n}+k-2-(a-1)\mathbf{R}_{n}$

Let $t=n+k-2-(a-1)\mathbf{R}_{n}$. By (3), we get the equality

$\mathbf{R}_{t}=(a-1)\sum_{j=n}^{t-1}\mathbf{R}_{j}+\mathbf{R}_{n}+k-2-(a-1)\mathbf{R}_{n}.$

Hence,

$\displaystyle\mathbf{s}_{0}-1$
$\displaystyle=(a-2)\mathbf{R}_{n+k}+(a-1)\sum_{j=t}^{n+k-1}\mathbf{R}_{j}+\mathbf{R}_{t}$
$\displaystyle=(a-2)\mathbf{R}_{n+k}+(a-1)\sum_{j=t+1}^{n+k-1}\mathbf{R}_{j}+a\mathbf{R}_{t}.$

Thus, the residual $(n+k)-$tuple that realizes $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})$ is $(0,\ldots,0,a,a-1,\ldots,a-1,a-2)$, where $a$
is in the $t-$th coordinate. Therefore,

$\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=(a-2)\mathbf{s}_{n+k}+(a-1)\sum_{j=t+1}^{n+k-1}\mathbf{s}_{j}+a\mathbf{s}_{t},$

where $t=n+k-2-(a-1)\mathbf{R}_{n}$. By using (4), we see that

$(a-1)\sum_{j=t+1}^{n+k-1}\mathbf{s}_{j}+a\mathbf{s}_{t}=\mathbf{s}_{n+k}-(n+k-t)(a-1).$

So we can write $\max{\rm
Ap}(S_{n},\mathbf{s}_{0})=(a-1)\mathbf{s}_{n+k}-(n+k-t)(a-1)$ and

$\displaystyle{\rm F}(S_{n})$
$\displaystyle=(a-1)\mathbf{s}_{n+k}-(n+k-t)(a-1)-\mathbf{s}_{0}$
$\displaystyle=a^{2n+2k+1}-a^{2n+2k}-a^{2n+k+1}-a^{2n+k}-a^{n+k}-a^{n+1}+2a^{n}-2a+3.$

## References

  * [1] Gu, Z., On the numerical semigroup generated by $\left\\{b^{n+i+1}+\frac{b^{n+i}-1}{b-1}\right\\}$, Discrete Math. Appl., 30 (4) (2020) 257-264.
  * [2] Gu, Z., Tang, X., _The Frobenius problem for a class of numerical semigroups_ , Int. J. Number Theory, 13 (2017) 1-13.
  * [3] Rosales, J. C., Branco, M. B., Torrão, D., _The Frobenius problem for Mersenne numerical semigroups_ , Math. Z., 286 (2017) 1-9.
  * [4] Rosales, J. C., Branco, M. B., Torrão, D., _The Frobenius problem for repunit numerical semigroups_ , Ramanujan J., 40 (2016) 323-334.
  * [5] Rosales, J. C., Branco, M. B., Torrão, D., _The Frobenius problem for Thabit numerical semigroups_ , J. Number Theory, 155 (2015) 85-99.
  * [6] Rosales, J.C., García-Sánchez, P. A., Numerical semigroups, Developments in Mathematics, Vol. 20, Springer, New York, 2009.
  * [7] Snyder, W. M., _Factoring repunits_ , Am. Math. Monthly 89 (1892) 462–466.
  * [8] Song, K., The Frobenius problem for extended Thabit numerical semigroups, Integers, 21 (2021) #A17.
  * [9] Song, K., _The Frobenius problem for numerical semigroups generated by the Thabit numbers of the first, second kind base $b$ and the Cunningham numbers_, Bull. Korean Math. Soc. 57 No.3 (2020) 623–647.
  * [10] Yates, S., _The Mystique of repunits_. Math. Mag. 51 (1978) 22–28.