# The asymptotic dimension of the grand arc graph is infinite

Michael C. Kopreski<EMAIL_ADDRESS>
###### Abstract.

Let $\Sigma$ be a compact, orientable surface, and let $\Gamma$ be a relation
on its boundary components such that the prescribed arc graph
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is Gromov hyperbolic and non-
trivial. We show that
$\operatorname{asdim}\operatorname{\mathcal{A}}(\Sigma,\Gamma)\geq-\chi(\Sigma)-1$.
As a first application, we prove that the asymptotic dimension of the grand
arc graph is infinite when there are finitely many equivalence classes of
maximal ends.

##  1\. Introduction

Let $\Sigma$ be a compact, orientable surface with boundary, and let $\Gamma$
be a relation on its boundary components. A simple, essential arc $a$ in
$\Sigma$ is $\Gamma$-allowed if it joins boundary components in $\Gamma$. The
$\Gamma$-prescribed arc graph $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is
the full subgraph of $\operatorname{\mathcal{A}}(\Sigma)$ spanned by isotopy
classes of $\Gamma$-allowed arcs, and an essential ($\pi_{1}$-injective non-
peripheral) non-pants subsurface $W\subset\Sigma$ is a $\Gamma$-witness if it
intersects every $\Gamma$-allowed arc, up to isotopy. We assume throughout
that $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is non-trivial, i.e.
$\chi(\Sigma)\leq-1$, $\Sigma\neq\Sigma_{0}^{3}$, and $\Gamma\neq\varnothing$.

We suppose $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is $\delta$-hyperbolic.
If $\Sigma=\Sigma_{0}^{4}$, then
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)\subset\operatorname{\mathcal{A}}(\Sigma_{0}^{4})$
is a quasi-tree and
$\operatorname{asdim}\operatorname{\mathcal{A}}(\Sigma,\Gamma)=1$. Otherwise,
we prove a lower bound:

######  Theorem 1.1.

If $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is $\delta$-hyperbolic, then
$-\chi(\Sigma)-1\leq\operatorname{asdim}\operatorname{\mathcal{A}}(\Sigma,\Gamma).$

For $\Omega$ a surface of infinite topological type, let
$\operatorname{\mathcal{G}}(\Omega)$ denote the grand arc graph on $\Omega$
[BNV22]. By applying Theorem 1.1, we obtain the following:

######  Theorem 1.2.

Let $\Omega$ be an infinite-type surface with finitely many equivalence
classes of maximal ends. Then
$\operatorname{asdim}\operatorname{\mathcal{G}}(\Omega)=\infty$.

In Section 2, we use the theory of alignment-preserving maps [DT17] to show
that the Gromov boundary $\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$
contains $\partial\operatorname{\mathcal{A}}(\Sigma)$. From results of Gabai
[Gab14] and Pho-on [Po15] we obtain a compact subspace
$Z\subset\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ of dimension
$-\chi(\Sigma)-2$. We then prove that
$\operatorname{asdim}\operatorname{\mathcal{A}}(\Sigma,\Gamma)\geq\dim Z+1$,
extending a result for proper $\delta$-hyperbolic spaces, whence Theorem 1.1
follows.

In Section 3, we show that witness subsurfaces $W\subset\Omega$ for
$\operatorname{\mathcal{G}}(\Omega)$ of arbitrarily large complexity admit
prescribing relations $\Gamma$ such that
$\operatorname{\mathcal{A}}(W,\Gamma)$ quasi-isometrically embeds into
$\operatorname{\mathcal{G}}(\Omega)$, where $\Omega$ is an infinite-type
surface with finitely many classes of maximal ends. In fact,
$\operatorname{asdim}\operatorname{\mathcal{G}}(\Omega)=\infty$ or $W$ may be
chosen such that $\operatorname{\mathcal{A}}(W,\Gamma)$ as above is
$\delta$-hyperbolic: Theorem 1.2 thus follows from Theorem 1.1 and the
monotonicity of asymptotic dimension.

###  1.1. Background

An orientable surface $\Omega$ has infinite topological type if its
fundamental group is not finitely generated, or equivalently when
$\partial\Omega=\varnothing$, if $\Omega$ has infinite genus or infinitely
many punctures. Beginning with a 2009 blog post of Calegari [Cal09], mapping
class groups of infinite-type surfaces have been objects of considerable
contemporary study: see [AV20, CPV21] for surveys of recent results and open
problems.

An infinite-type surface $\Omega$ is classified by its genus, number of
punctures, and end space, which is obtained as the inverse limit of the
complementary components of a compact exhaustion [Ric63]. Its mapping class
group $\operatorname{Mod}(\Omega)$ is a non-compactly generated Polish group,
which by Mann–Rafi [MR20] admits a well defined coarse geometry in the sense
of [Ros14] when the end space of $\Omega$ satisfies certain conditions.
Mann–Rafi also define a preorder on the ends of $\Omega$ corresponding to
topological complexity, which always admits maximal elements [MR20, Prop.
4.7]. We shall denote by $\mathcal{S}(\Omega)$ the equivalence classes of
maximal ends in $\Omega$ with respect to this preorder.

Following Bar-Natan and Verberne, a grand arc in $\Omega$ is a bi-infinite arc
converging to maximal ends of distinct type [BNV22].

######  Definition 1.3 (Bar-Natan–Verberne).

Let $\Omega$ be an infinite-type surface with $|\mathcal{S}(\Omega)|<\infty$.
The grand arc graph $\operatorname{\mathcal{G}}(\Omega)$ is the simplicial
graph whose vertices correspond to isotopy classes of grand arcs and whose
edges are determined by disjointness.

The grand arc graph $\operatorname{\mathcal{G}}(\Omega)$ is a combinatorial
model for $\Omega$ which generalizes the ray graph defined by Calegari [Cal09]
on $S^{2}\setminus\text{Cantor set}$ and for surfaces with stable endspace
extends the omnipresent arc graph defined by Fanoni-Ghaswala-McLeay [FGM21].
$\operatorname{Mod}(\Omega)$ acts naturally on
$\operatorname{\mathcal{G}}(\Omega)$ by isometries. Bar-Natan–Verberne
classify the $\delta$-hyperbolicity of $\operatorname{\mathcal{G}}(\Omega)$
and show that when $\operatorname{\mathcal{G}}(\Omega)$ is
$\delta$-hyperbolic, the action of $\operatorname{Mod}(\Sigma)$ is quasi-
continuous, extends continuously to
$\partial\operatorname{\mathcal{G}}(\Omega)$, and has loxodromic elements.

####  1.1.1. Prescribed arc graphs

Prescribed arc graphs were defined by the author in [Kop23a] as combinatorial
models of finite-type surfaces that quasi-isometrically embed into
$\operatorname{\mathcal{G}}(\Omega)$. Excepting trivial cases they are
connected and infinite-diameter and their $\delta$-hyperbolicity is fully
determined by the prescribing relation $\Gamma$:

######  Theorem 1.4 ([Kop23a, Thm. 1.3]).

Assume that $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is non-trivial. Then
if $\chi(\Sigma)\geq-2$ or $\Sigma=\Sigma_{0}^{n+1}$ and $\Gamma$ is a
$n$-pointed star then $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is
$\delta$-hyperbolic. Otherwise, $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is
(uniformly) $\delta$-hyperbolic if and only if $\Gamma$ is not bipartite.

We note that if $\Gamma\subset\Gamma^{\prime}$ then every $\Gamma$-allowed arc
is $\Gamma^{\prime}$-allowed, which induces a simplicial map
$\iota:\operatorname{\mathcal{A}}(\Sigma,\Gamma)\to\operatorname{\mathcal{A}}(\Sigma,\Gamma^{\prime})$.
This map is $3$-coarsely surjective [Kop23a, Lem. 2.10]. In particular, since
the prescribed arc graph with the complete relation is exactly
$\operatorname{\mathcal{A}}(\Sigma)$,
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ always coarsely surjects onto
$\operatorname{\mathcal{A}}(\Sigma)$.

A compact, essential ($\pi_{1}$-injective, non-peripheral) non-pants
subsurface is a witness for a given combinatorial model if it intersects every
vertex. We call a witness $W\subset\Sigma$ for
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ a $\Gamma$-witness.

####  1.1.2. Boundaries of non-proper $\delta$-hyperbolic spaces

In general, if $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is non-trivial then
it is non-proper. For a geodesic $\delta$-hyperbolic space $X$, by $\partial
X$ we always mean the sequential boundary of $X$; when $X$ is non-proper,
$\partial X$ may be non-compact. In this setting, $\partial X$ does not
coincide with the geodesic boundary, but is instead homeomorphic to the quasi-
geodesic boundary [Has22]. We will make use of the following statement by
Hasegawa, from a construction of Kapovich–Benakli [KB02, Rmk. 2.16]:

######  Remark 1.5 ([Has22, Prop. 4]).

Fixing $x_{0}\in X$, for any $z\in\partial X$ there exists a
$(1+4\delta,12\delta)$-quasi-geodesic ray $\rho:[0,\infty)\to X$ based at
$x_{0}$ with $[\rho(n)]=z$.

Any quasi-isometry between geodesic $\delta$-hyperbolic spaces $X\to Y$
extends to a map $X\cup\partial X\to Y\cup\partial Y$ that restricts to a
homeomorphism on the boundaries (e.g. applying the proof of [DK18, Thm.
11.108]). Given $x,y\in X\cup\partial X$, let $(x|y)_{x_{0}}$ denote their
Gromov product at $x_{0}$. We occassionally omit the basepoint, which is
changeable up to bounded error.

####  1.1.3. Ending laminations

$\chi(\Sigma)\leq-1$, hence we fix a (finite-area) hyperbolic metric for
$\Sigma$ with geodesic boundary. We recall that a geodesic lamination on
$\Sigma$ is a closed subset $L\subset\Sigma$ which may be decomposed (in fact,
uniquely) into pair-wise disjoint simple geodesic leaves. $L$ is minimal if it
has no proper sublaminations, or equivalently, if every leaf is dense in $L$.

######  Definition 1.6.

Given a connected subspace $X\subset\Sigma$ with non-trivial $\pi_{1}$-image,
if $Y\subset\Sigma$ is the smallest essential subsurface containing $X$ up to
isotopy, then $Y$ is filled by $X$. If $Y=\Sigma$, then $X$ is filling.

######  Definition 1.7.

The space of ending laminations $\operatorname{\mathcal{EL}}(\Sigma)$ is the
set of filling minimal laminations on $\Sigma$, equipped with the coarse
Hausdorff topology. Similarly, let $\operatorname{\mathcal{EL}}_{0}(\Sigma)$
denote the space of minimal laminations that fill a subsurface containing
$\partial\Sigma$, again with the coarse Hausdorff topology.

By constructing infinite unicorn paths $P(a,\ell)$ between a fixed arc
$a\in\operatorname{\mathcal{A}}(\Sigma)$ and geodesic rays $\ell$ asymptotic
to laminations $L\in\operatorname{\mathcal{EL}}_{0}(\Sigma)$, we obtain:

######  Theorem 1.8 (Pho-on, [Po15]).

$\operatorname{\mathcal{EL}}_{0}(\Sigma)\cong\partial\operatorname{\mathcal{A}}(\Sigma)$.

##  2\. Asymptotic dimension of $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$

When $\Sigma=\Sigma_{0}^{4}$, then
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)\subset\operatorname{\mathcal{A}}(\Sigma_{0}^{4})$
is an infinite-diameter connected subgraph of a quasi-tree, hence likewise a
quasi-tree: $\operatorname{asdim}\operatorname{\mathcal{A}}(\Sigma,\Gamma)=1$.
For $\Sigma\neq\Sigma_{0}^{4}$, we first prove that
$\operatorname{\mathcal{EL}}_{0}(\Sigma)\cong\partial\operatorname{\mathcal{A}}(\Sigma)\subset\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$.

###  2.1. Alignment-preserving maps

We recall the theory of alignment-preserving maps from [DT17]. Let $X$ be a
geodesic metric space. Then a triple $(x,y,z)\in X^{3}$ is $K$-aligned if
$d(x,y)+d(y,z)\leq d(x,z)+K$. A Lipschitz map between geodesic metric spaces
$f:X\to Y$ is coarsely alignment preserving if there exists $K\geq 0$ for
which $f$ maps any $0$-aligned triple in $X$ to a $K$-aligned triple in $Y$.

Suppose that $f:X\to Y$ is a coarsely alignment preserving map between
geodesic $\delta$-hyperbolic spaces. Then we define
$\partial_{Y}X\subset\partial X$ to be

$\partial_{Y}X\mathrel{\mathop{:}}=\\{[\gamma]\in\partial
X\;\vline\;\gamma:\mathbb{R}^{+}\to X\text{ quasi-geodesic,
}\operatorname{diam}_{Y}(f\gamma(\mathbb{R}^{+}))=\infty\\}.$

######  Theorem 2.1 (Dowdall–Taylor, [DT17, Thm. 3.2]).

