%apa.tex: Using the ``Freshman's Dream'' Identity to  Prove  Combinatorial Congruences 
%by Moa Apagodu
%Plain TeX
%begin macros
\def\L{{\cal L}}
\baselineskip=14pt
\parskip=10pt
\def\halmos{\hbox{\vrule height0.15cm width0.01cm\vbox{\hrule height
  0.01cm width0.2cm \vskip0.15cm \hrule height 0.01cm width0.2cm}\vrule
  height0.15cm width 0.01cm}}
\font\eightrm=cmr8 \font\sixrm=cmr6
\font\eighttt=cmtt8
\magnification=\magstephalf
\def\W{{\cal W}}
\def\P{{\cal P}}
\def\Q{{\cal Q}}
\def\1{{\overline{1}}}
\def\2{{\overline{2}}}
\parindent=0pt
\overfullrule=0in
\def\Tilde{\char126\relax}
\def\frac#1#2{{#1 \over #2}}
%\headline={\rm  \ifodd\pageno  \RightHead  \else  \LeftHead  \fi}
%\def\RightHead{\centerline{
%Title
%}}
%\def\LeftHead{ \centerline{Doron Zeilberger}}
%end macros

\bf
\centerline
{
Using the ``Freshman's Dream'' Identity to  Prove  Combinatorial Congruences 
}
\rm
\bigskip
\centerline
{\it By Moa APAGODU}

{\bf Abstract.}
In a recent beautiful but technical article, William Y.C. Chen, Qing-Hu Hou, 
and Doron Zeilberger  developed an algorithm for finding and proving congruence identities (modulo primes)
of indefinite sums of many combinatorial sequences, namely those (like the Catalan and Motzkin sequences)
that are expressible in terms of constant terms of powers of Laurent polynomials.
We first give a leisurely exposition of their elementary but brilliant approach, and then  extend it in two directions. 
The Laurent polynomials may be of several variables, 
and instead of single sums we have multiple sums. In fact we even combine these two generalizations!

{\bf Introduction}

In a recent elegant article ([CHZ]) the following type of quantities were considered

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

where 

$\bullet$  $a(k)$ is a combinatorial sequence, expressible as the constant term of a power of a Laurent polynomial of a {\bf single} variable
(for example, the central binomial coefficient ${2k \choose k}$ is the coefficient of $x^0$ in $(x+ \frac{1}{x})^{2k}$) .

$\bullet$ $r$ is a specific positive integer .

$\bullet$ $p$ is an arbitrary prime .

Let  $x \equiv_p y$ mean $x \, \equiv \, y \,\,(\hbox{mod} \,\, p)$, in other words, that $x-y$ is divisible by $p$.

The [CHZ] method, while ingenious, is very elementary! The main ``trick'' is:

