1. Introduction
The Motzkin numbers $\{M_n\}_{n=0}^{\infty}=1, 1, 2, 4, 9, 21, 51, 127,\ldots$ first appeared in [Reference Motzkin6] in a circle chording setting, which count the number of ways of connecting a subset of n points on a circle by nonintersecting chords. The Motzkin number Mn also counts the number of lattice paths on the upper right quadrant of a grid from $(0,0)$ to $(n,0)$ if one is allowed to move by using only steps $(1,1),(1,0)$ and $(1,-1)$ but forbidden from dipping below the y = 0 axis.
The Motzkin numbers are named after Theodore Motzkin and naturally appear in various combinatorial objects. Fourteen different manifestations of Motzkin numbers in different branches of mathematics were enumerated by Donaghey and Shapiro [Reference Donaghey and Shapiro2] in their survey of Motzkin numbers. The interested readers may refer to [Reference Stanley11] for further information on Motzkin numbers.
The famous Catalan numbers $C_n={2n\choose n}/(n+1)$ are closely related to Motzkin numbers. The Motzkin numbers can be expressed in terms of Catalan numbers:
and inversely,
where $\lfloor x \rfloor$ denotes the integral part of real x.
Another sequence closely related to Motzkin numbers are the central trinomial coefficients. For $n\in \mathbb{N}$, the central trinomial coefficient Tn is given by the constant term in the expansion of $(1+x+x^{-1})^n$, which can be expressed in terms of binomial coefficients:
Note that $\{T_n\}_{n=0}^{\infty}=1, 1, 3, 7, 19, 51, 141, 393,\ldots$. We remark that the central trinomial coefficient Tn counts the number of lattice paths from $(0,0)$ to $(n,0)$ if one is allowed to move by using only steps $(1,1),(1,0)$ and $(1,-1)$.
Although Catalan numbers, Motzkin numbers and central trinomial coefficients naturally arise in combinatorics, they also possess rich arithmetic properties.
Throughout the paper, let $p\ge 5$ be a prime. Sun and Tauraso [Reference Sun and Tauraso16] showed that
where $\left(-\right)$ denotes the Legendre symbol.
In 2014, Sun [Reference Sun12] proved that
By the telescoping method for double summations developed by Chen, Hou and Mu [Reference Chen, Hou and Mu1], Sun [Reference Sun14] recently established the following interesting supercongruence:
The motivation of the paper is the following three conjectural supercongruences of Sun [Reference Sun12, Conjecture 1.1]:
‘The three supercongruences look curious and challenging’, as described by Sun [Reference Sun14] in his recent paper. Although the three supercongruence conjectures were officially announced by Sun [Reference Sun12] in 2014, they first appeared in arXiv version of Sun’s paper in 2010 (see https://arxiv.org/abs/1008.3887).
Note that (1.3) follows immediately from (1.1) and (1.2). In this paper, we aim to prove (1.2) and (1.4).
We remark that both Motzkin numbers and central trinomial coefficients have many different expressions (see A001006 and A002426 in [Reference Sloane10]). The following two expressions will be used in the proof of Theorem 1.1:
The rest of the paper is organized as follows. Section 2 is devoted to proving some preliminary results. In § 3, we establish three congruences for triple sums which play an important role in the proof of Theorem 1.1. We show (1.2) in § 4, whereas (1.4) is proved in § 5.
2. Preliminaries
Let $p\ge 5$ be a prime. In the proof of Theorem 1.1, we will frequently use Wolstenholme’s theorem [Reference Wolstenholme19]:
which is equivalent to
and Lehmer’s congruences [Reference Lehmer5]:
where $q_p(a)$ denotes the Fermat quotient $(a^{p-1}-1)/p$.
In addition, we require some congruences related to central binomial coefficients and Catalan numbers.
Lemma 2.1. For any prime $p\ge 5$, we have
Proof. Congruences (2.6)–(2.8) were proved by Sun and Tauraso (see [Reference Sun and Tauraso16, (1.7) and (1.9)] and [Reference Sun and Tauraso15, Theorem 1.3]). It is easily proved by induction on n that
Letting n = p in (2.11) and using (2.2) gives
Then the proof of (2.9) follows from (2.6) and (2.12).
From the following identity:
we deduce that
where we have used (2.7) and (2.8).
By (2.7), (2.13) and the identity $C_k={2k\choose k}-{2k\choose k+1}$, we have
as desired.
We also need some congruences involving harmonic numbers $H_n=\sum_{k=1}^n 1/k$.
Lemma 2.2 For any prime $p\ge 5$, we have
Proof. Congruence (2.14) is a known result. We begin with the following congruence due to Tauraso [Reference Tauraso17, (9)]:
where $y=-x/(1-4x)$. Letting x = 1 in (2.17) and using the congruence [Reference Sun and Tauraso15, (1.13)], we arrive at
which is (2.14).
By using the software package Sigma developed by Schneider [Reference Schneider9], we can automatically discover and prove the following three combinatorial identities:
and
By (2.18), we can rewrite (2.19) and (2.20) as
and
Using Fermat’s little theorem, we obtain
From Granville’s congruence [Reference Granville4]:
we deduce that
which was also mentioned in the proof of [Reference Sun13, Lemma 3.3]. Thus,
Finally, letting $n=(p-1)/2$ in (2.21)–(2.22) and using (2.5), (2.14), (2.23) and the facts that $H_{p-1}\equiv 0\pmod{p^2}$ and
For an assertion A, we set
The following two known congruences play important roles in the proof of Theorem 1.1 (see [Reference Pan and Sun7, Theorem 1.2]).
Lemma 2.3. Let $p\ge 5$ be a prime. For $1\le k \le p$, we have
where $\alpha(k)=2(-1)^k+3[3\mid p-k])$.
Based on Lemma 2.3, we establish the following result which seems to be crude but useful in the proof of Theorem 1.1.
Lemma 2.4. Let $p\ge 5$ be a prime. For $1\le k \le p$, we have
where $\beta(i)=(-1)^i(3[3\mid p-i]-1)$.
Proof. By Pascal’s formula ${n\choose m}={n-1\choose m}+{n-1\choose m-1}$, we have
It follows that
Let
We rewrite (2.27) as
From (2.28), we deduce that
and so
By ${2i\choose i+1}={2i\choose i}-{2i\choose i}/(i+1)$, we have
where we have used (2.7) and (2.10) in the last step.
Combining (2.25), (2.29) and (2.30) gives
as desired.
3. Three key triple sums
The main idea in the proof of Theorem 1.1 is to translate the left-hand sides of (1.2) and (1.4) into three triple sums, which can be determined modulo p by using Lemmas 2.3 and 2.4. The three congruences for triple sums are stated as follows.
Lemma 3.1. For any prime $p\ge 5$, we have
Proof. Substituting (2.25) and (2.26) into the left-hand side of (3.1) gives
We shall only prove the case $p\equiv 1\pmod{3}$ of (3.1). The proof of the case $p\equiv 2\pmod{3}$ runs analogously, and we omit the details.
Suppose that $p\equiv 1\pmod{3}$. Let $n=\lfloor p/6\rfloor$. Then $n\equiv -1/6\pmod{p}$. Since the sequences $\{\alpha(k)\}_{k\in \mathbb{N}}$ and $\{\beta(k)\}_{k\in \mathbb{N}}$ both have a period of 6, it is easy to check that
and
It follows that
and
Furthermore, we have
where we have used (3.3) in the last step. It is also easy to check that
and so
Substituting (3.3)–(3.5) into the right-hand side of (3.2) gives
Finally, noting that for $p\equiv 1\pmod{3}$, $2n=\lfloor p/3\rfloor,3n=\lfloor p/2\rfloor, 4n=\lfloor 2p/3\rfloor$ and applying (2.3)–(2.5) to the right-hand side of (3.6), we arrive at the desired result:
which is the case $p\equiv 1\pmod{3}$ of (3.1).
Lemma 3.2. For any prime $p\ge 5$, we have
Proof. By (2.24) and (2.25), we have
We shall only prove the case $p\equiv 1\pmod{3}$, and the proof of the case $p\equiv 2\pmod{3}$ runs similarly and the details are omitted.
Suppose that $p\equiv 1\pmod{3}$. Let $n=\lfloor p/6\rfloor$. Then $n\equiv -1/6\pmod{p}$. It is easy to check that
It follows that
Finally, noting that for $p\equiv 1\pmod{3}$, $2n=\lfloor p/3\rfloor,3n=\lfloor p/2\rfloor, 4n=\lfloor 2p/3\rfloor, 5n=\lfloor 5p/6 \rfloor$ and applying (2.3)–(2.5) to the right-hand side of (3.9), we obtain
which is the case $p\equiv 1\pmod{3}$ of (3.7).
Lemma 3.3. For any prime $p\ge 5$, we have
Proof. By (2.24) and (2.26), we have
Similarly, we only prove the case $p\equiv 1\pmod{3}$. Suppose that $p\equiv 1\pmod{3}$. It is easy to check that
and
It follows that
and
From (3.12), we deduce that
Furthermore, we have
where we have used (3.14) in the last step. It is easy to check that
Combining (3.15) and (3.16) yields
where we have used the fact that $2n=\lfloor p/3\rfloor,3n=\lfloor p/2\rfloor, 4n=\lfloor 2p/3\rfloor, 5n=\lfloor 5p/6 \rfloor$ for $p\equiv 1\pmod{3}$ and (2.3)–(2.5) in the last step.
Finally, substituting (3.13), (3.14) and (3.17) into the right-hand side of (3.11) gives
which is the case $p\equiv 1\pmod{3}$ of (3.10).
4. Proof of (1.2)
By (1.5), we have
From the identity [Reference Riordan8, (9), page 15]:
we deduce that
where we have utilized the hockey-stick identity in the last step. Letting $l\to k-i$ on the right-hand side of (4.2), we rewrite (4.2) as
Note that ${k\choose j}{j\choose k-i}\equiv 0\pmod{p}$ for $0\le i\le p-1,0\le j\le p-1$ and $p\le k \le 2p-2$, and
for $0\le k\le p-1$. It follows that
Recall the following partial fraction decomposition:
where $(x)_0=1$ and $(x)_k=x(x+1)\cdots (x+k-1)$ for $k\ge 1$. Letting x = 1 in (4.4) gives
It follows from (4.3) and (4.5) that
Combining (4.1) and (4.6) gives
Let
From the identity due to Von Szily [Reference Von Szily18] (see also [Reference Gould3, (3.38)]):
we deduce that $S(i,j)$ is an integer. It is easy to verify that the numbers $S(i,j)$ satisfy the recurrence:
Note that
It follows from (4.7) and (4.10) that
where we have used the symmetry with respect to i and j in the third step.
By (4.9), we have
Furthermore, by (2.2), we have
For $1\le j\le p-2$, we have ${p+1+j\choose j}\equiv j+1\pmod{p}$. It follows that
where we have used (2.10) in the last step.
On the other hand, we have
where we have used (2.1), (2.2) and (2.10) in the last step.
It follows from (4.12), (4.13) and (4.14) that
Combining (4.11) and (4.15) gives
Note that
Furthermore, we have
where we have used (2.2), (2.8) and the fact that ${p+i\choose i}\equiv 1\pmod{p}$ for $1\le i\le p-1$.
For $1\le i\le p-1$, we have $p/\left(i{i+p-1\choose i}\right)\equiv 1-pH_{i-1}\pmod{p^2}$, and so
where we have used (2.1), (2.6), (2.8) and (2.14).
For $1\le j\le p-1$, we have ${p+j\choose j}\equiv 1+pH_j \pmod{p^2}$, and so
where we have used (2.2), (2.7) and (2.16).
It follows from (4.17)–(4.20) that
Combining (4.16) and (4.21) gives
By (4.8), we have
It follows that
where we have used (2.8) in the last step.
Finally, combining (4.22) and (4.24) yields
5. Proof of (1.4)
Applying (4.6) to the right-hand side of (5.1), we obtain
Noting that
we have
Note that
and
For $0\le j\le p-1$, we have ${p+j\choose j}\equiv 1+pH_j\pmod{p^2}$, and so
where we have used (2.2), (2.6) and (2.14).
By (5.5), we have
By (2.1) and $p/{p+j-1\choose j}\equiv j(1-pH_{j-1})\pmod{p^2}$ for $1\le j\le p-1$, we have
where we have used (2.6), (2.9) and (2.15) in the last step.
It follows from (5.2)–(5.7) that
By (4.23), we have
where we have used (2.8) in the last step.
On the other hand, we have
where we have used (2.6), (2.7) and $C_{p-1}\equiv -1\pmod{p}$ in the last step.
It follows from (5.8)–(5.10) that
Then the proof of (1.4) follows from (3.7), (3.10) and (5.11).
Acknowledgements
The author is grateful to the anonymous referee for both the careful reading of the manuscript, and also the valuable comments and suggestions, which well improve the exposition of the paper. This work was supported by the National Natural Science Foundation of China (grant 12171370).