Let $f:X\to Y$ be a coarsely surjective, coarsely alignment preserving map
between geodesic $\delta$-hyperbolic spaces. Then $f$ admits an extension to a
homeomorphism $\partial f:\partial_{Y}X\to\partial Y$ such that if
$x_{n}\to\omega\in\partial_{Y}X$, then $f(x_{n})\to\partial f(\omega)$.

######  Lemma 2.2.

If $\Gamma$ is not bipartite then for any $\Gamma^{\prime}\supset\Gamma$ the
induced coarse surjection
$\iota:\operatorname{\mathcal{A}}(\Sigma,\Gamma)\to\operatorname{\mathcal{A}}(\Sigma,\Gamma^{\prime})$
is uniformly coarsely alignment-preserving.

###### Proof.

We first claim that if $\Gamma$ is not bipartite, then geodesics in
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ are uniformly (independent of
$\Gamma$) Hausdorff close to unicorn paths with coarsely the same endpoints,
and vice versa. If $\Gamma$ is not bipartite and if $\Sigma=\Sigma_{1}^{2}$
then $\Gamma$ is not two loops, then the claim holds by [Kop23a, §3]. If
instead $\Sigma=\Sigma_{1}^{2}$ and $\Gamma=\ell_{1}\cup\ell_{2}$ is two
loops, then
$\iota:\operatorname{\mathcal{A}}(\Sigma,\ell_{1})\to\operatorname{\mathcal{A}}(\Sigma,\Gamma)$
is a quasi-isometry by [Kop23a, Lem. 5.2] and we apply the Morse lemma. We
observe that if $\Gamma$ is not bipartite then neither is $\Gamma^{\prime}$.

We claim that for any geodesic $\gamma$ between
$a,b\in\operatorname{\mathcal{A}}(\Sigma,\Gamma)$, $\iota\gamma$ is uniformly
Hausdorff close to a geodesic between $\iota(a),\iota(b)$, whence the proof
follows. Let $\gamma^{\prime}$ be a unicorn path close to $\gamma$, in the
sense above. $\iota$ is Lipschitz, hence $\iota\gamma,\iota\gamma^{\prime}$
are close; since $\iota\gamma^{\prime}$ is a unicorn path in
$\operatorname{\mathcal{A}}(\Sigma,\Gamma^{\prime})$, choose a geodesic
$\gamma^{\prime\prime}$ close to $\iota\gamma^{\prime}$. By the Morse lemma,
there exists a geodesic $\gamma^{\prime\prime\prime}$ between
$\iota(a),\iota(b)$ that is close to $\gamma^{\prime\prime}$, hence close to
$\iota\gamma$. ∎

######  Corollary 2.3.

If $\Gamma$ is not bipartite and $\Gamma^{\prime}\supset\Gamma$, then there
exists an embedding
$(\partial\iota)^{-1}:\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma^{\prime})\to\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$.
∎

By [Kop23a, §5], if $\Sigma\neq\Sigma_{0}^{4}$ and
$\operatorname{\mathcal{A}}(\Gamma,\Sigma)$ is $\delta$-hyperbolic, then  (i)
$\Sigma=\Sigma_{0}^{n+1}$and $\Gamma$ is an $n$-pointed star,  (ii)
$\Sigma=\Sigma_{1}^{2}$and $\Gamma$ is a non-loop edge, or  (iii) $\Gamma$is
not bipartite.  In case (i), by [Kop23a, Lem. 5.4]
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is quasi-isometric to
$\operatorname{\mathcal{A}}(\Sigma,\ell_{0})$, where $\ell_{0}$ is a single
loop and hence not bipartite. Thus for cases (i) and (iii), Corollary 2.3
implies
$\partial\operatorname{\mathcal{A}}(\Sigma)\subset\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$.
In case (ii), every $\Gamma$-witness is in fact a witness for the usual arc
graph: by [Kop23] $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ and
$\operatorname{\mathcal{A}}(\Sigma)$ have the same quasi-isometry type, hence
$\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)\cong\partial\operatorname{\mathcal{A}}(\Sigma)$.

######  Proposition 2.4.

Let $\Sigma\neq\Sigma_{0}^{4}$ and $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$
be $\delta$-hyperbolic.
$\partial\operatorname{\mathcal{A}}(\Sigma)\cong\operatorname{\mathcal{EL}}_{0}(\Sigma)$
embeds canonically into $\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$. ∎

###  2.2. A lower bound

From [Gab14], we have the following:

######  Theorem 2.5 (Gabai).

Let $S$ be the $(n+4)$-times punctured sphere. Then
$\operatorname{\mathcal{EL}}(S)$ is homeomorphic to the $n$-dimensional
Nöbeling space.

For any $\Sigma$ with $\chi(\Sigma)\leq-2$, let $n=n(\Sigma)=-\chi(\Sigma)-2$
and let $\Gamma$ be a prescribing relation such that
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is $\delta$-hyperbolic. We may
choose an essential $(n+4)$-punctured sphere $S$ that contains all of the
punctures of $\Sigma$, thus
$\operatorname{\mathcal{EL}}(S)\subset\operatorname{\mathcal{EL}}_{0}(\Sigma)\cong\partial\operatorname{\mathcal{A}}(\Sigma)$.
Then applying Proposition 2.4 and Theorem 2.5,
$\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ contains the $n$-dimension
Nöbeling space, and in particular, a compact subspace
$Z\subset\operatorname{\mathcal{EL}}(S)$ of dimension $n$ by the universal
embedding property of Nöbeling spaces [Nob30].

For the remainder of the section, we will prove the following generalization
of a result for proper $\delta$-hyperbolic spaces (e.g. [BL08, Prop. 6.2]):

######  Proposition 2.6.

Let $X$ be a geodesic $\delta$-hyperbolic space with $Z\subset\partial X$
compact. Then $\operatorname{asdim}X\geq\dim Z+1$.

Since $\partial\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ contains a
$n(\Sigma)$-dimensional compact subspace for $\chi(\Sigma)\leq-2$, Theorem 1.1
follows (vacuously for $\chi(\Sigma)>-2$).

By $\delta$-hyperbolic, we mean that geodesic triangles are $\delta$-slim. Let
$X$ be a geodesic $\delta$-hyperbolic space and let $Z\subset\partial X$ be
compact. A metric $d:\partial X\times\partial X\to[0,\infty)$ is visual if
there exist $k_{1},k_{2}$ and $a>0$ such that

$k_{1}a^{-(\xi|\xi^{\prime})}\leq d(\xi,\xi^{\prime})\leq
k_{2}a^{-(\xi|\xi^{\prime})}.$

Such metrics always exist [BH99, Prop. III.H.3.21] and are compatible with the
usual topology on the (sequential) boundary: $d(\xi_{i},\xi)\to 0$ if and only
if $(\xi_{i}|\xi)\to\infty$, which is equivalent to $\xi_{i}\to\xi$.

######  Notation.

Where unambiguous, we denote by $|xx^{\prime}|$ the distance between
$x,x^{\prime}\in X$ a metric space. Given a specified basepoint $o\in X$, let
$|x|\mathrel{\mathop{:}}=|ox|$.

######  Definition 2.7.

For $(Z,d)$ a bounded metric space, the hyperbolic cone $\operatorname{Co}Z$
is the topological cone $Z\times[0,\infty)/Z\times\\{0\\}$ endowed with the
following metric. Let $\mu=\pi/\operatorname{diam}(Z)$. For any
$x=(z,t),x^{\prime}=(z^{\prime},t^{\prime})\in\operatorname{Co}Z$, consider a
geodesic triangle $\bar{o}\bar{x}\bar{x}^{\prime}\subset H^{2}$ with
$|\bar{o}\bar{x}|=t,|\bar{o}\bar{x}^{\prime}|=t^{\prime}$, and
$\angle_{\bar{o}}(\bar{x},\bar{x}^{\prime})=\mu|zz^{\prime}|$. Then let
$|xx^{\prime}|\mathrel{\mathop{:}}=|\bar{x}\bar{x}^{\prime}|$.

This metric is compatible with the usual topology on $\operatorname{Co}Z$. In
addition, $\operatorname{Co}Z$ is $\delta$-hyperbolic,
$Z\hookrightarrow\partial\operatorname{Co}Z$ via the geodesic rays
$\gamma_{z}:t\mapsto(z,t)$, and $d$ is visual for
$Z\subset\partial\operatorname{Co}Z$ with respect to $\operatorname{Co}Z$
[Buy06, Prop. 6.1]. We fix $o=Z\times\\{0\\}$ as a basepoint for
$\operatorname{Co}Z$. Analogously to [Buy06, Prop. 6.2], we have the
following:

######  Lemma 2.8.

Let $X$ be a geodesic $\delta$-hyperbolic space and let $Z\subset\partial X$
be compact. Then $\operatorname{Co}Z$ quasi-isometrically embeds into $X$.

###### Proof.

Fix a basepoint $x_{0}\in X$ and let
$\delta^{\prime}=\delta(\operatorname{Co}Z)$. Since $d$ is visual for both $X$
and $\operatorname{Co}Z$, up to rescaling $X$ we may assume that
$(z|z^{\prime})_{x_{0}}$ and $(z|z^{\prime})_{o}$ are uniformly close for all
$z,z^{\prime}\in Z$. For each $z\in Z$, fix a representative
$(\kappa_{0},12\delta)$-quasi-geodesic ray $\rho_{z}\in z$ eminating from
$x_{0}$ by Remark 1.5, where $\kappa_{0}=1+4\delta$. Let
$\iota:\operatorname{Co}Z\to X$ be the map $(z,t)\mapsto\rho_{z}(t)$.

Since $\gamma_{z}\in z$ is geodesic,
$(z|\gamma_{z}(t))_{o}>|\gamma_{z}(t)|-\delta^{\prime}$ and
$|\gamma_{z}(t)|=t$. Likewise, since $\rho_{z}\in z$ is
$(\kappa_{0},12\delta)$-quasi-geodesic,
$(z|\rho_{z}(t))_{x_{0}}>|\rho_{z}(t)|-M-\delta$, where
$M=M(\kappa_{0},12\delta)$ is the Morse constant, and
$|\rho_{z}(t)|=\kappa_{z}(t)t+O_{\delta}(1)$ with
$\frac{1}{\kappa_{0}}\leq\kappa_{z}(t)\leq\kappa_{0}$. Let
$y=(z,t),y^{\prime}=(z^{\prime},t^{\prime})\in\operatorname{Co}Z$. By [BS00,
Lem. 5.1], we have

$\displaystyle|yy^{\prime}|$
$\displaystyle=|\gamma_{z}(t)\gamma_{z^{\prime}}(t^{\prime})|$
$\displaystyle=|\gamma_{z}(t)|+|\gamma_{z^{\prime}}(t^{\prime})|-2\min\\{|\gamma_{z}(t)|,|\gamma_{z^{\prime}}(t^{\prime})|,(z|z^{\prime})_{o}\\}+O_{\delta^{\prime}}(1)$
$\displaystyle=t+t^{\prime}-2\min\\{t,t^{\prime},(z|z^{\prime})_{o}\\}+O_{\delta^{\prime}}(1)$

and similarly,

$\displaystyle|\iota(y)\iota(y^{\prime})|$
$\displaystyle=|\rho_{z}(t)\rho_{z^{\prime}}(t^{\prime})|$
$\displaystyle=\kappa_{z}(t)t+\kappa_{z^{\prime}}(t^{\prime})t^{\prime}-2\min\\{\kappa_{z}(t)t,\kappa_{z^{\prime}}(t^{\prime})t^{\prime},(z|z^{\prime})_{x_{0}}\\}+O_{\delta}(1).$

$\iota$ is a quasi-isometric embedding. ∎

Applying the argument in [BL08, Prop. 6.5], we obtain that
$\operatorname{asdim}\operatorname{Co}Z\geq\dim Z+1$. Proposition 2.6 then
follows from Lemma 2.8. $/\\!\\!/$

##  3\. Asymptotic dimension of $\operatorname{\mathcal{G}}(\Omega)$

We prove Theorem 1.2. Let $\Omega$ be a surface of infinite topological type
and let $\operatorname{\mathcal{S}}(\Omega)$ be the set of equivalence classes
of maximal ends.

######  Definition 3.1.

An essential, connected, compact subsurface $\Sigma\subset\Omega$ is fully
separating if every complementary component is adjacent to exactly one
boundary component of $\Sigma$.

Any compact subsurface can be enlarged to one that is fully separating: e.g.
we may glue $1$-handles between boundary components adjacent to the same
complementary component and take the compact surface filled by the result.

######  Lemma 3.2.

Suppose that $\Sigma\subset\Omega$ is a fully separating non-annular witness
for $\mathcal{G}(\Omega)$ and $|\mathcal{S}(\Omega)|=m<\infty$. There exists a
minimally $m$-partite relation $\Gamma$ on $\pi_{0}(\partial\Sigma)$ such that
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ quasi-isometrically embeds into
$\mathcal{G}(\Omega)$. In particular, $\Gamma$ is not bipartite if
$|\mathcal{S}(\Omega)|>2$.

###### Proof.

