
% ----------------------------------------------------------------
% AMS-LaTeX Paper ************************************************
% **** -----------------------------------------------------------
\documentclass{amsart}
\usepackage{graphicx}
% ----------------------------------------------------------------
\vfuzz2pt % Don't report over-full v-boxes if over-edge is small
\hfuzz2pt % Don't report over-full h-boxes if over-edge is small
% THEOREMS -------------------------------------------------------
\newtheorem{thm}{Theorem}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
%\theoremstyle{definition}
%\newtheorem{defn}[thm]{Definition}
%\theoremstyle{remark}
%\newtheorem{rem}[thm]{Remark}
%\numberwithin{equation}{section}
% MATH -----------------------------------------------------------
\newcommand{\norm}[1]{\left\Vert#1\right\Vert}
\newcommand{\abs}[1]{\left\vert#1\right\vert}
\newcommand{\set}[1]{\left\{#1\right\}}
\newcommand{\Real}{\mathbb R}
\newcommand{\eps}{\varepsilon}
\newcommand{\To}{\longrightarrow}
\newcommand{\BX}{\mathbf{B}(X)}
\newcommand{\A}{\mathcal{A}}
% ----------------------------------------------------------------
\begin{document}

\title{Congruence Theorems for sequences defined by partial sums}
\maketitle

\begin{center}
{\bf Moa Apagodu }\\
{Department of Mathematics, Virginia Commonwealth University,\\ Richmond, VA 23284, USA}\\

\vskip .2in

{\bf Doron Zeilberger }\\
 {Rutgers University, Department of Math., 110 Frelinghuysen Rd, Piscataway, NJ 08854}
\end{center}

\vskip .3in

\begin{abstract} In a recent interesting and innovative paper, Bill Chen, Qing-Hu Hou, and Doron Zeilberger developed symbolic-computational 
algorithms for finding congruences, mod p, of sequences of partial sums of combinatorial sequences given as constant terms of powers of Laurent polynomials. These include, inter alia, the famous combinatorial sequences of Catalan and Motzkin. Here we extend it in two directions. The Laurent polynomials in question can be of several variables, and instead of single sums we have double sums. In fact we even combine them.
\end{abstract}

\vskip .2in

\noindent  The topic of interest is to find 

$$
\left(\sum_{k=0}^{rp-1}a(k)\right)\,\,\text{mod}\,\,p \,\,,
$$

\noindent where $a(k)$ is some combinatorial sequence of one or more variables, $r$ is a positive integer, and $p$ (sumbolic) is a prime number. Our approach in this article is to first express the summand as a constant term of a Laurent polynomial featuring $k$ and then reduce the problem to that of finding diagonal coefficients of certain rational function. Thanks to the Apagodu-Zeilebreger algorithm, the later problem is garanteed to satisfy  a $P$-finite recurrence whose solution is congruent to the partial sum. The following notations are used for the remainder of the article.\\

\noindent The constant term of a Laurent polynomial $P(x_1,x_2,\ldots,x_n)$, the coefficient of $x_1^0x_2^0..x_n^0$, is denoted by $CT[P(x_1,x_2,\ldots,x_n)]$ and the general coefficinet of $x_1^{n_1}x_2^{n_2}..x_n^{n_k}$ in $P(x_1,x_2,\ldots,x_n)$ is denoted by $COEFF_{[x_1^{n_1}x_2^{n_2}..x_n^{n_k}]}$. For example, 
$$
\displaystyle{CT\left[ \frac{1}{xy}+3+5xy-x^3+6y^2\right]=3}\,\, \text{and} \,\, 
COEFF_{[xy]}\left[ \frac{1}{xy}+3+5xy+x^3+6y^2\right]=5.
$$

\noindent We use the symmetric representation of integers in $[-|m|/2, |m|/2]$ when reducing an integer modulo integer $m$. For example  6 mod $5=1$ and 4 mod $5 =-1$. 

\vskip .2in

\noindent We start with the single variable cse, the subject of  [6], to illustrate our approach.\\ 

\noindent {\bf Theorem 1}. For any prime $p$ and positive integer $r$, define

$\displaystyle{A(r;p):=\left(\sum_{n=0}^{rp-1} { 2n \choose n}\right)  \text{mod} \, p \,\,.}$ Then,  $A(1;p)=\left\{\begin{array}{l}
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-1 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$
\vskip .1in

\noindent  {\bf Proof}: Using the fact that $\displaystyle{{ 2n \choose n} = CT\left[ \frac{(1+x)^{2n}}{x^n} \right]}$ and $(a+b)^p\equiv_p a^p+b^p $, we have

\begin{eqnarray*}
\sum_{n=0}^{p-1} {2n \choose n} &=& \sum_{n=0}^{p-1} CT\left[ \left(\frac{(1+x)^{2n}}{x^n}\right)\right] \\
&=& \sum_{n=0}^{p-1} CT\left[ \left(2+x+\frac{1}{x}\right)^n\right] \\
&=& CT\left[ \frac{\left(2+x+\frac{1}{x}\right)^p-1}{2+x+\frac{1}{x}-1}\right] \\
&\equiv_p& CT \left[ \frac{1+x^{p}+\frac{1}{x^p}}{1+x+\frac{1}{x}}\right] \\
&\equiv_p& CT\left[ \frac{1+x^p+x^{2p}}{(1+x+x^2)x^{p-1}}\right] \\
&\equiv_p& COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right] \\
&\equiv_p& COEFF_{[x^{p-1}]} \left[ \frac{1-x}{1-x^3}\right] \\
\end{eqnarray*}

\noindent The result folllows from series expansion of the last expression.\\

\noindent {\bf Corollary 1 (Corollary 2.3, [6])}:   $A(2;p)=\left\{\begin{array}{l}
3 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-3 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\noindent {\bf Proof}: Proceed as in the thoerem,

\begin{eqnarray*}
\sum_{n=0}^{2p-1} {2n \choose n} &=& \sum_{n=0}^{2p-1} CT \left[ \left(\frac{(1+x)^{2n}}{x^n}\right)\right] \\
&=&CT \left[ \frac{\left(2+x+\frac{1}{x}\right)^{2p}-1}{2+x+\frac{1}{x}-1}\right] \\
&=&CT\left[ \frac{\left(6+4x+\frac{4}{x}+x^2+\frac{1}{x^2}\right)^{p}-1}{2+x+\frac{1}{x}-1}\right] \\
&\equiv_p&CT\left[ \frac{\left(6+4x^p+\frac{4}{x^p}+x^{2p}+\frac{1}{x^{2p}}\right)-1}{2+x+\frac{1}{x}-1}\right] \\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[  \frac{1+4x^p}{1+x+x^2}\right] \\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[ \frac{1}{1+x+x^2}\right]  +4 COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right] \\
\end{eqnarray*}

\noindent The result folllows from Theorem 1 and the last congruence. 

\vskip .2in

\noindent
{\bf Corollary 2 (Catalan Numbers)}:  Let $a(n)$ be the constant term of $\displaystyle{(1-x)\left(2+x+\frac{1}{x}\right)^n}$ and let
$$
A(r;p):=\left(\sum_{n=0}^{rp-1}  a(n)\right) \text{mod} \,p \,\,.
$$
 \noindent 
Then,  $A(1;p)=\left\{\begin{array}{l}
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-2 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.$

\noindent {\bf Proof}:  Continuing as above, 
\begin{eqnarray*}
\sum_{n=0}^{p-1} a(n) &=& \sum_{n=0}^{p-1} CT \left[(1-x)\left(2+x+\frac{1}{x}\right)^n\right] \\
&=& CT \left[ \frac{(1-x)\left(\left(2+x+\frac{1}{x}\right)^p-1\right)}{2+x+\frac{1}{x}-1}\right]\\
&\equiv_p& CT\left[ \frac{(1-x)\left(\left(2+x^p+\frac{1}{x^p}\right)-1\right)}{2+x+\frac{1}{x}-1}\right]\\
&\equiv_p& COEFF_{[x^{p-1}]} \left[  \frac{1-x}{1+x+x^2}\right] \\
&\equiv_p& COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right]  -  COEFF_{[x^{p-2}]} \left[ \frac{1}{1+x+x^2}\right] \\
\end{eqnarray*}

\noindent The result follows from Theorem 1 and the last congruence.

\vskip .2in


\noindent
{\bf Theorem 2 (Motzkin Numbers)}.  Let $a(n)$ be the constant term of $\displaystyle{(1-x^2)\left(1+x+\frac{1}{x}\right)^n}$ and define
$$A(r;p):=\sum_{n=0}^{rp-1}  a(n)\,\,. $$
 
\noindent 
Then,  $A(1;p)=\left\{\begin{array}{l}
2 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  4\\
-2 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 3 \mod 4\,\,\,.\\
\end{array}\right.
$

\noindent
{\bf Proof}: 

\begin{eqnarray*}
\sum_{n=0}^{p-1} a(n) &=& \sum_{n=0}^{p-1} CT \left[(1-x^2)\left(1+x+\frac{1}{x}\right)^n\right] \\
&=& CT \left[ \frac{(1-x^2)\left(\left(1+x+\frac{1}{x}\right)^p-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&\equiv_p& COEFF_{[x^{p-1}]} \left[  \frac{1-x^2}{1+x^2}\right] \\
&\equiv_p& COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x^2}\right]  -  COEFF_{[x^{p-3}]} \left[ \frac{1}{1+x^2}\right] \\
\end{eqnarray*}

\noindent The result follows from series expansion of $\displaystyle{\frac{1}{1+x^2}}$ and the last congruence.

\vskip .2in

\noindent
{\bf Corollary 3}:  Let $a(n)$ be the constant term of $\displaystyle{(1-x^2)\left(1+x+\frac{1}{x}\right)^n}$ and let

$$
A(r;p):=\sum_{n=0}^{rp-1}  a(n)\,\,. 
$$
 
\noindent 
Then,  $A(1;p)=\left\{\begin{array}{l}
4 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  4\\
-4 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 3 \mod 4\,\,\,.\\
\end{array}\right.
$

\noindent {\bf Proof}: 

\begin{eqnarray*}
\sum_{n=0}^{2p-1} a(n) &=& \sum_{n=0}^{2p-1} CT \left[(1-x^2)\left(1+x+\frac{1}{x}\right)^n\right] \\
&=& CT\left[ \frac{(1-x^2)\left(\left(1+x+\frac{1}{x}\right)^{2p}-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&=& CT \left[ \frac{(1-x^2)\left(\left(3+2x+x^2+\frac{2}{x}+\frac{1}{x^2}\right)^{p}-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&=& CT\left[ \frac{(1-x^2)\left(\left(3+2x^p+x^{2p}+\frac{2}{x^p}+\frac{1}{x^{2p}}\right)-1\right)}{1+x+\frac{1}{x}-1}\right]\\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[  \frac{(1-x^2)(1+2x^p)}{1+x^2}\right] \\
&\equiv_p& COEFF_{[x^{2p-1}]} \left[ \frac{1}{1+x^2}\right]  + 2 COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x^2}\right] \\& -&COEFF_{[x^{2p-3}]} \left[ \frac{1}{1+x^2}\right] -2COEFF_{[x^{p-3}]} \left[ \frac{1}{1+x^2}\right]\,. \\
\end{eqnarray*}

\noindent The result follows from Theorem 2 and the last congruence. 

\vskip .2in

\noindent From the above theorems and corollaries, it is easy to observe that partial sums with upper summation limit of the form  $rp-1$ can always be expressed in terms of the sum with upper summation limit $p-1$. This observation leads us to the following simplification of Theorem 2.1 in [1]. 

\vskip .2in

\noindent 
{\bf Theorem 3 }. Let $P(x)$  be a Laurent polynomial in $x$ and let $p$ be a prime.  Let $R(x)$ the denominator after simplifying the expression 
$$
\frac{P(x^p)-1}{P(x)-1}. 
$$

\noindent  Then, for any positive integer $r$ and Laurent polynomial $Q(x)$,

$$
\left( \sum_{n=0}^{rp-1} CT \left[P(x)^nQ(x)\right] \right) \text{mod} \,\, p\,\,,
$$

\noindent is congruent to a $p$-finite sequence and can be expressed as linear combinations of finite terms of coefficients of $\displaystyle{\frac{1}{R(x)}}$.

\vskip .2in

\noindent 
{\bf Theorem 4}. Let $p$ be a prime number and let $r$ be a positive integer.  Let 

$$
A(r,s;p) := \left(\sum_{n=0}^{rp-1}\sum_{m=0}^{sp-1} { n+m \choose m}^2\right) \mod p\,\,.
$$

\vskip .2in
\noindent 
Then,  $A(1,1;p)=\left\{\begin{array}{l}
0 ,\,\,\, \,\,\,\, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,0 \mod 3\\
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
-1 ,\,\,\,   \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$

\vskip .2in
\noindent 
Furthermore,  $\displaystyle{A(2,2;p) \equiv_p COEFF_{[x^{2p-1}y^{2p-1}]} \frac{1+4x^p+4y^p+16x^py^p}{(1+x+xy)(1+y+xy)}}$.\\

\vskip .2in
\noindent 
{\bf{Proof}}: Let  $\displaystyle{P(x,y)=\left(1+y\right)\left(1+\frac{1}{x}\right)}$ and $\displaystyle{ Q(x,y) = \left(1+x\right)\left(1+\frac{1}{y}\right)}$. First observe that 
$$
 { n+m \choose m}^2 =  { n+m \choose m} { n+m \choose n}=CT\left( P(x,y)^n Q(x,y)^m\right)\,\,.
$$

\noindent
Then,

\begin{eqnarray*}
 \sum_{m=0}^{p-1}\sum_{n=0}^{p-1}  { m+n \choose m}^2  &=& \sum_{m=0}^{p-1}\sum_{n=0}^{p-1}  CT\left[ P(x,y) ^nQ(x,y)^m\right]\\
&=&\sum_{m=0}^{p-1} CT\left[\frac{P(x,y)^{p}-1)Q(x,y)^m}{P(x,y)-1}\right] \\
&=&CT\left[\left(\frac{P(x,y)^{p}-1}{P(x,y)-1}\right ) \left(\frac{Q(x,y)^{p}-1}{Q(x,y)-1}\right)\right]
\end{eqnarray*}

\noindent Using $(a+b)^p \equiv_p a^p+b^p$, we can pass to modulo as before

\begin{eqnarray*}
\sum_{m=0}^{p-1}\sum_{n=0}^{p-1}  { m+n \choose m}^2  &\equiv_p&CT\left[\left(\frac{P(x^p,y^p)-1}{P(x,y)-1}\right ) \left(\frac{Q(x^p,y^p)-1}{Q(x,y)-1}\right)\right]\\
&\equiv_p&CT\left[\frac{(1+y^p+x^py^p)(1+x^p+x^py^p)}{(1+y+xy)(1+x+xy)x^{p-1}y^{p-1}}\right]\\
&\equiv_p&COEFF_{[x^{p-1}y^{p-1}]}\left[\frac{(1+y^p+x^py^p)(1+x^p+x^py^p)}{(1+y+xy)(1+x+xy)}\right]\\
&\equiv_p&COEFF_{[x^{p-1}y^{p-1}]}\left[\frac{1}{(1+y+xy)(1+x+xy)}\right]\\
\end{eqnarray*}


\noindent
Using the Apagodu-Zeilberger algorithm, the diagonal coefficients satisfy the recurrence $N^2+N+1=0$  with the initial conditions $a(0)=1,a(1)=1, a(2)=0$. The result now follows from the fact that this recurrence is equivalent to $N^3-1=0$ and the solution to this recurrence: \\

\noindent 
$$
a(n)=\left\{\begin{array}{l}
1 ,\,\,\, \,\,\,\, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,0 \mod 3\\
1 ,\,\,\, \,\,\, \, \,\text{if} \,\,\,p\,\,\,\,\equiv \,\,1 \mod  3\\
0 ,\,\,\, \,\,\, \, \,  \text{if} \,\,\,p\,\,\,\,\equiv\,\, 2 \mod 3\,\,\,.\\
\end{array}\right.
$$

\noindent  Note that our partial sum is congruent to $a(p-1)$ for any prime $p$.

\vskip .2in

\noindent 
Finally, for $A(2,2;p)$ we have,  

\begin{eqnarray*}
\sum_{m=0}^{2p-1}\sum_{n=0}^{2p-1}  { m+n \choose m}^2  &\equiv_p&CT\left[\left(\frac{P(x^p,y^p)^2-1}{P(x,y)-1}\right ) \left(\frac{Q(x^p,y^p)^2-1}{Q(x,y)-1}\right)\right]\\
&\equiv_p&CT\left[\frac{(1+y^p+x^py^p)^2(1+x^p+x^py^p)^2}{(1+y+xy)(1+x+xy)x^{p-1}y^{p-1}}\right]\\
&\equiv_p&COEFF_{[x^{2p-1}y^{2p-1}]}\left[\frac{(1+y^p+x^py^p)^2(1+x^p+x^py^p)^2}{(1+y+xy)(1+x+xy)}\right]\\
&\equiv_p&COEFF_{[x^{2p-1}y^{2p-1}]}\left[\frac{1+4x^p+4y^p+16x^py^p}{(1+x+xy)(1+y+xy)}\right]\\
\end{eqnarray*}

\noindent It follows that 

$$\displaystyle{A(2,2;p) \equiv_p   COEFF_{[x^{2p-1}y^{2p-1}]} \frac{1+4x^p+4y^p+16x^py^p}{(1+x+xy)(1+y+xy)}}\,\,.$$

\noindent By symmetry, it simplifies to  

$$
A(2,2;p) \equiv_p COEFF_{[x^{2p-1}y^{2p-1}]} \frac{1}{(1+x+xy)(1+y+xy)} +
$$ 
$$
8COEFF_{[x^{p-1}y^{2p-1}]} \frac{1}{(1+x+xy)(1+y+xy)}+ 16COEFF_{[x^{p-1}y^{p-1}]} \frac{1}{(1+x+xy)(1+y+xy)}
$$

\vskip .2in

\noindent {\bf Remark}: If we take the third power of the summand in Theorem 4 and define 

$$
C(r,s;p):=\left(\sum_{n=0}^{rp-1}\sum_{m=0}^{sp-1} { n+m \choose m}^3\right) \mod p\,\,.
$$

\noindent  then, 

$$
 { n+m \choose m}^3 =  CT \left[ \frac{(1+x)^{m+n}}{x^m}\frac{ (1+y)^{m+n}}{y^m}\frac{ (1+z)^{m+n}}{z^n}\right]\,\,.
$$

\noindent and if we let  $\displaystyle{P(x,y,z)=\left(1+\frac{1}{x}\right)\left(1+\frac{1}{y}\right)\left(1+z\right)}$ and $\displaystyle{ Q(x,y,z) = \left(1+x\right)\left(1+y\right)\left(1+\frac{1}{z}\right)}$, then we have 

$$
 { n+m \choose m}^3 =  CT\left(( P(x,y)^m Q(x,y)^n\right)\,\,.
$$

\noindent Repeating the above arguement verbatim, we get

$$
C(1,1;p) \equiv_p COEFF_{[x^{p-1}y^{p-1}z^{p-1}]}\left[\frac{1}{p(x,y,z)q(x,y,z)}\right],
$$

\vskip .2in
\noindent where $p(x,y,z)=1+x+y+xy+xz+yz+xyz$ and $q(x,y,z)=1+y+z+xy+xz+yz+xyz$.  

\vskip .2in

\noindent {\bf Theorem 5}.  Let $p>2 $ be prime, and $r, s$ and $t$ be positive integers. Let

$$
A(r,s,t;p):=\sum_{m_1=0}^{rp-1}\sum_{m_2=0}^{sp-1} \sum_{m_3=0}^{tp-1} { m_1+m_2+m_3 \choose m_1,m_2,m_3}   \,\,.
$$

\noindent  Then,   $\displaystyle{A(1,1,1;p) \equiv_p 1}$.    \\

\noindent 
{\bf Proof}:  Observe that  

$$
 { m_1+m_2+m_3 \choose m_1,m_2,m_3}  = CT\left[\frac{ \left(1+x+y+z\right)^{m_1+m_2+m_3}}{x^{m_1}y^{m_2}z^{m_3}}\right]
$$

\noindent  Using $(x+y)^p\equiv_p x^p + y^p$ and routine algebra, we get

\begin{eqnarray*}
\sum_{m1=0}^{p-1}\sum_{m2=0}^{p-1} \sum_{m_3=0}^{p-1} { m_1+m_2+m_3 \choose m_1,m_2,m_3}   &= &  \sum_{m_1=0}^{p-1}\sum_{m_2=0}^{p-1} \sum_{m_3=0}^{p-1} CT\left[\frac{ \left(1+x+y+z\right)^{m_1+m_1+m_3}}{x^{m_1}y^{m_2}z^{m_3}}\right]\\
&\equiv_p& CT\frac{(1+x^py^p+x^pz^p)(1+y^px^p+y^pz^p)(1+z^px^p+z^py^p)}{(xyz)^{p-1}(1+x+y)(1+x+z)(1+y+z)}\\
&\equiv_p& COEFF_{[x^{p-1}y^{p-1} z^{p-1}]}  \frac{1}{(1+x+y)(1+x+z)(1+y+z)}\\
\end{eqnarray*}

\vskip .1in

\noindent Using Apagodu-Zeilberger algorithm, the diagonal coefficients, $a(n):=a(n,n,n)$, satisfy the recurrence  

$$
24(5n+11)(3n+5)(3n+4)a(n)+(295n^3+1614n^2+2855n+1620)a(n+1)
$$

$$
+2(2n+5)(n+2)(5n+6)a(n+2)=0\,\,.
$$

\vskip .1in

\noindent Passing to mod p, the terms with powers of $p$ are zero and the recurrence reduces to the much simpler second order recurrence, 

$$
288a(p)+84a(p+1)+6a(p+2)=0
$$ 

\vskip .2in

\noindent with initial conditions  $a(0)=1$ and $a(1)=-14$, whose solution is given by 

$$
a(p)\equiv_p 4(-8)^p-3(-6)^p\,\,.
$$

\vskip .2in

\noindent From the above equation, we know that  $A(1,1,1;p) \equiv a(p-1)$ (mod p).  Thus, 

$$
A(1,1,1;p)=a(p-1) \equiv_p  4(-8)^{p-1} - 3 (-6)^{p-1} \equiv_p 2^{p-1} \,.
$$. 

\noindent  Now it suffices to show that $2^{p-1}-1 \equiv_p 0$.  But this follows fom 

$$
2^{p-1}-1 = \frac{1}{2}(2^p-2) = \frac{1}{2}((1+1)^p-2) \equiv_p \frac{1}{2}(1+1-2)=0\,\,.  
$$

\vskip .2in

\noindent Computer evidences suggest the following conjectures\\

\noindent {\bf Conjecture 1}: $\displaystyle{A(1,1,1;p) \equiv_{p^{\alpha}} 1}$  for $\alpha =2,3$.\\

\noindent {\bf Conjecture 2}: The above  computer data suggests that $\displaystyle{A(2,2,2;p) \equiv_{p^\alpha} 16}$  for $p\geq 17$ and $\alpha = 1, 2, 3$ 

\vskip .2in

\noindent For the general case,  if we denote, 

$$
A(r_1,r_2,\ldots ,r_a;p):=\sum_{m_1=0}^{r_1p-1}\sum_{m_2=0}^{r_2p-1}\ldots  \sum_{m_a=0}^{r_ap-1} { m_1+m_2\ldots+m_a \choose m_1,m_2,\ldots,m_a}   \,\,.
$$

\noindent Then,  one can show that 
$\displaystyle{A(1,1,\ldots,1;p) \equiv_p Coeff_{[x_1^{p-1}x_2^{p-1} \ldots x_a^{p-1}]} \frac{1}{\prod_{j=1}^{a} (1+\sum_{i =1, i\neq j}^{a}x_i)} }$.\\

\noindent {\bf{Proof}} (of i) :  Observe that  

$$
 { m_1+m_2\ldots+m_a \choose m_1,m_2,\ldots,m_a}   = CT\left[\frac{ \left(1+x_1+x_2+\ldots +x_a\right)^{m_1+m_2+\ldots+m_a}}
 {\prod_{i=1}^{a}x_i^{m_i}}\right]
$$

\vskip .2in

\noindent  As in the proof of Theorem 4, 

\begin{eqnarray*}
\sum_{m_1=0}^{p-1}\ldots  \sum_{m_a=0}^{p-1} { m_1+m_2\ldots+m_a \choose m_1,m_2,\ldots,m_a}    &= &  
\sum_{m_1=0}^{p-1}\ldots  \sum_{m_a=0}^{p-1} CT \left[\frac{ \left(1+x_1+x_2+\ldots +x_a\right)^{\sum_{j=1}^{a}m_j}} {\prod_{i=1}^{a}x_i^{m_i}}\right]\\
 &\equiv_p& COEFF_{[x_1^{p-1}x_2^{p-1} \ldots x_a^{p-1}]} \frac{1}{\prod_{j=1}^{a} \left(1+\sum_{i =1, i\neq j}^{a}x_i\right)} .\\
\end{eqnarray*}

\noindent Computer evidence suggests that\\

\noindent  {\bf Conjecture 3}: $\displaystyle{A(1,1,\ldots,1;p) \equiv_{p^{\alpha}} 1}$ for $p>2$  and $\alpha = 1, 2,3$.\\

\vskip .2in
\noindent {\bf Ap$\acute{e}$ry Numbers}:\\

\noindent As our last example, we consider one of the most intriguing sequence, the Apery numbers, defined by 

$$
A(n):=\sum_{k=0}^{n} { n \choose k}^2 {n+k \choose k}^2
$$

\noindent Many people have studied arithmetic propertites of this sequence . We mention two  results derived by F.  Beukers [3]: 

$$
A(mp^r)\equiv A(mp^{r-1})   \,\,(\text{mod}\,\,p^{3r})\,\,,
$$

\noindent for  prime $p\geq 5$ and positive integr $r$ and 
$$
A \left( \frac{p-1}{2} \right) \equiv  \sum_{k=0}^{p-1} {2k \choose k}^4 2^{-8k} \equiv \gamma(p) \pmod{p},
$$

\noindent and
$$
\sum_{j=1}^{\infty} \gamma(n)q^n = q \prod_{n=1}^\infty (1-q^{2n})^4 (1-q^{4n})^4.
$$

\noindent Here we will aproach the problem from our angle. It is known that [see [4]) that 

$$
A(n)= CT\left[ \left(\frac{(1+x)(1+y)(1+z)(1+y+z+yz+xyz)}{xyz}\right)^n\right] 
$$

\noindent Let $p$ be a prime number and define 

$$
a(p):=\sum_{n=0}^{p-1}A(n)\,\,.
$$ 

\noindent We can express  $a(p)$ as 

\begin{eqnarray*}
\sum_{n=0}^{p-1}\sum_{k=0}^{n} { n \choose k}^2 {n+k \choose k}^2 &=& \sum_{n=0}^{p-1} CT\left[ \left(\frac{(1+x)(1+y)(1+z)(1+y+z+yz+xyz)}{xyz}\right)^n\right] \\
&=& CT \left[R1(x,y,z)+R2(x,y,z)\right]\\
&=&CT\left[\frac{R1(x,y,z)}{x^{p-1}y^{p-1}z^{p-1}}\right]\\
&=&CT\left[\frac{P(x,y,z)}{x^{p-1}y^{p-1}z^{p-1}Q(x,y,z)}\right]\\
&\equiv_p&COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} \frac{P(x^p,y^p,z^p)}{Q(x,y,z)}\\
&\equiv_p& COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} \left[\frac{1}{Q(x,y,z)}\right]\\
\end{eqnarray*}

\noindent where,  $R2(x,y,z)=\frac{xyz}{Q(x,y,z)}$ and has zero constant term and  $R1(x,y,z)= \frac{P(x,y,z)}{Q(x,y,z)}$, where

$$
P(x,y,z) = (x+1)^p(y+1)^p(1+z)^p((1+y+z+yz+xyz)^p
$$

\noindent and 

$$
Q(x,y,z) = x^2y^2z^2+x^2y^2z+x^2yz^2+2xy^2z^2+x^2yz+3xy^2z+3xyz^2+y^2z^2+xy^2
$$
$$
+4xyz+xz^2+2y^2z+2yz^2+2xy+2xz+y^2+4yz+z^2+x+2y+2z+1\,\,.
$$

\noindent  Therefore, 

$$
a(p) \equiv \alpha (p-1,p-1,p-1) (\text{mod}\,\, p)
$$

\noindent where 

$$
Q(x,y,z)=\sum_{m,n,k} \alpha(m,n,k) x^ny^mz^k\,\, .
$$

\vskip .2in

\noindent 
{\bf {Theorem 6}}:  Let  $P(x,y,z)$ and $Q(x,y,z)$ be Laurent polynomials in $x,y$ and $z$.  Let  $T(x,y,z)$ be the denominator (after clearing!) of 

$$
\frac{(P(x^p,y^p,z^p)-1)(Q(x^p,y^p,z^p)-1)}{(P(x,y,z)-1)(Q(x,y,z)-1)}\,\,.
$$

\noindent Then, for a prime $p$,  Laurent polynomial $R(x,y,z)$,  and positive integers $r,s,t$,

$$
\left(\sum_{k=0}^{rp-1}\sum_{n=0}^{sp-1}\sum_{n=0}^{tp-1}  CT\left(P(x,y,z)^nQ(x,y,z)^kR(x,y,z)\right)\ \right)\,\,\,\text{mod} \,\, p
$$

\noindent is congruent to a $P$-finite sequence and can be expressed as a finite linear combination of coefficients of  
$\displaystyle{\frac{1}{T(x,y,z)}}$.

\vskip .2in

\noindent {\bf Remark}: Theorem 3 and Theorem 6 will be implemented to automated discovery and Proof of congruence theorems for partial sums, a multivariable analog analog of [6],  in a forth coming article by the first author. Stay tunes. \\
\begin{thebibliography}{1}

\bibitem{Ahl00}
S.~Ahlgreen and K.~Ono.
\newblock A Gaussian hypergeometric series evaluation and Ap\'{e}ry number congruences.
\newblock {\em Journal fur die Reine und Angewandte Mathematik}, pages
  187--212, 2000.

\bibitem{AZ}
M. ~Apagodu and D. ~Zeilberger, Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory, Adv. Appl. Math. 37(2006).


\bibitem{Beu87}
F.~Beukers.
\newblock Another congruence for the Ap{\'e}ry numbers.
\newblock {\em Journal of Number Theory}, 25(2):201--210, 1987.

\bibitem{Row14}
E.~Rowland and D.~Zeilberger.
\newblock A case study in meta-automation: automatic generation of congruence
  automata for combinatorial sequences.
\newblock {\em Journal of Difference Equations and Applications},
  20(7):973--988, 2014.

\bibitem{Sun14}
Z.-W.~Sun.
\newblock Congruences involving generalized central trinomial coefficients.
\newblock {\em Science China Mathematics}, 57(7):1375--1400, 2014.

\bibitem{CHZ} 
 William Y.C. Chen, Qing-Hu Hou, and D. ~Zeilberger, Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial Sequences, J. of Difference Equations and Applications (on-line), 
DOI:10.1080/10236198.2016.1142541.

\end{thebibliography}

\end{document} 