{\bf The Freshman's Dream Identity} ([Wi]): $(a+b)^p \equiv_p a^p + b^p$ \quad .

Recall that the easy proof follows from the Binomial Theorem, and noting that ${p \choose k}$ is divisible by $p$ except when
$k=0$ and $k=p$. This also leads to one of the many proofs of the {\bf grandmother} of all congruences, {\bf Fermat's Little Theorem},
$a^p  \equiv_p a$,  by  starting with  $0^p  \equiv_p 0$,  and applying induction to $(a+1)^p \equiv_p a^p + 1^p$.

The second ingredient  in the [CHZ] method is even more elementary! It is:

{\bf Sum of a Geometric Series}:
$$
\sum_{i=0}^{n-1} z^i = \frac{z^n \, - \, 1}{z \, - \,1} \quad .
$$

The focus in the Chen-Hou-Zeilberger ([CHZ]) paper was both computer-algebra implementation, and proving a general theorem
about a wide class of sums.
Their paper is rather technical, and hence its beauty  is lost to a wider audience.
Hence the first purpose of the present article is to give a  leisurely introduction to their method, and
illustrate it with numerous illuminating examples. The second, main, purpose, however, is to extend the method
in {\bf two} directions. The summand $a(k)$, may be the constant term of a Laurent polynomial of {\bf several} variables,
and instead of a {\bf single} summation sign, we can have {\it multi-sums}. In fact we can combine these two!

{\bf Notation}

The constant term of a Laurent polynomial $P(x_1,x_2,\ldots,x_n)$, alias
the coefficient of $x_1^0x_2^0..x_n^0$, is denoted by $CT[P(x_1,x_2,\ldots,x_n)]$.
The general coefficient of 
$x_1^{m_1}x_2^{m_2}..x_n^{m_n}$ in $P(x_1,x_2,\ldots,x_n)$ is denoted by 
$COEFF_{[x_1^{m_1}x_2^{m_2}..x_n^{m_n}]}P(x_1,x_2,\ldots,x_n)$. For example, 
$$
CT\left[ \frac{1}{xy}+3+5xy-x^3+6y^2\right]=3 \quad , \quad
COEFF_{[xy]}\left[ \frac{1}{xy}+3+5xy+x^3+6y^2\right]=5.
$$

We use the symmetric representation of integers in $(-p/2, p/2]$ when reducing modulo a prime $p$. 
For example,  6 mod $5=1$ and 4 mod $5 =-1$. 

{\bf Review of the Chen-Hou-Zeilberger Single Variable Case}

In order to motivate our generalization, we will first review, in more detail than given in [CHZ], some
of their elegant results. 
Let's start with the {\bf Central Binomial Coefficients},  sequence  A000984 in the great OEIS ([Sl], https://oeis.org/A000984).

{\bf Proposition 1}. For any prime $p \geq 5$ 
$$
\sum_{n=0}^{p-1} { 2n \choose n} \, \,
\equiv_p  \,\,
\cases{
1 ,& if \quad  $p \equiv 1 \, (mod \,\, 3)$ ;\cr
-1 ,& if \quad  $p \equiv 2 \, (mod \,\, 3)$ .\cr}   
$$

{\bf Proof}: Using the fact that 
$$
{ 2n \choose n} = CT\left[ \frac{(1+x)^{2n}}{x^n} \right] \quad ,
$$
and the Freshman's Dream identity, $(a+b)^p\equiv_p a^p+b^p$, we have
$$
\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{2^p+x^{p}+\frac{1}{x^p}-1}{1+x+\frac{1}{x}}\right] \quad (\hbox{By Freshman's Dream})
$$
$$
\equiv_p CT \left[ \frac{2+x^{p}+\frac{1}{x^p}-1}{1+x+\frac{1}{x}}\right](\hbox{By Fermat's little theorem})
$$
$$
= CT \left[ \frac{1+x^{p}+\frac{1}{x^p}}{1+x+\frac{1}{x}}\right]
\,= \,CT\left[ \frac{1+x^p+x^{2p}}{(1+x+x^2)x^{p-1}}\right]
= COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right]
$$
$$
= COEFF_{[x^{p-1}]} \left[ \frac{1-x}{1-x^3}\right]\,
= COEFF_{[x^{p}]} \left ( \, \sum_{i=0}^{\infty} x^{3i+1} \,\right ) \, + \, 
 COEFF_{[x^{p}]} \left ( \, \sum_{i=0}^{\infty} (-1) \cdot x^{3i+2} \, \right) \quad .
$$
The result follows from extracting the coefficient of $x^p$ in the above geometrical series.


{\bf Proposition 1'} 
$$
\sum_{n=0}^{2p-1} { 2n \choose n} \,\,
\equiv_p \,\,
\cases{
3 ,& if \quad  $p \equiv 1 \, (mod \,\, 3)$ ;\cr
-3 ,& if \quad  $p \equiv 2 \, (mod \,\, 3)$ .\cr}   \quad,
$$

{\bf Proof}: 
$$
\sum_{n=0}^{2p-1} {2n \choose n} = \sum_{n=0}^{2p-1} CT \left[ \left(  2+x+\frac{1}{x} \right)^n\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]
$$
$$
\,=\, COEFF_{[x^{2p-1}]} \left[  \frac{1+4x^p}{1+x+x^2}\right]
\,=\, COEFF_{[x^{2p-1}]} \left[ \frac{1}{1+x+x^2}\right]  +4 \cdot COEFF_{[x^{p-1}]} \left[ \frac{1}{1+x+x^2}\right] 
$$
$$
\, = \,COEFF_{[x^{2p-1}]} \left[ \frac{1-x}{1-x^3}  \right]  +4 \cdot COEFF_{[x^{p-1}]} \left[ \frac{1-x}{1-x^3}\right] 
$$
$$
= \, COEFF_{[x^{2p-1}]} \left[ \frac{1}{1-x^3}  \right]  + COEFF_{[x^{2p-1}]} \left[ \frac{-x}{1-x^3}  \right]  
+4 \cdot COEFF_{[x^{p-1}]} \left[ \frac{1}{1-x^3}\right]  +4 \cdot COEFF_{[x^{p-1}]} \left[ \frac{-x}{1-x^3}\right] \,\,
$$
$$
=COEFF_{[x^{2p}]} \left[ \sum_{i=0}^{\infty} x^{3i+1}  \right]  + COEFF_{[x^{2p}]} \left[  \sum_{i=0}^{\infty} (-1) \cdot x^{3i+2} \right]  
$$
$$
+4 \cdot COEFF_{[x^{p}]} \left[   \sum_{i=0}^{\infty} x^{3i+1} \right]  +4 \cdot COEFF_{[x^{p}]} \left[   \sum_{i=0}^{\infty} (-1) \cdot x^{3i+2} \right] \,\,
$$
The result follows from extracting the coefficients of $x^{2p}$ in the first two geometrical series above,
and the coefficient of $x^p$ in the last two.

The same method (of [CHZ]) can be used to find the `mod $p$' of $\sum_{n=0}^{rp-1} { 2n \choose n}$ for {\bf any}
{\it specific} positive integer $r$. This lead to the following conjecture, that we (rigorously) proved (with a computer) for
$r\leq 10$. We believe that the same method can be used to handle it when $r$ is left general, but we
prefer to leave it as a challenge to our readers.

{\bf Conjecture 1''}  For any priem $p \geq 5$, and any positive integer, $r$, 
$$
\sum_{n=0}^{rp-1} { 2n \choose n} \,\,
\equiv_p \,\,
\cases{
\alpha_r ,& if \quad  $p \equiv 1 \, (mod \,\, 3)$ ;\cr
-\alpha_r ,& if \quad  $p \equiv 2 \, (mod \,\, 3)$ ,\cr}   
$$
where
$$
\alpha_r \, = \, \sum_{n=0}^{r-1} {{2n} \choose {n}}
$$
For the record, here are the first ten terms of the integer sequence $\alpha_r$:
$$
[1,3,9,29,99,351,1275,4707,17577,66187] \quad .
$$
To our surprise, at this time of writing (June 9, 2016), the sequence $\alpha_r$ is not (yet) in the OEIS,
but $\alpha_r-1$ is Sequence A066796 [[Sl],{\tt https://oeis.org/A066796}].
Note that $\alpha_r$ is the number of ways of tossing a coin $<2r$ times
and getting at many Heads as Tails (including tossing it $0$ times, while $\alpha_r-1$ excludes the
lazy option of doing nothing).


The most {\it ubiquitous} sequence in combinatorics is sequence A000108 in the great OEIS \hfill\break
([Sl], {\tt https://oeis.org/A000108}, that according to Neil Sloane is the longest entry!), the
super-famous {\it Catalan Numbers}, $C_n:=(2n)!/(n!(n+1)!$, that count
{\it zillions} of combinatorial families (see [St] for some of the more interesting ones)

{\bf Proposition 2}: Let $C_n$ be the Catalan Numbers,  then,  for every prime $p \geq 5$,
$$
\sum_{n=0}^{p-1}  C_n \,\,
\equiv_p \,\,
\cases{
1 ,& if \quad  $p \equiv 1 \, (mod \,\, 3)$ ;\cr
-2 ,& if \quad  $p \equiv 2 \, (mod \,\, 3)$ .\cr}   \quad,
$$


{\bf Proof}:  Since  $C_n={{2n} \choose {n}} - {{2n} \choose {n-1}}$, it
is readily seen that $C_n=CT[(1-x)(\frac{1}{2+x+\frac{1}{x}})^{n}]$.
We have
$$
\sum_{n=0}^{p-1}  C_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]
\, = \, COEFF_{[x^{p-1}]} \left[  \frac{1-x}{1+x+x^2}\right] \, = \, COEFF_{[x^{p-1}]} \left[  \frac{(1-x)^2}{1-x^3}\right]
$$

$$
=  COEFF_{[x^{p}]} \left[  \frac{x}{1-x^3}\right]
+COEFF_{[x^{p}]} \left[  \frac{-2x^2}{1-x^3}\right]
+COEFF_{[x^{p}]} \left[  \frac{x^3}{1-x^3}\right]
$$
$$
=  COEFF_{[x^{p}]} \left[  \sum_{i=0}^{\infty} 1 \cdot x^{3i+1}  \right]
+COEFF_{[x^{p}]} \left[    \sum_{i=0}^{\infty} (-2) \cdot x^{3i+2}   \right]
+COEFF_{[x^{p}]} \left[   \sum_{i=0}^{\infty} 1 \cdot x^{3i+3} \right] \quad ,
$$
and the result follows from extracting the coefficient of $x^p$ from the first or second geometric series above
(note that we would never have to use the third geometrical series, if $p>3$).


The same method (of [CHZ]) can be used to find the `mod $p$' of $\sum_{n=0}^{rp-1} C_n$ for {\bf any}
{\it specific} positive integer $r$. This lead to the following conjecture, that we (rigorously) proved (with a computer) for
$r\leq 10$. We believe that the same method can be used to handle it when $r$ is left general, but we
prefer to leave it as a challenge to our readers.

{\bf Conjecture 2'}: Let $C_n$ be the Catalan Numbers,  then,  for any positive integer $r$, there 
$$
\sum_{n=0}^{rp-1}  C_n \,\,
\equiv_p \,\,
\cases{
\beta_r ,& if \quad  $p \equiv 1 \, (mod \,\, 3)$ ;\cr
-\gamma_r ,& if \quad  $p \equiv 2 \, (mod \,\, 3)$ ,\cr}   
$$
where

$$
\beta_r = \sum_{n=0}^{r-1} C_n \quad, \quad
\gamma_r = \sum_{n=0}^{r-1} (3n+2)C_n \quad .
$$

For the record, the first ten terms of the sequence of integer pairs $[\beta_r, -\gamma_r]$ are
$$
[ [1,-2], [2,-7], [4,-23], [9,-78], [23,-274], [65, -988], [197, -3628], [626,-13495], [2076,-50675], [6918, -191673]] \quad .
$$
We note that the sequence $\beta_r$ is sequence A014137 in the OEIS ([Sl], {\tt https://oeis.org/A014137})
but at this time of writing (June 9, 2016), the sequence $\gamma_r$ is not there (yet).

Not as famous as the Catalan numbers, but not exactly obscure, are the {\it Motzkin numbers}, $M_n$,
sequence A001006 in the great OEIS ([Sl],  {\tt https://oeis.org/A001006}), that may be defined by the
constant term formula
$$
M_n= CT \left [ \displaystyle{(1-x^2)\left(1+x+\frac{1}{x}\right)^n} \right ] \quad .
$$

{\bf Proposition 3}:   Let $M_n$ be the Motzkin numbers, then for any prime $p \geq 3$, we have
$$
\sum_{n=0}^{p-1}  M_n  \,
\equiv_p  \,\,
\cases{
2 ,& if \quad  $p \equiv 1 \, (mod \,\, 4)$ ;\cr
-2 ,& if \quad  $p \equiv 3 \, (mod \,\, 4)$ .\cr}   
$$

{\bf Proof}: 
$$
\sum_{n=0}^{p-1} M_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  \, CT \left[ \frac{(1-x^2)\left( 1+x^p+\frac{1}{x^p}-1 \right)}{1+x+\frac{1}{x}-1}\right]
\, = \,   CT \left[ \frac{(1-x^2)\left( x^p+\frac{1}{x^p} \right)}{x+\frac{1}{x}}\right]
\, = \,   CT \left[ \frac{x(1-x^2)\left( x^p+\frac{1}{x^p} \right)}{1+x^2}\right]
$$
$$
= COEFF_{[x^{p-1}]} \left[  \frac{1-x^2}{1+x^2}\right]
= COEFF_{[x^{p}]} \left[ \frac{x}{1+x^2}\right]  -  COEFF_{[x^{p}]} \left[ \frac{x^3}{1+x^2}\right] \quad .
$$
$$
= COEFF_{[x^{p}]} \left[ \sum_{i=0}^{\infty} (-1)^i x^{2i+1} \right]  
+ COEFF_{[x^{p}]} \left[   \sum_{i=0}^{\infty} (-1)^{i+1} x^{2i+3} \right] \quad ,
$$
and the result follows from extracting the coefficient of $x^p$ from the first and second geometric series above,
by noting that when $p \equiv \,1 \, (mod \,\, 4)$ $i$ is even in the first series, and odd in the second one, and
vice-versa when  $p \equiv \,1 \, (mod \,\, 4)$.

The same method yieds

{\bf Conjecture 3'}:  Let $M_n$ be the Motzkin numbers, and let
$p \geq 3$ be prime, then for any positive integer $r$, there exists an integer $\delta_r$ such that
$$
\sum_{n=0}^{rp-1}  M_n  \,
\equiv_p 
\cases{
\delta_r ,& if \quad  $p \equiv 1 \, (mod \,\, 4)$ ;\cr
-\delta_r ,& if \quad  $p \equiv 3 \, (mod \,\, 4)$ .\cr}   
$$

Using the present method ([CHZ]) we rigorously proved that the first ten terms of the integer sequence $\delta_r$ are
$$
[2,4,10,24,62,164,446,1232,3446,9724] \quad .
$$
At this time of writing (June 9, 2016), the sequence $\delta_r$ is not (yet) in the OEIS.

{\bf Challenge:} Can you find an expression for $\delta_r$ in terms of $r$?

From the above  proofs, it is easy to observe that partial sums with upper summation limit of the form  $rp-1$, for $r >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 [CHZ]. 


{\bf Theorem 4}. Let $P(x)$  be a Laurent polynomial in $x$ and let $p$ be a prime.  Let $R(x)$ be the denominator, after clearing, of the expression 
$$
\frac{P(x^p)-1}{P(x)-1}. 
$$
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) \hbox{mod} \,\, p\,\,,
$$

is congruent to a finite linear combination of shifts of the sequence of coefficients of the rational function $\displaystyle{\frac{1}{R(x)}}$.


{\bf Multi-Sums and Multi-Variable}

We now go to the {\it new} material.

{\bf Proposition 5}. Let $p \geq 5$ be a prime number, then
$$
\sum_{n=0}^{p-1}\sum_{m=0}^{p-1} { n+m \choose m}^2\,\,
\equiv_p \,\,
\cases{
1 ,& if \quad  $p \equiv 1 \, (mod \,\, 3)$ ;\cr
-1 ,& if \quad  $p \equiv 2 \, (mod \,\, 3)$ .\cr}  
$$

{\bf{Proof}}: Let  
$$
P(x,y)=\left(1+y\right)\left(1+\frac{1}{x}\right)
$$
and 
$$
Q(x,y) = \left(1+x\right)\left(1+\frac{1}{y}\right)
$$
Then
$$
 { n+m \choose m}^2 =  { n+m \choose m} { n+m \choose n}=CT \left[ P(x,y)^n Q(x,y)^m\right]\,\,.
$$
We have
$$
\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] \quad .
$$

Using the Freshman's Dream ($(a+b)^p \equiv (a^p+b^p)\,\hbox{mod}\,p$), we can pass to mod $p$ as above, we get
$$
\sum_{m=0}^{p-1}\sum_{n=0}^{p-1}  { m+n \choose m}^2  \equiv_pCT\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] \quad .
$$
It is possible to show that the coefficient of $x^ny^n$ in the Maclaurin expansion of the rational function
$\frac{1}{(1+y+xy)(1+x+xy)}$ is $1$ when $n$ is a multiple of $3$ and $0$ otherwise.
One way is to do a partial-fraction decomposition, and extract the coefficient of $x^n$, getting
a certain expression in $y$ and $n$, and then extracting the coefficient of $y^n$.
Another way is by using the Apagodu-Zeilberger algorithm ([AZ]), the yields that 
the diagonal coefficients satisfy the recurrence equation 
$a(n+2)+a(n+1)+a(n)=0$  with initial 
conditions $a(0)=1,a(1)=-1$. 

Based on computer calculations, we conjecture 

{\bf Conjecture 5'}. For any prime $p \geq 5$, and any pair of positive integers, $r$, $s$, we have
$$
\sum_{n=0}^{rp-1}\sum_{m=0}^{sp-1} { n+m \choose m}^2\,\,
\equiv_p \,\,
\cases{
\epsilon_{rs} ,& if \quad  $p \equiv 1 \, (mod \,\, 3)$ ;\cr
-\epsilon_{rs} ,& if \quad  $p \equiv 2 \, (mod \,\, 3)$ ,\cr}  
$$
where
$$
\epsilon_{rs} =\sum_{m=0}^{r-1} \sum_{n=0}^{s-1}  { n+m \choose m}^2 \quad .
$$

We finally consider partial sums of {\it trinomial coefficients}.

{\bf Proposition 6}.  Let $p>2 $ be prime, 
$$
\sum_{m_1=0}^{p-1}\sum_{m_2=0}^{p-1} \sum_{m_3=0}^{p-1} { m_1+m_2+m_3 \choose m_1,m_2,m_3}  \, \equiv_p 1 \, \,\, .
$$

{\bf Proof}: First observe that 
${ m_1+m_2+m_3 \choose m_1,m_2,m_3}= CT \left[\frac{(x+y+z)^{m_1+m_2+m_3}}{x^{m_1}y^{m_2}z^{m_3}}\right]$.

Hence
$$
\sum_{0 \leq m_1, m_2, m_3 \leq p-1}{ m_1+m_2+m_3 \choose m_1,m_2,m_3}  = \sum_{0 \leq m_1, m_2, m_3 \leq p-1} 
CT \left[(x+y+z)^{m_1+m_2+m_3}/(x^{m_1}y^{m_2}z^{m_3}) \right]
$$
$$
= CT\left[\sum_{0 \leq m_1, m_2, m_3 \leq p-1}\frac{ (x+y+z)^{m_1+m_2+m_3}}{x^{m_1}y^{m_2}z^{m_3}}\right]
$$
$$
= CT \left[
\left ( \sum_{m_1=0}^{p-1} \left(\frac{x+y+z}{x}\right)^{m_1} \right )
\left ( \sum_{m_2=0}^{p-1} \left(\frac{x+y+z}{x}\right)^{m_2} \right )
\left ( \sum_{m_3=0}^{p-1} \left(\frac{x+y+z}{x}\right)^{m_3} \right )
\right] 
$$
$$
=CT\left[  \frac{(\frac{x+y+z}{x})^p -1}{\frac{x+y+z}{x}-1}
 \frac{(\frac{x+y+z}{y})^p -1}{\frac{x+y+z}{y}-1} 
\frac{(\frac{x+y+z}{z})^p -1}{\frac{x+y+z}{z}-1} \right]
$$
$$
=COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} \left [ \frac{(x+y+z)^p -x^p}{y+z} \cdot \frac{(x+y+z)^p -y^p}{x+z}  \cdot
\frac{(x+y+z)^p -z^p}{x+y} \right ] \,.
$$
So far this is true for all $p$, not only $p$ prime. Now take it mod $p$ and get, 
using the Freshman's Dream in the form $ (x+y+z)^p \equiv_p x^p+y^p+z^p$, that 
$$
\sum_{m_1=0}^{p-1}\sum_{m_2=0}^{p-1} \sum_{m_3=0}^{p-1} { m_1+m_2+m_3 \choose m_1,m_2,m_3}  
\,\, \equiv_p \,\,
COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} \left(\frac{y^p+z^p}{y+z} \cdot \frac{x^p+z^p}{x+z}\cdot \frac{y^p+z^p}{y+z}\right)
$$
$$
=COEFF_{[x^{p-1}y^{p-1}z^{p-1}]} 
\left ( \sum_{i=0}^{p-1} (-1)^i y^i z^{p-1-i} \right)
\left ( \sum_{j=0}^{p-1} (-1)^j z^j x^{p-1-j} \right)
\left ( \sum_{k=0}^{p-1} (-1)^k x^{k} y^{p-1-k} \right)
$$
$$
=COEFF_{[x^{p-1}y^{p-1}z^{p-1}]}  \left[
\sum_{0 \leq i,j,k<p} (-1)^{i+j+k} x^{p-1-j+k} y^{i+p-1-k} z^{p-1-i+j}
\right ] \quad .
$$

The only contributions to the coefficient of $x^{p-1}y^{p-1}z^{p-1}$  in the above triple sum come when
$i=j=k$, so the desired coefficient of $x^{p-1}y^{p-1}z^{p-1}$
is
$$
\sum_{i=0}^{p-1} (-1)^{3i}= \sum_{i=0}^{p-1} (-1)^{i}=(1-1+1-1+ \dots +1-1)+ 1 = 1 \quad . \quad \halmos
$$

Based on ample computer data, we conjecture

{\bf Proposition 6'}.  Let $p\geq 3$ be prime, and let $r,s,t$ be any positive integers, then
$$
\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}  \, \equiv_p  \,\, \kappa_{rst} \quad,
$$
where
$$
\kappa_{rst} =
\sum_{m_1=0}^{r-1}\sum_{m_2=0}^{s-1} \sum_{m_3=0}^{t-1} { m_1+m_2+m_3 \choose m_1,m_2,m_3} \quad .
$$

The same method of proof used in Proposition 6 yields (with a little more effort) a {\it multinomial} generatlization.

{\bf Proposition 7}.  Let $p \geq 3 $ be prime,  then
$$
\sum_{m_1=0}^{p-1} \dots \sum_{m_n=0}^{p-1} 
{ m_1+\dots m_n \choose m_1, \dots , m_n}  \, \equiv_p 1 \, \,\, .
$$

More generally, we conjecture

{\bf Proposition 7'}.  Let $p \geq 3$ be prime, and let $r_1, \dots, r_n$ be positive integers, then
$$
\sum_{m_1=0}^{r_1p-1} \dots \sum_{m_n=0}^{r_np-1} 
{ m_1+\dots m_n \choose m_1, \dots , m_n}  
\, \equiv_p  \kappa_{r_1 \dots r_n} \quad ,
$$
where
$$
 \kappa_{r_1 \dots r_n} \, =\,
 \sum_{m_1=0}^{r_1-1} \dots \sum_{m_n=0}^{r_n-1}  { m_1+\dots m_n \choose m_1, \dots , m_n}  
\, \,\, .
$$



{\bf References}

[AZ] Moa Apagodu and Doron Zeilberger,
{\it Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory},
Adv. Appl. Math. {\bf 37} (2006), 139-152. \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/multiZ.html} \quad .

[CHZ]  William Y.C. Chen, Qing-Hu Hou, and D. Zeilberger, 
{\it Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial Sequences}, J. of Difference Equations and Applications
(on-line before print),  DOI:10.1080/10236198.2016.1142541. Volume and page tbd.
Available from \hfill\break
{\tt http://www.math.rutgers.edu/\~{}zeilberg/mamarim/mamarimhtml/ctcong.html} \quad .

[Sl] N. J. A. Sloane, {\it The On-Line Encyclopedia of Integer Sequences}, {\tt http://oeis.org/} \quad .

[St] Richard Stanley, {\it ``Catalan Numbers''}, Cambridge University Press, 2015.

[Wi] The Wikipedia Foundation, {\it The Freshman's Dream} \quad .



{\bf Acknowledgment} The author would like to thank Doron Zeilberger without whose insightful 
comments and discussions this project would not have come to fruition. 

\bigskip
\bigskip
\hrule
\bigskip
Moa Apagodu, Department of Mathematics, 
Department of Mathematics, Virginia Commonwealth University, Richmond, VA 23284, USA
\bigskip
\hrule
\bigskip
{\bf  First Written:  June 8, 2016} ; 
{\bf  This version:  June 8, 2016} .

\end





