Since $\Sigma$ is a witness for $\operatorname{\mathcal{G}}(\Omega)$, it must
separate distinct equivalence classes of maximal ends. In particular, each
boundary component is adjacent to a complementary component containing ends of
at most one class in $\operatorname{\mathcal{S}}(\Omega)$. Color each
component $c\in\pi_{0}(\partial\Sigma)$ with the corresponding class
$e(c)\in\operatorname{\mathcal{S}}(\Omega)$, if one exists; let $\Gamma$ be
the complete $m$-partite relation on these colors (components without a
corresponding class are left isolated).

Fix a hyperbolic metric on $\Sigma$. For each colored boundary component $c$,
choose a parameterization $c:[0,1)\to\Sigma$ and a simple ray $\rho_{c}$
disjoint from $\operatorname{int}(\Sigma)$ with origin $c(0)$ and converging
to an end in $e(c)$. Let $a\in V(\operatorname{\mathcal{A}}(\Sigma,\Gamma))$
terminate on $c_{1},c_{2}\in\pi_{1}(\partial\Sigma)$. Let $\alpha$ be the
geodesic representative for $a$ with endpoints $c_{i}(t_{i})$ and define
$\delta_{i}=c_{i}|_{[0,t_{i}]}$ to be the subpath of $c_{i}$ between
$c_{i}(0)$ and $c_{i}(t_{i})$. Let $\alpha^{\dagger}$ denote the extension of
$\alpha$ from both endpoints by $\bar{\delta}_{i}*\rho_{c_{i}}$, for $i=1,2$
as appropriate. $\alpha^{\dagger}$ is a simple arc converging to ends in
$e(c_{1}),e(c_{2})$ respectively, which are non-equivalent and maximal by our
choice of $\Gamma$. $\alpha^{\dagger}$ is a grand arc. The map
$a\mapsto[\alpha^{\dagger}]$ preserves disjointness hence extends to a
simplicial ($1$-Lipschitz) map
$\psi:\operatorname{\mathcal{A}}(\Sigma,\Gamma)\to\operatorname{\mathcal{G}}(\Omega)$.

We show that $\psi$ is a quasi-isometric embedding by constructing a coarse
Lipschitz retraction
$\pi:\operatorname{\mathcal{G}}(\Omega)\to\operatorname{\mathcal{A}}(\Sigma,\Gamma)$.
For a grand arc $w\in\operatorname{\mathcal{G}}(\Omega)$, fix a representative
$\omega$ that is geodesic in $\Sigma$. Let $\omega^{\pm}$ denote the first and
last intersections of $\omega$ with $\Sigma$ and let $\hat{\omega}$ denote the
shortest path between $\omega^{-}$ and $\omega^{+}$ in
$(\omega\cap\Sigma)\cup\partial\Sigma$. Since $\omega$ converges to maximal
ends of distinct type, $\omega^{\pm}$ lie on boundary components with distinct
colors: isotoping $\hat{\omega}$ into the interior of $\Sigma$ rel
$\omega^{\pm}$, $\hat{\omega}$ is $\Gamma$-allowed and we define
$\pi:w\mapsto[\hat{\omega}]$. From the constructions of $\psi,\pi$, it is
immediate that $\pi\psi$ is identity on
$\operatorname{\mathcal{A}}(\Sigma,\Gamma)$. We verify that $\pi$ is
Lipschitz. Let $w,w^{\prime}\in\operatorname{\mathcal{G}}(\Omega)$ be disjoint
grand arcs and let $\pi(w)=[\hat{\omega}]$ and
$\pi(w^{\prime})=[\hat{\omega}^{\prime}]$ as above. Since $\hat{\omega}$ is
constructed as a shortest path, it contains at most
$|\pi_{0}(\partial\Sigma)|-1$ segments that are components of
$\omega\cap\Sigma$. Each of these segments intersects $\hat{\omega}^{\prime}$
at most twice and in subsegments of $\hat{\omega}^{\prime}$ parallel to
$\partial\Sigma$, and the same statement holds exchanging $\hat{\omega}$ and
$\hat{\omega}^{\prime}$. Thus $i(\hat{\omega},\hat{\omega}^{\prime})\leq
4|\pi_{0}(\partial\Sigma)|-4$. Finally, since
$d([\hat{\omega}],[\hat{\omega}^{\prime}])\leq
i(\hat{\omega},\hat{\omega}^{\prime})+1$ by [Kop23a, Prop. 2.6], we obtain
that $\pi$ is $(4|\pi_{0}(\partial\Sigma)|-3)$-Lipschitz. ∎

Witnesses for $\operatorname{\mathcal{G}}(\Sigma)$ exist [BNV22, Lem. 2.7] and
their enlargements are likewise witnesses, hence there exist fully separating
witnesses $\Sigma\subset\Omega$ of arbitrarily large complexity. If
$|\operatorname{\mathcal{S}}(\Omega)|>2$ and $\Gamma$ is chosen as in Lemma
3.2, then $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is $\delta$-hyperbolic
by Theorem 1.4 and by Lemma 3.2 and Theorem 1.1
$\operatorname{asdim}\mathcal{G}(\Omega)>n$ for all $n$.

Suppose instead that $|\operatorname{\mathcal{S}}(\Omega)|=2$. If $\Omega$ has
infinite genus or infinitely many non-maximal ends, then there exists an
infinite collection of pairwise-disjoint annular witnesses separating the two
maximal end classes $\\{e,f\\}=\operatorname{\mathcal{S}}(\Omega)$. Choosing
finite subcollections defines quasi-flats of arbitrarily large dimension [Sch,
Exercise 3.13], hence again
$\operatorname{asdim}\operatorname{\mathcal{G}}(\Omega)=\infty$.
Alternatively, $\operatorname{\mathcal{G}}(\Omega)$ contains an asymphoric
hierarhically hyperbolic space of arbitrarily high rank, hence has infinite
asymptotic dimension [Kop23, Prop. 1.11].

Finally, suppose that $|\operatorname{\mathcal{S}}(\Omega)|=2$ and $\Omega$
has finite genus and finitely many non-maximal ends. $\Omega$ must have at
least one infinite equivalence class $e$ of maximal ends; let $f$ be the other
maximal end class. For any $n$, choose a $(n+1)$-holed sphere
$\Sigma\subset\Omega$ with $n$ boundary components partitioning $e$ and the
remaining component separating $e$ from $f$ and any genus or non-maximal ends.
Then $\Sigma$ is a fully separating witness for
$\operatorname{\mathcal{G}}(\Omega)$ and $\Gamma$, defined as in Lemma 3.2, is
a $n$-pointed star. $\operatorname{\mathcal{A}}(\Sigma,\Gamma)$ is
$\delta$-hyperbolic by Theorem 1.4: we conclude by Lemma 3.2 and Theorem 1.1.
$/\\!\\!/$

##  4\. Acknowledgements

The author would like to thank Mladen Bestvina for his support and advice, and
George Shaji for numerous helpful discussions. The author was supported by NSF
award no. 2304774.

## References

  * [AV20] Javier Aramayona and Nicholas G. Vlamis  “Big mapping class groups: an overview”, 2020  arXiv:2003.07950 [math.GT]
  * [BH99] Martin R. Bridson and André Haefliger  “Metric Spaces of Non-Positive Curvature”  Heidelberg: Springer Berlin, 1999
  * [BL08] Sergei Buyalo and Nina Lebedeva  “Dimensions of locally and asymptotically self-similar spaces”  In _St. Petersburg Math. J._ 19, 2008, pp. 45–65
  * [BNV22] Assaf Bar-Natan and Yvon Verberne  “The grand arc graph”, 2022  arXiv: https://doi.org/10.48550/arXiv.2110.14761
  * [BS00] Mario Bonk and Oded Schramm  “Embeddings of Gromov Hyperbolic Spaces”  In _Geometric and Functional Analysis_ 10, 2000, pp. 243–284  URL: https://api.semanticscholar.org/CorpusID:18559672
  * [Buy06] Sergei Buyalo  “Asymptotic dimension of a hyperbolic space and capacity dimension of its boundary at infinity”  In _St. Petersberg Math. J._ 17, 2006, pp. 267–283
  * [Cal09] Danny Calegari  “Big mapping class groups and dynamics”, Blog post, https://lamington.wordpress.com/2009/06/22/big-mapping-class-groups-and-dynamics, 2009
  * [CPV21] Yassin Chandran, Priyam Patel and Nicholas G. Vlamis  “Infinite type surfaces and mapping class groups: Open problems”, http://qcpages.qc.cuny.edu/~nvlamis/Papers/InfTypeProblems.pdf, 2021
  * [DK18] C. Druţu and M. Kapovich  “Geometric Group Theory”, Colloquium Publications  American Mathematical Society, 2018
  * [DT17] Spencer Dowdall and Samuel J. Taylor  “The co-surface graph and the geometry of hyperbolic free group extensions”  In _Journal of Topology_ 10.2, 2017, pp. 447–482  DOI: https://doi.org/10.1112/topo.12013
  * [FGM21] Federica Fanoni, Tyrone Ghaswala and Alan McLeay  “Homeomorphic subsurfaces and the omnipresent arcs”  In _Annales Henri Lebesgue_ 4 ÉNS Rennes, 2021, pp. 1565–1593  DOI: https://doi.org/10.5802/ahl.110
  * [Gab14] David Gabai  “On the topology of ending lamination space”  In _Geometry & Topology_ 18.5 MSP, 2014, pp. 2683 –2745  DOI: 10.2140/gt.2014.18.2683
  * [Has22] Yo Hasegawa  “Gromov Boundaries of Non-proper Hyperbolic Geodesic Spaces”  In _Tokyo Journal of Mathematics_ 45.2 Publication Committee for the Tokyo Journal of Mathematics, 2022, pp. 319–331  DOI: 10.3836/tjm/1502179357
  * [KB02] Ilya Kapovich and Nadia Benakli  “Boundaries of hyperbolic groups”, 2002  arXiv:math/0202286 [math.GR]
  * [Kop23] Michael C. Kopreski  “Multiarc and curve graphs are hierarchically hyperbolic”, 2023  arXiv:2311.04356 [math.GT]
  * [Kop23a] Michael C. Kopreski  “Prescribed Arc Graphs”, 2023  arXiv:2305.05316 [math.GT]
  * [MR20] Kathryn Mann and Kasra Rafi  “Large scale geometry of big mapping class groups”, 2020  arXiv: https://doi.org/10.48550/arXiv.1912.10914
  * [Nob30] G. Nobeling  “Uber eine n-dimensionale Universalmenge im $\mathbb{R}_{2n+1}$”  In _Mathematische Annalen_ 104, 1930, pp. 71–80
  * [Po15] Witsarut Pho-on  “Infinite Unicorn Paths and Gromov Boundaries”  In _Groups, Geometry, and Dynamics_ 11, 2015, pp. 353–370
  * [Ric63] I. Richards  “On the classification of noncompact surfaces”  In _Transactions of the American Mathematical Society_ 106, 1963, pp. 259–269
  * [Ros14] Christian Rosendal  “Large scale geometry of metrisable groups”, 2014  arXiv:1403.3106 [math.GR]
  * [Sch] Saul Schleimer  “Notes on the complex of curves”, http://homepages.warwick.ac.uk/~masgar/Maths/notes.pdf


# Repeated Sums and Binomial Coefficients

Roudy El Haddad
Université La Sagesse, Faculté de génie, Polytech
<EMAIL_ADDRESS>
###### Abstract

Binomial coefficients have been used for centuries in a variety of fields and
have accumulated numerous definitions. In this paper, we introduce a new way
of defining binomial coefficients as repeated sums of ones. A multitude of
binomial coefficient identities will be shown in order to prove this
definition. Using this new definition, we simplify some particular sums such
as the repeated Harmonic sum and the repeated Binomial-Harmonic sum. We derive
formulae for simplifying general repeated sums as well as a variant containing
binomial coefficients. Additionally, we study the $m$-th difference of a
sequence and show how sequences whose $m$-th difference is constant can be
related to binomial coefficients.

######  Keywords.

Binomial Coefficients, Binomial Sums, $m$-th Difference, Repeated Sequences,
Repeated Sums, Harmonic Sums, Binomial-Harmonic Sums.
MSC 2020: 05A10

##  1 Introduction

The author is interested in the study of the various types of repetitive sums,
that is, developing formulae and identities to better understand these types
of sums as well as to simplify the way we work with them. Previously, the
author has presented a set of useful formulae for two types of repetitive
sums: recurrent sums [1] and multiple sums [2]. In this article, we aim to do
the same for a third type of repetitive sums: the repeated sums. For the first
two types, partitions were key for developing a reduction theorem to simplify
these sums. For this type of sums, binomial coefficients are key. Hence, we
first need to develop a set of binomial coefficient identities as well as we
need to introduce a new definition for binomial coefficients. Binomial
coefficients appear in many distinct fields of mathematics (including
probability, combinatorics, analysis, etc.) and, therefore, they can be
defined in many different ways. In 1654, in his article “Traité du triangle
arithmétique” [3, 4], Pascal presented what is now known as Pascal’s triangle
and which constituted the first definition of binomial coefficients. The
binomial coefficient $\binom{n}{k}$ represents the element in the $k$-th
column and $n$-th row of Pascal’s triangle. They can also be defined by the
recurrent relation used to construct Pascal’s triangle which we will call the
Pascal’s triangle identity and which states that
$\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}$. The notation $\binom{n}{k}$
was introduced by Euler in the 18th century. Alternatively, binomial
coefficients can be denoted as $C_{n}^{k}$. This second notation, introduced
in the 19th century, is mostly used in combinatorics where binomial
coefficients are defined as the number of ways of choosing an unordered subset
of $k$ elements from a set of $n$ elements. Binomial coefficients are also
intensively used in probability calculation for binomial distributions. Let X
be a random variable, let $n$ be the number of experiments, let $k$ be an
integer, and let $p$ represent the probability of success in a single
experiment, the binomial distribution formula is given by
$P(X=k)=C_{n}^{k}p^{k}(1-p)^{n-k}$. Additional definitions of these
coefficients appear in analysis and calculus. First, they appear in the
binomial theorem as well as in the generalized binomial theorem presented by
Newton [5, 6], $(u+v)^{n}=\sum_{k=0}^{n}{\binom{n}{k}u^{k}v^{n-k}}$ and
$(u_{1}+\cdots+u_{m})^{n}=\sum_{k_{1}+\cdots+k_{m}=n}{\binom{n}{k_{m}}\binom{n-k_{m}}{k_{m-1}}\cdots\binom{n-k_{m}-\cdots-
k_{1}}{k_{2}}u_{1}^{k_{1}}u_{2}^{k_{2}}\cdots u_{m}^{k_{m}}}$. From the simple
case of the theorem, the binomial coefficient $\binom{n}{k}$ can be defined as
the coefficient of $u^{k}v^{n-k}$ in the expansion of $(u+v)^{n}$. Likewise,
$\binom{n}{k}$ appears in Leibniz’s formula for the $n$-th derivative of a
product [7, 8, 9], $(uv)^{(n)}=\sum_{k=0}^{n}{\binom{n}{k}u^{(k)}v^{(n-k)}}$.
Hence, Leibniz’s rule defines the binomial coefficient $\binom{n}{k}$ as the
coefficient of $u^{(k)}v^{(n-k)}$ in the expansion of $(uv)^{(n)}$. These
coefficients even appear in number theory: In [1, 2], binomial coefficients
are defined as a sum over partitions of an integer $m$ in several ways. And,
finally, binomial coefficients can be defined in terms of factorials:
$\binom{n}{k}=\frac{n!}{k!(n-k)!}$.

######  Remark.

Tables of binomial coefficients can be found in [10, 11, 12].

In this study, we propose a new definition: we define binomial coefficients as
repeated sums (Section 3). This definition is key for the determination of a
reduction formula for repeated sums which allows the reduction of such sums
into simple non-repetitive sums. In Section 3, we also present formulas for
the $m$-th difference of a sequence as well as we show the link between
sequences with a constant $m$-th difference and binomial coefficients. In
Section 2, we present some formulae for binomial sums and repeated binomial
sums which are needed to prove the definition. In Section 4, this new
definition is used to derive results related to the harmonic sum such as an
expression for the repeated harmonic sum in terms of the simple harmonic sum.
We also derive expressions for a modified version of the repeated harmonic sum
which we will refer to as the repeated binomial-harmonic sum. Then, in Section
5, this definition as well as the results derived will be utilized to develop
a reduction formula for the repeated sum of any sequence $a_{N}$. A similar
expression is also derived for a modified version of repeated sums which we
will refer to as the repeated “binomial-sequence” sum.

##  2 Sums of binomial coefficients

In this section, we prove some formulas related to the sums and repeated sums
of binomial coefficients. These formulas are needed in order to produce the
proposed definition for binomial coefficients. They are also essential for
developing the harmonic sum identities later on. Furthermore, they are crucial
for developing an expression for repeated sums in terms of single sums.

###  2.1 Binomial sum

We begin by determining a formula for the sum of binomial coefficients.

######  Theorem 2.1.

For any $k,q,n\in\mathbb{N}$ such that $n\geq q$, we have

$\sum_{i=q}^{n}{\binom{i}{k}}=\binom{n+1}{k+1}-\binom{q}{k+1}.$

######  Remark.

The coefficients of the form $\binom{n}{k}$ where $n<k$, being undefined
according to the factorial definition, are supposed zero. Hence, if $q<k$, we
can start the sum at $k$.

###### Proof.

1\. Base case: verify true for $n=q$.
Using Pascal’s Triangle identity,

$\sum_{i=q}^{q}{\binom{i}{k}}=\binom{q}{k}=\binom{q+1}{k+1}-\binom{q}{k+1}.$

2\. Induction hypothesis: assume the statement is true until $n$.

$\sum_{i=q}^{n}{\binom{i}{k}}=\binom{n+1}{k+1}-\binom{q}{k+1}.$

3\. Induction step: we will show that this statement is true for $(n+1)$.
We have to show the following statement to be true:

$\sum_{i=q}^{n+1}{\binom{i}{k}}=\binom{n+2}{k+1}-\binom{q}{k+1}.$

$\sum_{i=q}^{n+1}{\binom{i}{k}}=\binom{n+1}{k}+\sum_{i=q}^{n}{\binom{i}{k}}=\binom{n+1}{k}+\binom{n+1}{k+1}-\binom{q}{k+1}.$

From Pascal’s Triangle identity, we get the case for $(n+1)$. ∎

######  Corollary 2.1.

For $q=0$ or $q=k$, Theorem 2.1 becomes

$\sum_{i=0}^{n}{\binom{i}{k}}=\sum_{i=k}^{n}{\binom{i}{k}}=\binom{n+1}{k+1}.$

######  Corollary 2.2.

The shifted binomial sum can be calculated as follows

$\sum_{i=m}^{n+m}{\binom{i}{k}}=\sum_{i=0}^{n}{\binom{i+m}{k}}=\binom{n+m+1}{k+1}-\binom{m}{k+1}.$

###### Proof.

Applying Theorem 2.1 for $q=m$ and replacing $n$ by $n+m$, we obtain the
corollary. ∎

###  2.2 Repeated binomial sum

Using Theorem 2.1, we develop a formula for the repeated sum of binomial
coefficients.

######  Theorem 2.2.

For any $m\in\mathbb{N^{*}}$ and for any $k,q,n\in\mathbb{N}$ such that $n\geq
q$, we have

$\begin{split}\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{\binom{N_{1}}{k}}}&=\binom{n+m}{k+m}-\sum_{j=1}^{m}{\binom{(q-1)+j}{k+j}\binom{(n-q)+(m-j)}{m-j}}\\\
&=\binom{n+m}{k+m}-\sum_{j=1}^{m}{\binom{(q-1)+j}{(q-1)-k}\binom{(n-q)+(m-j)}{n-q}}.\end{split}$

###### Proof.

1\. Base case: verify true for $m=1$.

$\binom{n+1}{k+1}-\sum_{j=1}^{1}{\binom{(q-1)+j}{k+j}\binom{(n-q)+(1-j)}{1-j}}=\binom{n+1}{k+1}-\binom{q}{k+1}.$

From Theorem 2.1, this case is proven.
2\. Induction hypothesis: assume the statement is true until $m$.

$\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{\binom{N_{1}}{k}}}=\binom{n+m}{k+m}-\sum_{j=1}^{m}{\binom{(q-1)+j}{k+j}\binom{(n-q)+(m-j)}{m-j}}.$

3\. Induction step: we will show that this statement is true for $(m+1)$.
We have to show the following statement to be true:

$\sum_{N_{m+1}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{\binom{N_{1}}{k}}}=\binom{n+m+1}{k+m+1}-\sum_{j=1}^{m+1}{\binom{(q-1)+j}{k+j}\binom{(n-q)+(m+1-j)}{m+1-j}}.$
$\begin{split}\sum_{N_{m+1}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{\binom{N_{1}}{k}}}&=\sum_{N_{m+1}=q}^{n}{\left(\sum_{N_{m}=q}^{N_{m+1}}{\cdots\sum_{N_{1}=q}^{N_{2}}{\binom{N_{1}}{k}}}\right)}\\\
&\leavevmode\resizebox{433.62pt}{}{$\displaystyle{=\sum_{N_{m+1}=q}^{n}{\binom{N_{m+1}+m}{k+m}}-\sum_{N_{m+1}=q}^{n}{\sum_{j=1}^{m}{\binom{(q-1)+j}{k+j}\binom{(N_{m+1}-q)+(m-j)}{m-j}}}}$}\\\
&\leavevmode\resizebox{433.62pt}{}{$\displaystyle{=\sum_{N_{m+1}=q}^{n}{\binom{N_{m+1}+m}{k+m}}-\sum_{j=1}^{m}{\sum_{N_{m+1}=q}^{n}{\binom{(q-1)+j}{k+j}\binom{(N_{m+1}-q)+(m-j)}{m-j}}}}$}\\\
&=\sum_{N_{m+1}=q+m}^{n+m}{\binom{N_{m+1}}{k+m}}-\sum_{j=1}^{m}{\binom{(q-1)+j}{k+j}\sum_{N_{m+1}=m-j}^{(n-q)+(m-j)}{\binom{N_{m+1}}{m-j}}}.\end{split}$

By applying Theorem 2.1,

$\begin{split}\sum_{N_{m+1}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{\binom{N_{1}}{k}}}=&\binom{n+m+1}{k+m+1}-\binom{q+m}{k+m+1}\\\
&-\sum_{j=1}^{m}{\binom{(q-1)+j}{k+j}\binom{(n-q)+(m+1-j)}{m+1-j}}.\end{split}$

Noticing that

$\sum_{j=m+1}^{m+1}{\binom{(q-1)+j}{k+j}\binom{(n-q)+(m+1-j)}{m+1-j}}=\binom{q+m}{k+m+1},$

hence, the case for $(n+1)$ is proven and the theorem is proven by induction.
∎

An important particular case of Theorem 2.2 is illustrated by the following
corollary. In fact, the formula for the repeated sum of binomial coefficients
is heavily simplified if the sums are started at $0$.

######  Corollary 2.3.

For any $m\in\mathbb{N^{*}}$ and for any $k,n\in\mathbb{N}$, we have that

$\sum_{N_{m}=0}^{n}{\cdots\sum_{N_{1}=0}^{N_{2}}{\binom{N_{1}}{k}}}=\binom{n+m}{k+m}.$

###### Proof.

From Theorem 2.2 for $q=0$,

$\sum_{N_{m}=0}^{n}{\cdots\sum_{N_{1}=0}^{N_{2}}{\binom{N_{1}}{k}}}=\binom{n+m}{k+m}-\sum_{j=1}^{m}{\binom{j-1}{k+j}\binom{n+(m-j)}{m-j}}.$

We can notice that because $k\geq 0$, then $k+j\geq j>j-1$, thus, $\forall
j\in\mathbb{N}$, $\binom{j-1}{k+j}=0$. Hence, we obtain the corollary. ∎

The formula for repeated sums of ones, which is needed to prove the new
definition for binomial coefficients, is another crucial particular case of
Theorem 2.2.

######  Corollary 2.4.

For any $m\in\mathbb{N^{*}}$ and for any $q,n\in\mathbb{N}$ such that $n\geq
q$, we have that

$\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{1}}=\binom{n-q+m}{m}.$

###### Proof.

$\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{1}}=\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{2}=q}^{N_{3}}{\sum_{N_{1}=0}^{N_{2}-q}{1}}}=\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{2}=0}^{N_{3}-q}{\sum_{N_{1}=0}^{N_{2}}{1}}}=\cdots=\sum_{N_{m}=0}^{n-q}{\cdots\sum_{N_{2}=0}^{N_{3}}{\sum_{N_{1}=0}^{N_{2}}{1}}}.$

From Corollary 2.3 for $k=0$, we obtain the corollary. ∎

The sum of a special product of binomial coefficients can also be derived from
Theorem 2.2.

######  Corollary 2.5.

For any $m\in\mathbb{N^{*}}$ and for any $q,n\in\mathbb{N}$ such that $n\geq
q$, we have that

$\begin{split}\sum_{j=1}^{m}{\binom{(q-1)+j}{j}\binom{(n-q)+(m-j)}{m-j}}&=\sum_{j=1}^{m}{\binom{(q-1)+j}{q-1}\binom{(n-q)+(m-j)}{n-q}}\\\
&=\binom{n+m}{m}-\binom{n-q+m}{m}.\end{split}$

###### Proof.

By applying Theorem 2.2 for $k=0$,

$\begin{split}\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{1}}&=\binom{n+m}{m}-\sum_{j=1}^{m}{\binom{(q-1)+j}{j}\binom{(n-q)+(m-j)}{m-j}}\\\
&=\binom{n+m}{m}-\sum_{j=1}^{m}{\binom{(q-1)+j}{q-1}\binom{(n-q)+(m-j)}{n-q}}.\end{split}$

By comparing with the expression given by Corollary 2.4, we get this
corollary. ∎

##  3 Binomial coefficients as repeated sums and repeated sequences

In this section, we use the formulas presented in the previous section in
order to introduce a new definition of binomial coefficients. First, we prove
that a binomial coefficient can be defined as a repeated sum of ‘1’s. Second,
we prove that a binomial coefficient can be defined as a repeated sequence.

###  3.1 Binomial coefficients as repeated sums of ones

In this section, we prove that binomial coefficients can be defined as
repeated sums of ones.
A repeated sum of ‘1’s can be expressed as a binomial coefficient as is shown
by Theorem 3.1.

######  Theorem 3.1.

A repeated sum of 1s corresponds to the following binomial coefficient,

$\sum_{N_{m}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{1}}=\binom{n+m-1}{m}.$
$\sum_{N_{m}=0}^{n}{\cdots\sum_{N_{1}=0}^{N_{2}}{1}}=\binom{n+m}{m}.$

###### Proof.

The first equality of this theorem is obtained by applying Corollary 2.4 for
$q=1$ and the second equality is obtained by applying Corollary 2.4 for $q=0$.
∎

######  Remark.

We can highlight the combinatorical nature of repeated sums of 1s as
$\binom{n-1+m}{m}$ represents the number of ways of choosing $m$ elements from
$n$ with replacement but without regard to order ([13] pp. 24-25).

A binomial coefficient can be defined as a repeated sum of 1s as shown by
Theorem 3.2.

######  Theorem 3.2.

A binomial coefficient corresponds to the following repeated sums of 1s,

$\binom{n}{k}=\sum_{N_{k}=1}^{n-k+1}{\cdots\sum_{N_{1}=1}^{N_{2}}{1}}=\sum_{N_{k}=0}^{n-k}{\cdots\sum_{N_{1}=0}^{N_{2}}{1}}.$

###### Proof.

The first part of this theorem is obtained by replacing $n$ by $n-k+1$ in the
first equation of Theorem 3.1. The second part is obtained by replacing $n$ by
$n-k$ in the second equation of Theorem 3.1. ∎

###  3.2 Binomial coefficients as repeated sequences

In this section, we will go through a series of lemmas in order to prove that
any binomial coefficient can be defined as a repeated sequence (defined
below). In order to do so, we will first prove that repeated sequences can be
explicitly expressed as a repeated sum of ones. Then, using the fact that any
repeated sum of ones can be defined as a binomial coefficient (as proven in
the previous section), we define these repeated sequences as binomial
coefficients.

####  3.2.1 Notation and definitions

######  Definition.

We define the first difference of a sequence $(x_{n})$, denoted by $\Delta
x_{n}$, as the difference between two consecutive terms of the sequence
$(x_{n})$:

$\Delta x_{n}=x_{n}-x_{n-1}.$

######  Definition.

Let $m\in\mathbb{N}$. We define the $m$-th difference of a sequence $(x_{n})$,
denoted by $\Delta^{m}x_{n}$, by the following recurrent relation:

$\begin{cases}\Delta^{m}x_{n}=\Delta^{m-1}x_{n}-\Delta^{m-1}x_{n-1}\\\ \forall
i\in\mathbb{Z},\Delta^{0}x_{i}=x_{i}.\end{cases}$

######  Definition.

We define a repeated sequence of degree $m$, denoted by
$\\{x_{n,m}\\}_{n=1}^{\infty}$, as a sequence whose $m$-th difference is a
constant $(\forall
i,j\in\mathbb{N}^{*},\,\,\Delta^{m}x_{i,m}=\Delta^{m}x_{j,m})$. $x_{n,m}$ is
the $n$-th term of this repeated sequence of order $m$.

######  Remark.

In order to keep the $m$-th difference always valid we define an extension of
the sequence such that $\forall i\leq 0,x_{i,m}=0$. However, the properties of
the sequence do not extend to this extension. Note that the theorems develop
in this section will only apply to repeated sequences which validate the
condition imposed by this extension.

######  Remark.

For a given order $m$ and a given $m$-th difference, the repeated sequence is
unique. The repeated sequence of order $m$ having
$\Delta^{m}x_{n,m}=\delta\in\mathbb{C}$ is denoted by
$\\{x_{n,m}^{(\delta)}\\}_{n=1}^{\infty}$.

######  Definition.

We define the unity repeated sequence, denoted by
$\\{\hat{x}_{n,m}\\}_{n=1}^{\infty}$, as the sequence whose $m$-th difference
is 1 $(\forall i\in\mathbb{N}^{*},\,\,\Delta^{m}\hat{x}_{i,m}=1)$.
$\hat{x}_{n,m}$ is the $n$-th term of the unity repeated sequence of order
$m$.

######  Example 3.1.

The unity repeated sequence of order $0$, $(\hat{x}_{n,0})$, is the following:

$\hat{x}_{1,0}=1,\,\,\hat{x}_{2,0}=1,\,\,\hat{x}_{3,0}=1,\cdots$

######  Example 3.2.

The unity repeated sequence of order $1$, $(\hat{x}_{n,1})$, is the following:

$\hat{x}_{1,1}=1,\,\,\hat{x}_{2,1}=2(=1+1),\,\,\hat{x}_{3,1}=3(=1+1+1),\cdots$

######  Example 3.3.

The unity repeated sequence of order $2$, $(\hat{x}_{n,2})$, is the following:

$\hat{x}_{1,2}=1,\,\,\hat{x}_{2,2}=3(=1+(1+1)),\,\,\hat{x}_{3,2}=6(=1+(1+1)+(1+1+1)),\cdots$

####  3.2.2 Expressions for the m-th difference of a sequence

In this section, using the recurrent definition of the $m$-th difference, we
develop an additional definition for the $m$-th difference of a sequence in
terms of a lower order difference of this sequence.

######  Theorem 3.3.

For any $m,n,p\in\mathbb{N}$ such that $p\leq m$ and for any sequence $x_{n}$,
we have that

$\Delta^{m}x_{n}=\sum_{j=0}^{p}{(-1)^{j}\binom{p}{j}\Delta^{m-p}x_{n-j}}.$

###### Proof.

1\. Base case: verify true for $m=0$.
Knowing that $0\leq p\leq m$ and $m=0$, hence, $p=0$.

$\sum_{j=0}^{0}{(-1)^{j}\binom{0}{j}\Delta^{0}x_{n-j}}=\Delta^{0}x_{n}.$

2\. Induction hypothesis: assume the statement is true until $m$.

$\Delta^{m}x_{n}=\sum_{j=0}^{p}{(-1)^{j}\binom{p}{j}\Delta^{m-p}x_{n-j}}.$

3\. Induction step: we will show that this statement is true for $(m+1)$.
We have to show the following statement to be true:

$\Delta^{m+1}x_{n}=\sum_{j=0}^{p}{(-1)^{j}\binom{p}{j}\Delta^{m-p+1}x_{n-j}}.$

Knowing that $\Delta^{m+1}x_{n}=\Delta^{m}x_{n}-\Delta^{m}x_{n-1}$ and
applying the induction hypothesis, we get

$\begin{split}\Delta^{m+1}x_{n}&=\sum_{j=0}^{p}{(-1)^{j}\binom{p}{j}\Delta^{m-p}x_{n-j}}-\sum_{j=0}^{p}{(-1)^{j}\binom{p}{j}\Delta^{m-p}x_{n-j-1}}\\\
&=\sum_{j=0}^{p}{(-1)^{j}\binom{p}{j}(\Delta^{m-p}x_{n-j}-\Delta^{m-p}x_{n-j-1})}\\\
&=\sum_{j=0}^{p}{(-1)^{j}\binom{p}{j}\Delta^{m-p+1}x_{n-j}}.\end{split}$

∎

######  Remark.

As we can see, the binomial coefficient $\binom{p}{j}$ can be defined as the
coefficient of $(-1)^{j}\Delta^{m-p}x_{n-j}$ in the expression of the $m$-th
difference of the sequence $(x_{n})$.

In particular, the $m$-th difference of a sequence can be expressed in terms
of its elements.

######  Corollary 3.1.

For $p=m$, Theorem 3.3 becomes

$\Delta^{m}x_{n}=\sum_{j=0}^{m}{(-1)^{j}\binom{m}{j}x_{n-j}}.$

####  3.2.3 Explicit expression for a repeated sequence as a repeated sum of
ones

We are interested in the calculation of the sum of such sequences as well as
in the definition of such sequences in terms of binomial coefficients. To do
so, in this section, we convert the definition of a repeated sequence of
degree $m$ which is in terms of the $m$-th difference into a definition in
terms of a repeated sum of ones. Then, in the later sections, the theorems for
repeated sums of ones are used to prove the proposed definition as well as to
develop a formula for the repeated sum of a repeated sequence of degree $m$.

We start by proving the following set of lemmas.

######  Lemma 3.1.

For repeated sequences of any order $k$, the difference of any order $m$ is
zero for all terms with an index $i\leq 0$,

$\forall k\in\mathbb{N},\forall m\in\mathbb{N},\forall i\leq
0,\Delta^{m}x_{i,k}^{(\delta)}=0.$

###### Proof.

1\. Base case: verify true for $m=0$.
By definition, $x_{i,k}^{(\delta)}=0$ for $i\leq 0$. Hence,

$\forall k\in\mathbb{N},\forall i\leq
0,\Delta^{0}x_{i,k}^{(\delta)}=x_{i,k}^{(\delta)}=0.$

2\. Induction hypothesis: assume the statement is true until $m$.

$\forall k\in\mathbb{N},\forall i\leq 0,\Delta^{m}x_{i,k}^{(\delta)}=0.$

3\. Induction step: we will show that this statement is true for $(m+1)$.
We have to show the following statement to be true:

$\forall k\in\mathbb{N},\forall i\leq 0,\Delta^{m+1}x_{i,k}^{(\delta)}=0.$

By definition,
$\Delta^{m+1}x_{i,k}^{(\delta)}=\Delta^{m}x_{i,k}^{(\delta)}-\Delta^{m}x_{i-1,k}^{(\delta)}$.
From the induction hypothesis, we get that $\Delta^{m}x_{i,k}^{(\delta)}=0$
and $\Delta^{m}x_{i-1,k}^{(\delta)}=0$ because, respectively, $i\leq 0$ and
$i-1\leq-1\leq 0$.
Hence, $\Delta^{m+1}x_{i,k}^{(\delta)}=0$. ∎

######  Lemma 3.2.

For repeated sequences of any order $k$, the difference of any order $m$ of
the first term of the sequence is equal to this initial term,

$\forall k\in\mathbb{N},\forall
m\in\mathbb{N},\Delta^{m}x_{1,k}^{(\delta)}=x_{1,k}^{(\delta)}.$

###### Proof.

1\. Base case: verify true for $m=0$.

$\forall k\in\mathbb{N},\Delta^{0}x_{1,k}^{(\delta)}=x_{1,k}^{(\delta)}.$

2\. Induction hypothesis: assume the statement is true until $m$.

$\forall k\in\mathbb{N},\Delta^{m}x_{1,k}^{(\delta)}=x_{1,k}^{(\delta)}.$

3\. Induction step: we will show that this statement is true for $(m+1)$.
We have to show the following statement to be true:

$\forall k\in\mathbb{N},\Delta^{m+1}x_{1,k}^{(\delta)}=x_{1,k}^{(\delta)}.$

By definition,
$\Delta^{m+1}x_{1,k}^{(\delta)}=\Delta^{m}x_{1,k}^{(\delta)}-\Delta^{m}x_{0,k}^{(\delta)}$.
From Lemma 3.1, $\Delta^{m}x_{0,k}^{(\delta)}=0$. Hence,
$\Delta^{m+1}x_{1,k}^{(\delta)}=\Delta^{m}x_{1,k}^{(\delta)}$.
By applying the induction hypothesis, we get
$\Delta^{m+1}x_{1,k}^{(\delta)}=x_{1,k}^{(\delta)}$. ∎

######  Remark.

From Lemma 3.2 for $k=m$, we see that the first term of a repeated sequence of
order $m$ is equal to its $m$-th difference
($x_{1,m}^{(\delta)}=\Delta^{m}x_{1,m}^{(\delta)}=\delta$).

######  Lemma 3.3.

For any $m,k,n\in\mathbb{N}$ where $n\geq 1$, we have that

$\sum_{N=1}^{n}{\Delta^{m}x_{N,k}^{(\delta)}}=\Delta^{m-1}x_{n,k}^{(\delta)}.$

###### Proof.

1\. Base case: verify true for $n=1$.
From Lemma 3.2,
$\Delta^{m}x_{1,k}^{(\delta)}=\Delta^{m-1}x_{1,k}^{(\delta)}=x_{1,k}^{(\delta)}$,

$\sum_{N=1}^{1}{\Delta^{m}x_{N,k}^{(\delta)}}=\Delta^{m}x_{1,k}^{(\delta)}=\Delta^{m-1}x_{1,k}^{(\delta)}.$

2\. Induction hypothesis: assume the statement is true until $n$.

$\sum_{N=1}^{n}{\Delta^{m}x_{N,k}^{(\delta)}}=\Delta^{m-1}x_{n,k}^{(\delta)}.$

3\. Induction step: we will show that this statement is true for $(n+1)$.
We have to show the following statement to be true:

$\sum_{N=1}^{n+1}{\Delta^{m}x_{N,k}^{(\delta)}}=\Delta^{m-1}x_{n+1,k}^{(\delta)}.$
$\sum_{N=1}^{n+1}{\Delta^{m}x_{N,k}^{(\delta)}}=\sum_{N=1}^{n}{\Delta^{m}x_{N,k}^{(\delta)}}+\Delta^{m}x_{n+1,k}^{(\delta)}.$

Applying the induction hypothesis to the first term and using the definition
of the second term,

$\sum_{N=1}^{n+1}{\Delta^{m}x_{N,k}^{(\delta)}}=\Delta^{m-1}x_{n,k}^{(\delta)}+\left[\Delta^{m-1}x_{n+1,k}^{(\delta)}-\Delta^{m-1}x_{n,k}^{(\delta)}\right]=\Delta^{m-1}x_{n+1,k}^{(\delta)}.$

∎

######  Lemma 3.4.

For any $m,k,j,n\in\mathbb{N}$ such that $n\geq 1$ and $1\leq j\leq m$, we
have that

$\sum_{N_{j}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{\Delta^{m}x_{N_{1},k}^{(\delta)}}}}=\Delta^{m-j}x_{n,k}^{(\delta)}.$

###### Proof.

1\. Base case: verify true for $j=1$.
Proven true in Lemma 3.3.
2\. Induction hypothesis: assume the statement is true until $j$.

$\sum_{N_{j}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\Delta^{m}x_{N_{1},k}^{(\delta)}}}=\Delta^{m-j}x_{n,k}^{(\delta)}.$

3\. Induction step: we will show that this statement is true for $(j+1)$.
We have to show the following statement to be true:

$\sum_{N_{j+1}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\Delta^{m}x_{N_{1},k}^{(\delta)}}}=\Delta^{m-j-1}x_{n,k}^{(\delta)}.$

Using the induction hypothesis,

$\sum_{N_{j+1}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\Delta^{m}x_{N_{1},k}^{(\delta)}}}=\sum_{N_{j+1}=1}^{n}{\sum_{N_{j}=1}^{N_{j+1}}{\cdots\sum_{N_{1}=1}^{N_{2}}{\Delta^{m}x_{N_{1},k}^{(\delta)}}}}=\sum_{N_{j+1}=1}^{n}{\Delta^{m-j}x_{N_{j+1},k}^{(\delta)}}.$

Applying Lemma 3.3, we get the lemma. ∎

A particular case of Lemma 3.4 for $j=k=m$ is as follows. This theorem relates
the repeated sequence to the repeated sum of ones.

######  Theorem 3.4.

Any element of the $m$-th degree repeated sequence can be defined as an $m$-th
order repeated sum of ones,

$x_{n,m}^{(\delta)}=\Delta^{m}x_{n,m}^{(\delta)}\sum_{N_{m}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{1}}}=\delta\sum_{N_{m}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{1}}}.$

###### Proof.

A particular case of Lemma 3.4 for $j=k=m$ is as follows,

$\sum_{N_{m}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{\Delta^{m}x_{N_{1},m}^{(\delta)}}}}=x_{n,m}^{(\delta)}.$

By definition of a repeated sequence of degree $m$,
$\Delta^{m}x_{n,m}^{(\delta)}$ is a constant. Hence, we can take it out of the
summation. Doing so gives the desired theorem. ∎

For repeated unity sequences, Theorem 3.4 shows that these sequences are equal
to repeated sums of ones.

######  Corollary 3.2.

Any element of the $m$-th degree unity repeated sequence can be defined as an
$m$-th order repeated sum of ones,

$\hat{x}_{n,m}=\sum_{N_{m}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{1}}}.$

###### Proof.

Knowing that $\Delta^{m}\hat{x}_{n,m}=1$, this corollary is a direct
consequence of Theorem 3.4. ∎

####  3.2.4 Explicit expression for a repeated sequence as a binomial
coefficient

We now prove that repeated sequences can be defined as binomial coefficients.

######  Theorem 3.5.

For any $m,n\in\mathbb{N}$ where $n\geq 1$, we have that

$x_{n,m}^{(\delta)}=\Delta^{m}x_{n,m}^{(\delta)}\binom{n+m-1}{m}=\delta\binom{n+m-1}{m}.$

###### Proof.

By applying Corollary 2.3 to Theorem 3.4, we obtain the theorem. ∎

######  Corollary 3.3.

For any $m,n\in\mathbb{N}$ where $n\geq 1$, we have that

$\hat{x}_{n,m}=\binom{n+m-1}{m}.$

####  3.2.5 Sum of repeated sequences

Now that the needed expressions for repeated sequences were developed, one can
proceed to develop formulae for the sum of the terms of such sequences.

######  Theorem 3.6.

For any $k\in\mathbb{N^{*}}$ and for any $m,n\in\mathbb{N}$ where $n\geq 1$,
we have that

$\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{x_{N_{1},m}^{(\delta)}}}=\Delta^{m}x_{n,m}^{(\delta)}\sum_{N_{k+m}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{1}}=\Delta^{m}x_{n,m}^{(\delta)}\binom{n+m+k-1}{m+k}=x_{n,m+k}^{(\delta)}.$

###### Proof.

Applying Theorem 3.4, we get

$\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{x_{N_{1},m}^{(\delta)}}}=\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\sum_{j_{m}=1}^{N_{1}}{\cdots\sum_{j_{2}=1}^{j_{3}}{\sum_{j_{1}=1}^{j_{2}}{\Delta^{m}x_{N_{1},m}^{(\delta)}}}}}}.$

Knowing that $\forall
i,j\in\mathbb{N}^{*},\,\,\,\,\Delta^{m}x_{i,m}^{(\delta)}=\Delta^{m}x_{j,m}^{(\delta)}$,
hence, $\Delta^{m}x_{N_{1},m}^{(\delta)}=\Delta^{m}x_{n,m}^{(\delta)}$.

$\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{x_{N_{1},m}^{(\delta)}}}=\Delta^{m}x_{n,m}^{(\delta)}\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\sum_{j_{m}=1}^{N_{1}}{\cdots\sum_{j_{2}=1}^{j_{3}}{\sum_{j_{1}=1}^{j_{2}}{1}}}}}=\Delta^{m}x_{n,m}^{(\delta)}\sum_{N_{k+m}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{1}}.$

The first equality is proven. The second equality is obtained by applying
Theorem 2.1.
Knowing that
$\Delta^{m+k}x_{n,m+k}^{(\delta)}=\Delta^{m}x_{n,m}^{(\delta)}=\delta$, we
apply Theorem 3.4 to get

$x_{n,m+k}^{(\delta)}=\Delta^{m}x_{n,m+k}^{(\delta)}\sum_{N_{m+k}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{1}}}=\Delta^{m}x_{n,m}^{(\delta)}\sum_{N_{m+k}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{1}}}.$

This completes the proof of the third equality. ∎

######  Corollary 3.4.

For any $k\in\mathbb{N^{*}}$ and for any $m,n\in\mathbb{N}$ where $n\geq 1$,
we have that

$\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\hat{x}_{N_{1},m}}}=\sum_{N_{k+m}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{1}}=\binom{n+m+k-1}{m+k}=\hat{x}_{n,m+k}.$

###### Proof.

Applying Theorem 3.6 and noting that $\Delta^{m}\hat{x}_{n,m}=1$, we obtain
this corollary. ∎

######  Example 3.4.

The sequence $(\hat{x}_{n,1})$ is a sequence of terms where the difference of
two consecutive terms is 1: $1,2,3,4,5,\ldots$ . Using Corollary 3.4, we
calculate the repeated sum of order $3$ of its first $10$ terms as follows:

$\sum_{N_{3}=1}^{10}{\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{\hat{x}_{N_{1},1}}}}=\binom{10+1+3-1}{1+3}=\binom{13}{4}=715.$

######  Example 3.5.

The sequence $(\hat{x}_{n,2})$ is a sequence of terms where the difference of
two consecutive terms is increasing by 1: $1,3,6,10,15,\ldots$ . Using
Corollary 3.4, we calculate the repeated sum of order $3$ of its first $10$
terms as follows:

$\sum_{N_{3}=1}^{10}{\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{\hat{x}_{N_{1},2}}}}=\binom{10+2+3-1}{2+3}=\binom{14}{5}=2002.$

##  4 Reduction of Binomial-Harmonic sums

The harmonic sum has been studied independently by Oresme [14], Mengoli [15],
Johann Bernoulli [16], Jacob Bernoulli [17, 18], and most importantly by
Euler. A particularly interesting variant of this sum is that combining
binomial coefficients with harmonic sums. We will refer to such sums as
binomial-harmonic sums. In this section, we develop various formulas for the
reduction and calculation of such sums. We also present a formula relating the
repeated harmonic sum to the shifted harmonic sum.

###  4.1 Binomial-Harmonic sum

We begin by proving the following reduction formula to simplify Binomial-
Harmonic sums.

######  Theorem 4.1.

For any $m,p,n\in\mathbb{N}$ such that $n\geq p$, we have that

$\sum_{N=p}^{n}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}=\binom{n+m+1}{m+1}\sum_{i=2+m}^{n+m+1}{\frac{1}{i}}-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}.$

###### Proof.

1\. Base case: verify true for $n=p$.

$\begin{split}&\binom{p+m+1}{m+1}\sum_{i=2+m}^{p+m+1}{\frac{1}{i}}-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}\\\
&\,\,\,\,=\binom{p+m+1}{m+1}\frac{1}{p+m+1}+\left[\binom{p+m+1}{m+1}-\binom{p+m}{m+1}\right]\sum_{i=2+m}^{p+m}{\frac{1}{i}}.\end{split}$

From the Pascal’s Triangle identity,
$\binom{p+m+1}{m+1}-\binom{p+m}{m+1}=\binom{p+m}{m}$. In addiction,

$\binom{p+m+1}{m+1}\frac{1}{p+m+1}=\binom{p+m}{m}\frac{1}{m+1}.$

Hence, substituting back, we get

$\binom{p+m+1}{m+1}\sum_{i=2+m}^{p+m+1}{\frac{1}{i}}-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}=\binom{p+m}{m}\sum_{i=1+m}^{p+m}{\frac{1}{i}}=\sum_{N=p}^{p}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}.$

2\. Induction hypothesis: assume the statement is true until $n$.

$\sum_{N=p}^{n}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}=\binom{n+m+1}{m+1}\sum_{i=2+m}^{n+m+1}{\frac{1}{i}}-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}.$

3\. Induction step: we will show that this statement is true for $(n+1)$.
We have to show the following statement to be true:

$\sum_{N=p}^{n+1}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}=\binom{n+m+2}{m+1}\sum_{i=2+m}^{n+m+2}{\frac{1}{i}}-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}.$
$\sum_{N=p}^{n+1}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}=\sum_{N=p}^{n}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}+\binom{n+m+1}{m}\sum_{i=1+m}^{n+m+1}{\frac{1}{i}}.$

From the induction hypothesis,

$\begin{split}\sum_{N=p}^{n+1}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}&=\binom{n+m+1}{m+1}\sum_{i=2+m}^{n+m+1}{\frac{1}{i}}-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}+\binom{n+m+1}{m}\sum_{i=1+m}^{n+m+1}{\frac{1}{i}}\\\
&=\left[\binom{n+m+1}{m+1}+\binom{n+m+1}{m}\right]\sum_{i=2+m}^{n+m+1}{\frac{1}{i}}+\binom{n+m+1}{m}\frac{1}{m+1}\\\
&\,\,\,\,\,\,-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}.\end{split}$

From the Pascal’s Triangle identity,
$\binom{n+m+1}{m+1}+\binom{n+m+1}{m}=\binom{n+m+2}{m+1}$. In addition,

$\begin{split}\leavevmode\resizebox{433.62pt}{}{$\displaystyle{\binom{n+m+1}{m}\frac{1}{m+1}=\frac{(n+m+1)!}{m!(n+1)!}\frac{1}{m+1}=\frac{(n+m+2)!}{(m+1)!(n+1)!}\frac{1}{n+m+2}=\binom{n+m+2}{m+1}\frac{1}{n+m+2}.}$}\end{split}$

Hence,

$\begin{split}\sum_{N=p}^{n+1}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}&=\binom{n+m+2}{m+1}\sum_{i=2+m}^{n+m+2}{\frac{1}{i}}-\binom{p+m}{m+1}\sum_{i=2+m}^{p+m}{\frac{1}{i}}.\end{split}$

∎

######  Corollary 4.1.

For $p=1$, Theorem 4.1 becomes

$\sum_{N=1}^{n}{\binom{N+m}{m}\sum_{i=1+m}^{N+m}{\frac{1}{i}}}=\binom{n+m+1}{m+1}\sum_{i=2+m}^{n+m+1}{\frac{1}{i}}.$

###  4.2 Repeated Binomial-Harmonic sum

Now we generalize Theorem 4.1 and develop a formula for simplifying repeated
Binomial-Harmonic sums.

######  Theorem 4.2.

For any $k\in\mathbb{N^{*}}$ and for any $m,p,n\in\mathbb{N}$ such that $n\geq
p$, we have that

$\begin{split}&\sum_{N_{k}=p}^{n}{\cdots\sum_{N_{1}=p}^{N_{2}}{\left[\binom{N_{1}+m}{m}\sum_{i=1+m}^{N_{1}+m}{\frac{1}{i}}\right]}}\\\
&\,\,\,\,=\binom{n+m+k}{m+k}\sum_{i=1+m+k}^{n+m+k}{\frac{1}{i}}-\sum_{j=0}^{k-1}{\binom{n-p+j}{j}\binom{p-1+m+k-j}{m+k-j}\sum_{i=1+m+k-j}^{p-1+m+k-j}{\frac{1}{i}}}.\end{split}$

###### Proof.

1\. Base case: verify true for $k=1$.
For $k=1$ this theorem will reduce to Theorem 4.1. Hence, the case for $k=1$
is proven.
2\. Induction hypothesis: assume the statement is true until $k$.

$\begin{split}&\sum_{N_{k}=p}^{n}{\cdots\sum_{N_{1}=p}^{N_{2}}{\left[\binom{N_{1}+m}{m}\sum_{i=1+m}^{N_{1}+m}{\frac{1}{i}}\right]}}\\\
&\,\,\,\,=\binom{n+m+k}{m+k}\sum_{i=1+m+k}^{n+m+k}{\frac{1}{i}}-\sum_{j=0}^{k-1}{\binom{n-p+j}{j}\binom{p-1+m+k-j}{m+k-j}\sum_{i=1+m+k-j}^{p-1+m+k-j}{\frac{1}{i}}}.\end{split}$

3\. Induction step: we will show that this statement is true for $(k+1)$.
We have to show the following statement to be true:

$\begin{split}&\sum_{N_{k+1}=p}^{n}{\cdots\sum_{N_{1}=p}^{N_{2}}{\left[\binom{N_{1}+m}{m}\sum_{i=1+m}^{N_{1}+m}{\frac{1}{i}}\right]}}\\\
&\,\,\,\,=\binom{n+m+k+1}{m+k+1}\sum_{i=2+m+k}^{n+m+k+1}{\frac{1}{i}}-\sum_{j=0}^{k}{\binom{n-p+j}{j}\binom{p+m+k-j}{m+k-j+1}\sum_{i=2+m+k-j}^{p+m+k-j}{\frac{1}{i}}}.\end{split}$

Let us denote the first term of the equality as B.

$B=\sum_{N_{k+1}=p}^{n}{\left\\{\sum_{N_{k}=p}^{N_{k+1}}{\cdots\sum_{N_{1}=p}^{N_{2}}{\left[\binom{N_{1}+m}{m}\sum_{i=1+m}^{N_{1}+m}{\frac{1}{i}}\right]}}\right\\}}.$

Applying the induction hypothesis, we get

$\begin{split}B&=\sum_{N_{k+1}=p}^{n}{\binom{N_{k+1}+m+k}{m+k}\sum_{i=1+m+k}^{N_{k+1}+m+k}{\frac{1}{i}}}\\\
&-\sum_{N_{k+1}=p}^{n}{\sum_{j=0}^{k-1}{\binom{N_{k+1}-p+j}{j}\binom{p-1+m+k-j}{m+k-j}\sum_{i=1+m+k-j}^{p-1+m+k-j}{\frac{1}{i}}}}\\\
&=\sum_{N_{k+1}=p}^{n}{\binom{N_{k+1}+m+k}{m+k}\sum_{i=1+m+k}^{N_{k+1}+m+k}{\frac{1}{i}}}\\\
&-\sum_{j=0}^{k-1}{\left\\{\sum_{N_{k+1}=p}^{n}{\binom{N_{k+1}-p+j}{j}}\right\\}\binom{p-1+m+k-j}{m+k-j}\sum_{i=1+m+k-j}^{p-1+m+k-j}{\frac{1}{i}}}.\end{split}$

Applying Theorem 4.1 to the first term and applying Theorem 2.1 to the term in
curly brackets,

$\begin{split}B&=\binom{n+m+k+1}{m+k+1}\sum_{i=2+m+k}^{n+m+k+1}{\frac{1}{i}}-\binom{p+m+k}{m+k+1}\sum_{i=2+m+k}^{p+m+k}{\frac{1}{i}}\\\
&-\sum_{j=0}^{k-1}{\binom{n-p+j+1}{j+1}\binom{p-1+m+k-j}{m+k-j}\sum_{i=1+m+k-j}^{p-1+m+k-j}{\frac{1}{i}}}\\\
&=\binom{n+m+k+1}{m+k+1}\sum_{i=2+m+k}^{n+m+k+1}{\frac{1}{i}}-\binom{p+m+k}{m+k+1}\sum_{i=2+m+k}^{p+m+k}{\frac{1}{i}}\\\
&-\sum_{j=1}^{k}{\binom{n-p+j}{j}\binom{p+m+k-j}{m+k-j+1}\sum_{i=2+m+k-j}^{p+m+k-j}{\frac{1}{i}}}\\\
&=\binom{n+m+k+1}{m+k+1}\sum_{i=2+m+k}^{n+m+k+1}{\frac{1}{i}}-\sum_{j=0}^{k}{\binom{n-p+j+1}{j+1}\binom{p-1+m+k-j}{m+k-j}\sum_{i=1+m+k-j}^{p-1+m+k-j}{\frac{1}{i}}}.\end{split}$

Hence, the theorem holds true for $(k+1)$. Thus, the theorem is proven by
induction. ∎

######  Corollary 4.2.

For $p=1$, Theorem 4.2 becomes

$\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\left[\binom{N_{1}+m}{m}\sum_{i=1+m}^{N_{1}+m}{\frac{1}{i}}\right]}}=\binom{n+m+k}{m+k}\sum_{i=1+m+k}^{n+m+k}{\frac{1}{i}}.$

A particular case of Corollary 4.2 which is of major interest is the repeated
harmonic sum.

######  Corollary 4.3.

The repeated harmonic sum of order $(m+1)$ is related to the shifted harmonic
sum of order $1$ by the following relation,

$\sum_{N_{m+1}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{\frac{1}{N_{1}}}}}=\binom{n+m}{m}\sum_{N=1+m}^{n+m}{\frac{1}{N}}.$

###### Proof.

Applying Corollary 4.2 with $m=0$, we get this corollary. ∎

##  5 Application to repeated sums

###  5.1 Reduction of a repeated sum

Let us denote the repeated sum of order $m$ of the sequence $a_{N}$ with lower
and upper bounds respectively $q$ and $n$ as $S_{m,q,n}(a_{N})$. For
simplicity, we will denote it as $S_{m,q,n}$.

$S_{m,q,n}=\sum_{N_{m}=q}^{n}{\sum_{N_{m-1}=q}^{N_{m}}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}.$

Recursively, it can be defined by:

$\displaystyle\begin{cases}S_{m,q,n}=\sum_{N_{m}=q}^{n}{S_{m-1,q,N_{m}}},\\\
S_{0,q,n}\,\,=a_{n}\,\,\,\,\forall q,n\in\mathbb{N}.\end{cases}$

####  5.1.1 Variation Formula

In this section, we will present formulas to express the variation of a
repeated sum of order $m$ ($S_{m,q,n+1}-S_{m,q,n}$) in terms of lower order
repeated sums. Equivalently, these formulas can be used to express
$S_{m,q,n+1}$ in terms of $S_{m,q,n}$ and lower order repeated sums.

We begin by presenting the variation formula that allows $S_{m,q,n+1}$ to be
expressed in terms of $S_{m,q,n}$ and of repeated sums of order going from $0$
to $(m-1)$.

######  Theorem 5.1.

For any $n,q\in\mathbb{N}$ such that $n\geq q$, and for any
$m\in\mathbb{N^{*}}$, we have

$\sum_{N_{m}=q}^{n+1}{\sum_{N_{m-1}=q}^{N_{m}}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}=\sum_{k=1}^{m}{\left(\sum_{N_{k}=q}^{n}{\sum_{N_{k-1}=q}^{N_{k}}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}\right)}+a_{n+1}.$

Or using the notation,

$S_{m,q,n+1}=\sum_{k=1}^{m}{S_{k,q,n}}+S_{0,q,n+1}.$

###### Proof.

In [1], the author presented the following variation formula:

$\sum_{N_{m}=q}^{n+1}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{(m);N_{m}}\cdots
a_{(1);N_{1}}}}=\sum_{k=0}^{m}{\left(\prod_{j=0}^{m-k-1}{a_{(m-j);n+1}}\right)\left(\sum_{N_{k}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{(k);N_{k}}\cdots
a_{(1);N_{1}}}}\right)}.$

Setting $a_{(m);N}=\cdots=a_{(2);N}=1$ and $a_{(1);N}=a_{N}$, we obtain this
theorem. ∎

The variation of a repeated sum can also be expressed in terms of only a
certain range of lower order repeated sums. In other words, $S_{m,q,n+1}$ can
be expressed in terms of $S_{m,q,n}$ and of repeated sums of order going only
from $p$ to $(m-1)$. To do so, we give the following theorem.

######  Theorem 5.2.

For any $n,q\in\mathbb{N}$ such that $n\geq q$, and for any
$m,p\in\mathbb{N^{*}}$ such that $p\leq m$, we have

$\sum_{N_{m}=q}^{n+1}{\sum_{N_{m-1}=q}^{N_{m}}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}=\sum_{k=p+1}^{m}{\left(\sum_{N_{k}=q}^{n}{\sum_{N_{k-1}=q}^{N_{k}}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}\right)}+\sum_{N_{p}=q}^{n+1}{\sum_{N_{p-1}=q}^{N_{p}}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}.$

Or using the notation,

$S_{m,q,n+1}=\sum_{k=p+1}^{m}{S_{k,q,n}}+S_{p,q,n+1}.$

###### Proof.

In [1], the author presented the following variation formula:

$\begin{split}\sum_{N_{m}=q}^{n+1}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{(m);N_{m}}\cdots
a_{(1);N_{1}}}}=&\sum_{k=p+1}^{m}{\left(\prod_{j=0}^{m-k-1}{a_{(m-j);n+1}}\right)\left(\sum_{N_{k}=q}^{n}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{(k);N_{k}}\cdots
a_{(1);N_{1}}}}\right)}\\\
&+\left(\prod_{j=0}^{m-p-1}{a_{(m-j);n+1}}\right)\left(\sum_{N_{p}=q}^{n+1}{\cdots\sum_{N_{1}=q}^{N_{2}}{a_{(p);N_{p}}\cdots
a_{(1);N_{1}}}}\right).\end{split}$

Setting $a_{(m);N}=\cdots=a_{(2);N}=1$ and $a_{(1);N}=a_{N}$, we obtain this
theorem. ∎

####  5.1.2 Reduction Formula

Now that we have proven the needed binomial coefficient definitions and
identities, we derive a formula to simplify the repeated sum of any sequence
$a_{N}$.

######  Theorem 5.3.

For any $m\in\mathbb{N^{*}}$, for any $q,n\in\mathbb{N}$ such that $n\geq q$
and for any sequence $a_{N}$ defined in the interval $[q,n]$, we have that

$\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{2}=q}^{N_{3}}{\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}=\sum_{i=q}^{n}{\binom{n+(m-1)-i}{m-1}a_{i}}.$

###### Proof.

Applying Theorem 3.3 from [1], for $a_{(m);N_{m}}=\cdots=a_{(2);N_{2}}=1$ and
$a_{(1);N_{1}}=a_{N_{1}}$, we get

$\sum_{N_{m}=q}^{n}{\cdots\sum_{N_{2}=q}^{N_{3}}{\sum_{N_{1}=q}^{N_{2}}{a_{N_{1}}}}}=\sum_{N_{1}=q}^{n}{a_{N_{1}}\sum_{N_{m}=N_{1}}^{n}{\cdots\sum_{N_{3}=N_{1}}^{N_{4}}{\sum_{N_{2}=N_{1}}^{N_{3}}{1}}}}.$

By applying Corollary 2.4 to the $(m-1)$ inner sums, we have

$\sum_{N_{m}=N_{1}}^{n}{\cdots\sum_{N_{3}=N_{1}}^{N_{4}}{\sum_{N_{2}=N_{1}}^{N_{3}}{1}}}=\binom{n-N_{1}+m-1}{m-1}.$

Hence, substituting back, we get the desired theorem. ∎

Theorem 5.3 offers a more computationally efficient way of calculating
repeated sums as computing the repeated sum directly requires adding up
$\binom{n-q+m}{m}$ terms while using the simplified form requires adding up
only $n-q+1$ terms. Also notice that the number of terms added in the
simplified form is independent of the order $m$. For example, let us consider
a repeated sum of order $m=10$ and with lower and upper bounds respectively
$q=1$ and $n=10$: computing this repeated sum directly requires adding $92378$
terms while using the theorem requires adding only $10$ terms.

######  Remark.

From Theorem 5.3, we can deduce that a term $a_{i}$ appears
$\binom{n+(m-1)-i}{m-1}$ times in the repeated sum of the sequence $a_{N}$.

######  Corollary 5.1.

If the sums start at $1$, Theorem 5.3 becomes

$\sum_{N_{m}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{a_{N_{1}}}}}=\sum_{i=1}^{n}{\binom{n+(m-1)-i}{m-1}a_{i}}.$

####  5.1.3 Application to harmonic sums and repeated harmonic sums

In this section, we apply Theorem 5.3 to develop some formulae for harmonic
sums and repeated harmonic sums.

First, we introduce a formula for simplifying repeated harmonic sums.

######  Theorem 5.4.

For any $m,n\in\mathbb{N^{*}}$, we have that

$\sum_{N_{m}=1}^{n}{\cdots\sum_{N_{2}=1}^{N_{3}}{\sum_{N_{1}=1}^{N_{2}}{\frac{1}{N_{1}}}}}=\sum_{i=1}^{n}{\binom{n+(m-1)-i}{m-1}\frac{1}{i}}=\binom{n+m-1}{m-1}\sum_{i=m}^{n+m-1}{\frac{1}{i}}.$

###### Proof.

By equating the expression of the repeated harmonic sum obtained from
Corollary 4.3 with that obtained from Theorem 5.3 for $a_{N}=\frac{1}{N}$, we
obtain this theorem. ∎

Now we present identities related to the harmonic sum. We start with the
following identity.

######  Theorem 5.5.

For any $m,n\in\mathbb{N}$ such that $n\geq 1$, we have that

$\sum_{i=1}^{n}{\frac{\binom{n}{i}}{\binom{n+m}{i}}\frac{1}{i}}=\sum_{i=1}^{n}{\left[\prod_{k=0}^{i-1}{\frac{(n-k)}{(n+m-k)}}\right]\frac{1}{i}}=\sum_{i=1+m}^{n+m}{\frac{1}{i}}.$

###### Proof.

From Theorem 5.4 with $m$ substituted by $(m+1)$,

$\sum_{i=1}^{n}{\binom{n+m-i}{m}\frac{1}{i}}=\binom{n+m}{m}\sum_{i=1+m}^{n+m}{\frac{1}{i}}.$

Knowing that

$\frac{\binom{n+m-i}{m}}{\binom{n+m}{m}}=\frac{\binom{n}{i}}{\binom{n+m}{i}}=\prod_{k=0}^{i-1}{\frac{(n-k)}{(n+m-k)}},$

hence, substituting back, we obtain the theorem. ∎

In order to prove the second identity, we need to first prove the following
two lemmas.

######  Lemma 5.1.

For any $k\in\mathbb{N}^{*}$, we have that

$\sum_{i=1}^{2k}{\frac{1}{i}}=(2k+1)\sum_{i=1}^{k}{\frac{1}{(2k+1-i)i}}=\frac{(2k+1)}{2}\sum_{i=1}^{2k}{\frac{1}{(2k+1-i)i}}.$

###### Proof.

We split the sum, modify its parts, then recombine them to obtain,

$\sum_{i=1}^{2k}{\frac{1}{i}}=\sum_{i=1}^{k}{\frac{1}{i}}+\sum_{i=k+1}^{2k}{\frac{1}{i}}=\sum_{i=1}^{k}{\frac{1}{i}}+\sum_{i=1}^{k}{\frac{1}{2k+1-i}}=(2k+1)\sum_{i=1}^{k}{\frac{1}{(2k+1-i)i}}.$

Similarly,

$\begin{split}\frac{(2k+1)}{2}\sum_{i=1}^{2k}{\frac{1}{(2k+1-i)i}}&=\frac{(2k+1)}{2}\left[\sum_{i=1}^{k}{\frac{1}{(2k+1-i)i}}+\sum_{i=k+1}^{2k}{\frac{1}{(2k+1-i)i}}\right]\\\
&=\frac{(2k+1)}{2}\left[\sum_{i=1}^{k}{\frac{1}{(2k+1-i)i}}+\sum_{i=1}^{k}{\frac{1}{(2k+1-i)i}}\right]\\\
&=(2k+1)\sum_{i=1}^{k}{\frac{1}{(2k+1-i)i}}.\end{split}$

Equating, we obtain the lemma. ∎

######  Lemma 5.2.

For any $k\in\mathbb{N}^{*}$, we have that

$\sum_{i=1}^{2k-1}{\frac{1}{i}}=(2k)\sum_{i=1}^{k}{\frac{1}{(2k-i)i}}-\frac{1}{k}=(2k)\sum_{i=1}^{k-1}{\frac{1}{(2k-i)i}}+\frac{1}{k}=(k)\sum_{i=1}^{2k-1}{\frac{1}{(2k-i)i}}.$

###### Proof.

We split the sum, modify its parts, then recombine them to obtain,

$\sum_{i=1}^{2k-1}{\frac{1}{i}}=\sum_{i=1}^{k}{\frac{1}{i}}+\sum_{i=k}^{2k-1}{\frac{1}{i}}-\frac{1}{k}=\sum_{i=1}^{k}{\frac{1}{i}}+\sum_{i=1}^{k}{\frac{1}{2k-i}}-\frac{1}{k}=(2k)\sum_{i=1}^{k}{\frac{1}{(2k-i)i}}-\frac{1}{k}.$

Similarly,

$\sum_{i=1}^{2k-1}{\frac{1}{i}}=\sum_{i=1}^{k-1}{\frac{1}{i}}+\sum_{i=k+1}^{2k-1}{\frac{1}{i}}+\frac{1}{k}=\sum_{i=1}^{k-1}{\frac{1}{i}}+\sum_{i=1}^{k-1}{\frac{1}{2k-i}}+\frac{1}{k}=(2k)\sum_{i=1}^{k-1}{\frac{1}{(2k-i)i}}+\frac{1}{k}.$

Finally, to obtain the last part of this lemma, we perform the following,

$\begin{split}(k)\sum_{i=1}^{2k-1}{\frac{1}{(2k-i)i}}&=(k)\left[\sum_{i=1}^{k-1}{\frac{1}{(2k-i)i}}+\frac{1}{k^{2}}+\sum_{i=k+1}^{2k-1}{\frac{1}{(2k-i)i}}\right]\\\
&=(k)\left[\sum_{i=1}^{k-1}{\frac{1}{(2k-i)i}}+\sum_{i=1}^{k-1}{\frac{1}{(2k-i)i}}\right]+\frac{1}{k}\\\
&=(2k)\sum_{i=1}^{k-1}{\frac{1}{(2k-i)i}}+\frac{1}{k}.\end{split}$

Equating, we obtain the lemma. ∎

Now that both needed lemmas have been proven, we give the second identity.

######  Theorem 5.6.

For any $n\in\mathbb{N^{\ast}}$, we have that

$\frac{n+1}{2}\sum_{i=1}^{n}{\frac{1}{(n+1-i)i}}=\sum_{i=1}^{n}{\frac{1}{i}}.$

###### Proof.

For this proof, a proof by case will be performed. Thus, the proof will be
divided into proving two complementary cases: the case when $n$ is even and
the case when $n$ is odd.

  * •

For $n=2k$ (where $k\in\mathbb{N^{*}}$):
This case corresponds to Lemma 5.1 that we have already proven.

  * •

For $n=2k-1$ (where $k\in\mathbb{N^{*}}$):
This case corresponds to Lemma 5.2 that we have already proven.

The formula holds true for both even and odd values of $n$, hence, it holds
for any $n\geq 1$. ∎

###  5.2 Reduction of the repeated “Binomial-Sequence” sum

In this section, we prove a generalization of Theorem 5.3. This generalization
is illustrated in the following theorem. The following theorem simplifies the
repeated “Binomial-Sequence” sum.

######  Theorem 5.7.

For any $k\in\mathbb{N^{*}}$, for any $m,q,n\in\mathbb{N}$ where $n\geq q$ and
for any sequence $a_{N}$ defined in the interval $[q,n]$, we have that

$\sum_{N_{k}=q}^{n}{\cdots\sum_{N_{2}=q}^{N_{3}}{\sum_{N_{1}=q}^{N_{2}}{\binom{(N_{2}-N_{1})+m}{m}a_{N_{1}}}}}=\sum_{N=q}^{n}{\binom{(n-N)+m+k-1}{m+k-1}a_{N}}.$

###### Proof.

By applying Theorem 5.3 to the inner sum, we have

$\begin{split}\sum_{N_{k}=q}^{n}{\cdots\sum_{N_{2}=q}^{N_{3}}{\sum_{N_{1}=q}^{N_{2}}{\binom{(N_{2}-N_{1})+m}{m}a_{N_{1}}}}}&=\sum_{N_{k}=q}^{n}{\cdots\sum_{N_{2}=q}^{N_{3}}{\sum_{j_{m+1}=q}^{N_{2}}{\cdots\sum_{j_{1}=q}^{j_{2}}{a_{j_{1}}}}}}\\\
&=\sum_{i_{m+k}=q}^{n}{\cdots\sum_{i_{2}=q}^{i_{3}}{\sum_{i_{1}=q}^{i_{2}}{a_{i_{1}}}}}\\\
&=\sum_{N=q}^{n}{\binom{(n-N)+m+k-1}{m+k-1}a_{N}}\end{split}$

∎

######  Corollary 5.2.

If the summations start at $1$, Theorem 5.7 becomes,

$\sum_{N_{k}=1}^{n}{\cdots\sum_{N_{1}=1}^{N_{2}}{\binom{(N_{2}-N_{1})+m}{m}a_{N_{1}}}}=\sum_{N=1}^{n}{\binom{(n-N)+m+k-1}{m+k-1}a_{N}}.$

For the simple “Binomial-Sequence” sum, Theorem 5.7 and Corollary 5.2 reduce
to the following.

######  Theorem 5.8.

For any $m\in\mathbb{N}^{*}$, for any $q,n\in\mathbb{N}$ where $n\geq q$ and
for any sequence $a_{N}$ defined in the interval $[q,n]$, we have that

$\sum_{N_{2}=q}^{n}{\sum_{N_{1}=q}^{N_{2}}{\binom{(N_{2}-N_{1})+(m-1)}{m-1}a_{N_{1}}}}=\sum_{N=q}^{n}{\binom{(n-N)+m}{m}a_{N}}.$

######  Corollary 5.3.

If the summations start at $1$, Theorem 5.8 becomes,

$\sum_{N_{2}=1}^{n}{\sum_{N_{1}=1}^{N_{2}}{\binom{(N_{2}-N_{1})+(m-1)}{m-1}a_{N_{1}}}}=\sum_{N=1}^{n}{\binom{(n-N)+m}{m}a_{N}}.$

## References

  * [1] R. El Haddad, Recurrent sums and partition identities, arXiv preprint arXiv:2101.09089 (2021).
  * [2] R. El Haddad, Multiple sums and partition identities, arXiv preprint arXiv:2102.00821 (2021).
  * [3] B. Pascal, Traité du triangle arithmétique avec quelques autres petits traitez sur la mesme matière, Chez Gvillavme Desprer, 1978.
  * [4] B. Pascal, Traité du triangle arithmétique, Éd. les Caractères d’Ulysse, 2011.
  * [5] D. T. Whiteside, Newton’s discovery of the general binomial theorem, The Mathematical Gazette (1961) 175–180.
  * [6] D. T. Whiteside, Henry briggs: The binomial theorem anticipated, The Mathematical Gazette 45 (351) (1961) 9–12.
  * [7] J. C. Polking, A leibniz formula for some differentiation operators of fractional order, Indiana University Mathematics Journal 21 (11) (1972) 1019–1029.
  * [8] D. Mazkewitsch, The n-th derivative of a produc, The American Mathematical Monthly 70 (7) (1963) 739–742.
  * [9] R. Dybowski, A generalization of the leibniz rule for derivatives (2009).
  * [10] L. Bol’shev, N. Smirnov, Mathematical statistics tables, Moscow: Science (1983).
  * [11] J. C. P. Miller, Table of binomial coefficients, Vol. 3, Published for the Royal Society at the University Press, 1954.
  * [12] R. S. G. B. M. T. Committee, J. Miller, Mathematical Tables: Table of Binomial Coefficients, Published for the Royal Society at Cambridge UP, 1954.
  * [13] P. Olofsson, M. Andersson, Probability, statistics, and stochastic processes (2012).
  * [14] N. Oresme, Quaestiones super geometriam Euclidis, Vol. 3, Brill Archive, 1961.
  * [15] P. Mengoli, ”praefatio [preface]”. novae quadraturae arithmeticae, seu de additione fractionum [new arithmetic quadrature (i.e., integration), or on the addition of fractions]. bologna: Giacomo monti. (1650).
  * [16] J. Bernoulli, ”corollary iii of de seriebus varia”. opera omnia. lausanne & basel: Marc-michel bousquet & co. 4 (1742) 8.
  * [17] J. Bernoulli, Propositiones arithmeticae de seriebus infinitis earumque summa finita [arithmetical propositions about infinite series and their finite sums]. basel: J. conrad. (1689).
  * [18] J. Bernoulli, Ars Conjectandi, Opus Posthumum; Accedit Tractatus De Seriebus Infinitis, Et Epistola Gallicè scripta De Ludo Pilae Reticularis [Theory of inference, posthumous work. With the Treatise on infinite series…]., Thurnisii, 1713.