USING THE “FRESHMAN’S DREAM” IDENTITY TO PROVE COMBINATORIAL CONGRUENCES

MOA APAGODU

Abstract. In a recent beautiful but technical article, William Y.C. Chen, Qing-Hu Hou, and Doron Zeilberger developed an algorithms for finding congruence, mod p, of sequences 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. Here we extend it in two directions. The Laurent polynomials in question may be of several variables, and instead of single sums we have multiple sums. In fact we even combine these two generalizations.

Introduction

In a recent elegant article, [2], the following type of quantities were considered

( ∑_{k=0}^{rp−1} a(k)) mod p ,

where a(k) is a combinatorial sequence, expressible as the constant term of a power of a Laurent polynomial of a singel variable, k; r is a positive integer; and p is a general (symbolic) prime.

Their method, while ingenious, is very elementary! All they need is the

The Freshman’s Dream Identity

(a + b)^{p} ≡_{p} a^{p} + b^{p} ,

where x ≡_{p} y means x ≡ ymod p.

Recall that the easy proof follows from using the Binomial theorem, and noting that \binom{p}{r} is divisible by p except when r = 0 and r = p. This also leads, to one of the many proofs of the grandmother of all congruences, Fermat’s Little Theorem, a^{p} ≡_{p} a, by starting with 0^{p} ≡_{p} 0, and applying induction to (a + 1)^{p} ≡_{p} a^{p} + 1^{p}.

The second ingredient in the ingenious method of [2] is even more elementary

Sum of a Geometric Series:

∑_{i=0}^{n−1} z^{i} = \frac{1 − z^{n}}{1 − z} ,

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

Notation The constant term of a Laurent polynomial P (x_{1}, x_{2}, …, x_{n}), alias the coefficient of x_{1}^{0}x_{2}^{0}..x_{n}^{0}, is denoted by CT [P (x_{1}, x_{2}, …, x_{n})] and the general coefficient of x_{1}^{n_{1}}x_{2}^{n_{2}}..x_{n}^{n_{k}} in P (x_{1}, x_{2}, …, x_{n}) is denoted by COEF F_{[x_{1}^{n_{1}} x_{2}^{n_{2}} ..x_{n}^{n_{k}}]}P (x_{1}, x_{2}, …, x_{n}). For example,

CT [\frac{1}{xy} + 3 + 5xy − x^{3} + 6y^{2}] = 3 and COEF F_{[xy]} [\frac{1}{xy} + 3 + 5xy + x^{3} + 6y^{2}] = 5.

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

Review of the Chen-Hou-Zeilberger Single Variable Case

In order to motivate our generalization, we will first review, in more detail then given in [2], some of their elegant results.

Proposition 1. For any prime p and positive integer r, define

A(r; p) := ∑_{n=0}^{rp−1} \binom{2n}{n}. Then, A(1; p) mod p = \{ \begin{matrix}1, if p ≡ 1 mod 3 \\ −1, if p ≡ 2 mod 3 . \end{matrix}

Proof: Using the fact that \binom{2n}{n} = CT [\frac{(1 + x)^{2n}}{x^{n}} ] and (a + b)^{p} ≡_{p} a^{p} + b^{p}, we

have

∑_{n=0}^{p−1} \binom{2n}{n} = ∑_{n=0}^{p−1} CT [(\frac{(1 + x)^{2n}}{x^{n}} )]

= ∑_{n=0}^{p−1} CT [(2 + x + \frac{1}{x})^{n}]

= CT [\frac{(2 + x + \frac{1}{x})^{p} − 1}{2 + x + \frac{1}{x} − 1}]

≡_{p} CT [\frac{2^{p} + x^{p} + \frac{1}{x^{p}} − 1}{1 + x + \frac{1}{x}}] By Freshman’s dream

≡_{p} CT [\frac{2 + x^{p} + \frac{1}{x^{p}} − 1}{1 + x + \frac{1}{x}}] By Fermat’s little theorem

= CT [\frac{1 + x^{p} + \frac{1}{x^{p}}}{1 + x + \frac{1}{x}} ]
= CT [\frac{1 + x^{p} + x^{2p}}{(1 + x + x^{2})x^{p−1}} ]
= COEF F_{[x^{p−1}]} [\frac{1}{1 + x + x^{2}} ]
= COEF F_{[x^{p−1}]} [\frac{1 − x}{1 − x^{3}} ] .

= COEF F_{[x^{p}]} ∑_{i=0}^{∞} x^{3i+1} − ∑_{i=0}^{∞} x^{3i+2} .

The result follows from extracting the coefficient of x^{p} from the two sums on the right side.

Corollary 1 (Corollary 2.3, [2]): A(2; p) mod p = \{ \begin{matrix}3, if p ≡ 1 mod 3 \\ −3, if p ≡ 2 mod 3 . \end{matrix}

Proof: Proceeding as in Theorem 1 above,

∑_{n=0}^{2p−1} \binom{2n}{n} = ∑_{n=0}^{2p−1} CT [(\frac{(1 + x)^{2n}}{x^{n}} )]
= CT [\frac{(2 + x + \frac{1}{x})^{2p} − 1}{2 + x + \frac{1}{x} − 1}]
= CT [\frac{(6 + 4x + \frac{4}{x} + x^{2} + \frac{1}{x^{2}} )^{p} − 1}{2 + x + \frac{1}{x} − 1}]
≡_{p} CT [\frac{(6 + 4x^{p} + \frac{4}{x^{p}} + x^{2p} + \frac{1}{x^{2p}} ) − 1}{2 + x + \frac{1}{x} − 1}]
≡_{p} COEF F_{[x^{2p−1}]} [\frac{1 + 4x^{p}}{1 + x + x^{2}} ]
≡_{p} COEF F_{[x^{2p−1}]} [\frac{1}{1 + x + x^{2}} ] + 4COEF F_{[x^{p−1}]} [\frac{1}{1 + x + x^{2}} ] .

The result follows from Theorem 1 and the last congruence. Corollary 2 (Catalan Numbers): Let a(n) be the constant term of (1 − x) (2 + x + \frac{1}{x})^{n} and let

A(r; p) := ∑_{n=0}^{rp−1} a(n) .

Then, A(1; p) mod p = \{ \begin{matrix}1, if p ≡ 1 mod 3 \\ −2, if p ≡ 2 mod 3 . \end{matrix} Proof: Continuing as above,

∑_{n=0}^{p−1} a(n) = ∑_{n=0}^{p−1} CT [(1 − x) (2 + x + \frac{1}{x})^{n}]
= CT [\frac{(1 − x) ((2 + x + \frac{1}{x})^{p} − 1)}{2 + x + \frac{1}{x} − 1}]
≡_{p} CT [\frac{(1 − x) ((2 + x^{p} + \frac{1}{x^{p}} ) − 1)}{2 + x + \frac{1}{x} − 1}]
≡_{p} COEF F_{[x^{p−1}]} [\frac{1 − x}{1 + x + x^{2}} ]
≡_{p} COEF F_{[x^{p−1}]} [\frac{1}{1 + x + x^{2}} ] − COEF F_{[x^{p−2}]} [\frac{1}{1 + x + x^{2}} ] .

The result follows from Theorem 1 and the last congruence.

Theorem 2 (Motzkin Numbers). Let a(n) be the constant term of (1 − x^{2}) (1 + x + \frac{1}{x})^{n}, and define

A(r; p) := ∑_{n=0}^{rp−1} a(n) .

Then, A(1; p) mod p = \{ \begin{matrix}2, if p ≡ 1 mod 4 \\ −2, if p ≡ 3 mod 4 . \end{matrix} Proof:

∑_{n=0}^{p−1} a(n) = ∑_{n=0}^{p−1} CT [(1 − x^{2}) (1 + x + \frac{1}{x})^{n}]
= CT [\frac{(1 − x^{2}) ((1 + x + \frac{1}{x})^{p} − 1)}{1 + x + \frac{1}{x} − 1}]
≡_{p} COEF F_{[x^{p−1}]} [\frac{1 − x^{2}}{1 + x^{2}} ]
≡_{p} COEF F_{[x^{p−1}]} [\frac{1}{1 + x^{2}} ] − COEF F_{[x^{p−3}]} [\frac{1}{1 + x^{2}} ]

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

Corollary 3: Let a(n) be the constant term of (1 − x^{2}) (1 + x + \frac{1}{x})^{n} and let

A(r; p) := ∑_{n=0}^{rp−1} a(n) .

Then, A(2; p) mod p = \{ \begin{matrix}4, if p ≡ 1 mod 4 \\ −4, if p ≡ 3 mod 4 . \end{matrix} Proof:

∑_{n=0}^{2p−1} a(n) = ∑_{n=0}^{2p−1} CT [(1 − x^{2}) (1 + x + \frac{1}{x})^{n}]

= CT [\frac{(1 − x^{2}) ((1 + x + \frac{1}{x})^{2p} − 1)}{1 + x + \frac{1}{x} − 1}]

= CT [\frac{(1 − x^{2}) ((3 + 2x + x^{2} + \frac{2}{x} + \frac{1}{x^{2}} )^{p} − 1)}{1 + x + \frac{1}{x} − 1}]

= CT [\frac{(1 − x^{2}) ((3 + 2x^{p} + x^{2p} + \frac{2}{x^{p}} + \frac{1}{x^{2p}} ) − 1)}{1 + x + \frac{1}{x} − 1}]

≡_{p} COEF F_{[x^{2p−1}]} [\frac{(1 − x^{2})(1 + 2x^{p})}{1 + x^{2}}]
≡_{p} COEF F_{[x^{2p−1}]} [\frac{1}{1 + x^{2}} ] + 2COEF F_{[x^{p−1}]} [\frac{1}{1 + x^{2}} ]
− COEF F_{[x^{2p−3}]} [\frac{1}{1 + x^{2}} ] − 2COEF F_{[x^{p−3}]} [\frac{1}{1 + x^{2}} ] .

The result follows from Theorem 2 and the last congruence.

From the above theorems and corollaries, 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 [2].

Theorem 3 . 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),

( ∑_{n=0}^{rp−1} CT [P (x)^{n}Q(x)]) mod p ,

is congruent to a finite linear combination of finite terms of coefficients of the

rational function \frac{1}{R(x)}.

Multi-Sums and Multi-Variables

Theorem 4. Let p be a prime number and let r and s be a positive integers. Let

A(r, s; p) := ∑_{n=0}^{rp−1} ∑_{m=0}^{sp−1} \binom{n + m}{m}^{2} .

Then, A(1, 1; p) mod p = \{ \begin{matrix}0, if p ≡ 0 mod 3 \\ 1, if p ≡ 1 mod 3 \\ −1, if p ≡ 2 mod 3 . \end{matrix}

Furthermore, A(2, 2; p) ≡_{p} COEF F_{[x^{2p−1}y^{2p−1}]} \frac{1 + 4x^{p} + 4y^{p} + 16x^{p}y^{p}}{(1 + x + xy)(1 + y + xy)}.

Proof: Let P (x, y) = (1 + y) (1 + \frac{1}{x}) and Q(x, y) = (1 + x) (1 + \frac{1}{y} ). First ob-

serve that

\binom{n + m}{m}^{2} = \binom{n + m}{m}\binom{n + m}{n} = CT (P (x, y)^{n}Q(x, y)^{m}) .

Then,

∑_{m=0}^{p−1} ∑_{n=0}^{p−1} \binom{m + n}{m}^{2} = ∑_{m=0}^{p−1} ∑_{n=0}^{p−1} CT [P (x, y)^{n}Q(x, y)^{m}]

= ∑_{m=0}^{p−1} CT [\frac{P (x, y)^{p} − 1)Q(x, y)^{m}}{P (x, y) − 1} ]

= CT [(\frac{P (x, y)^{p} − 1}{P (x, y) − 1}) (\frac{Q(x, y)^{p} − 1}{Q(x, y) − 1})]

Using (a + b)^{p} ≡ (a^{p} + b^{p}) mod p, we can pass to mod p as above

∑_{m=0}^{p−1} ∑_{n=0}^{p−1} \binom{m + n}{m}^{2} ≡_{p} CT [(\frac{P (x^{p}, y^{p}) − 1}{P (x, y) − 1}) (\frac{Q(x^{p}, y^{p}) − 1}{Q(x, y) − 1})]

≡_{p} CT [\frac{(1 + y^{p} + x^{p}y^{p})(1 + x^{p} + x^{p}y^{p})}{(1 + y + xy)(1 + x + xy)x^{p−1}y^{p−1}} ]
≡_{p} COEF F_{[x^{p−1}y^{p−1}]} [\frac{(1 + y^{p} + x^{p}y^{p})(1 + x^{p} + x^{p}y^{p})}{(1 + y + xy)(1 + x + xy)}]
≡_{p} COEF F_{[x^{p−1}y^{p−1}]} [\frac{1}{(1 + y + xy)(1 + x + xy)}]

Using the Apagodu-Zeilberger algorithm ([1]), the diagonal coefficients satisfy the recurrence equation N^{2} + N + 1 = 0 with 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 is given by:

a(n) = \{ \begin{matrix}1, if n ≡ 0 mod 3 \\ 1, if n ≡ 1 mod 3 \\ 0, if n ≡ 2 mod 3 . \end{matrix}

Note that our partial sum is congruent to a(p − 1), not a(p).

For the A(2, 2; p), we have

∑_{m=0}^{2p−1} ∑_{n=0}^{2p−1} \binom{m + n}{m}^{2} ≡_{p} CT [(\frac{P (x^{p}, y^{p})^{2} − 1}{P (x, y) − 1}) (\frac{Q(x^{p}, y^{p})^{2} − 1}{Q(x, y) − 1})]

≡_{p} CT [\frac{(1 + y^{p} + x^{p}y^{p})^{2}(1 + x^{p} + x^{p}y^{p})^{2}}{(1 + y + xy)(1 + x + xy)x^{p−1}y^{p−1}} ]
≡_{p} COEF F_{[x^{2p−1}y^{2p−1}]} [\frac{(1 + y^{p} + x^{p}y^{p})^{2}(1 + x^{p} + x^{p}y^{p})^{2}}{(1 + y + xy)(1 + x + xy)} ]
≡_{p} COEF F_{[x^{2p−1}y^{2p−1}]} [\frac{1 + 4x^{p} + 4y^{p} + 16x^{p}y^{p}}{(1 + x + xy)(1 + y + xy)}]

It follows that,

A(2, 2; p) ≡_{p} COEF F_{[x^{2p−1}y^{2p−1}]} \frac{1 + 4x^{p} + 4y^{p} + 16x^{p}y^{p}}{(1 + x + xy)(1 + y + xy)} .

By symmetry, it simplifies to

A(2, 2; p) ≡_{p} COEF F_{[x^{2p−1}y^{2p−1}]} \frac{1}{(1 + x + xy)(1 + y + xy)}+

8COEF F_{[x^{p−1}y^{2p−1}]} \frac{1}{(1 + x + xy)(1 + y + xy)}+16COEF F_{[x^{p−1}y^{p−1}]} \frac{1}{(1 + x + xy)(1 + y + xy)}

Based on computer calculations, we conjecture other values of r and s that admits a nice form. These congruence are also true mod p^{2}. The congruences with higher power of p are called supercongruence and the present method can’t handle them.

(1) For p ≥ 17, A(2, 2; p) mod p = \{ \begin{matrix}7, if p ≡ 1 mod 3 \\ −7, if p ≡ 2 mod 3 . \end{matrix}
(2) For p ≥ 37, A(2, 3; p) mod p = \{ \begin{matrix}17, if p ≡ 1 mod 3 \\ −17, if p ≡ 2 mod 3 . \end{matrix}
(3) For p ≥ 127, A(3, 3; p) mod p = \{ \begin{matrix}63, if p ≡ 1 mod 3 \\ −63, if p ≡ 2 mod 3 . \end{matrix}
(4) A(1, 1; p) ≡ 1 (mod p^{2}) .
(5) For p ≥ 5, A(2, 2; p) mod p^{2} = \{ \begin{matrix}7, if p ≡ 1 mod 3 \\ −7, if p ≡ 2 mod 3 . \end{matrix}
(6) For p ≥ 7, A(2, 3; p) mod p^{2} = \{ \begin{matrix}17, if p ≡ 1 mod 3 \\ −17, if p ≡ 2 mod 3 . \end{matrix}
(7) For p ≥ 17, A(3, 3; p) mod p^{2} = \{ \begin{matrix}63, if p ≡ 1 mod 3 \\ −63, if p ≡ 2 mod 3 . \end{matrix}

Remark: If we take the third power of the summand in Theorem 4 and define

C(r, s; p) := ∑_{n=0}^{rp−1} ∑_{m=0}^{sp−1} \binom{n + m}{m}^{3} ,

then,

\binom{n + m}{m}^{3} = CT [\frac{(1 + x)^{m+n}}{x^{m}} \frac{(1 + y)^{m+n}}{y^{m}} \frac{(1 + z)^{m+n}}{z^{n}} ] .

with P (x, y, z) = (1 + \frac{1}{x}) (1 + \frac{1}{y} ) (1 + z) and Q(x, y, z) = (1 + x) (1 + y) (1 + \frac{1}{z}),

we have

\binom{n + m}{m}^{3} = CT ((P (x, y)^{m}Q(x, y)^{n}) .

and proceeding as above, we get

C(1, 1; p) ≡ COEF F_{[x^{p−1}y^{p−1}z^{p−1}]} [\frac{1}{p(x, y, z)q(x, y, z)}] mod p ,

where p(x, y, z) = 1 + x + y + xy + xz + yz + xyz and q(x, y, z) = 1 + y + z + xy + xz + yz + xyz.

Theorem 5. Let p > 2 be prime, and r, s and t be positive integers. Define

A(r, s, t; p) := ∑_{m_{1}=0}^{rp−1} ∑_{m_{2}=0}^{sp−1} ∑_{m_{3}=0}^{tp−1} \binom{m_{1} + m_{2} + m_{3}}{m_{1}, m_{2}, m_{3}} .

Then, A(1, 1, 1; p) ≡ 1 mod p.

Proof: First observe that \binom{m_{1} + m_{2} + m_{3}}{m_{1}, m_{2}, m_{3}} = CT [\frac{(x + y + z)^{m_{1}+m_{2}+m_{3}}}{x^{m_{1}}y^{m_{2}}z^{m_{3}}} ].

Hence

∑_{0≤m_{1},m_{2},m_{3}≤p−1} \binom{m_{1} + m_{2} + m_{3}}{m_{1}, m_{2}, m_{3}} = ∑_{0≤m_{1},m_{2},m_{3}≤p−1} CT [(x + y + z)^{(}m_{1} + m_{2} + m_{3})/(x^{m_{1}}y^{m_{2}}z^{m_{3}})]

= CT [  ∑_{0≤m_{1},m_{2},m_{3}≤p−1} \frac{(x + y + z)^{(}m_{1} + m_{2} + m_{3})}{x^{m_{1}}y^{m_{2}}z^{m_{3}}} ]

= CT [  ∑_{0≤m_{1},m_{2},m_{3}≤p−1} \frac{(x + y + z)^{m_{1}}}{x^{m_{1}}} \frac{(x + y + z)^{m_{2}}}{y^{m_{2}}} \frac{(x + y + z)^{m_{3}}}{y^{m_{3}}}

= CT [( ∑_{0≤m_{1}≤p−1} (\frac{x + y + z}{x} )^{m_{1}} ) ( ∑_{0≤m_{2}≤p−1} (\frac{x + y + z}{y} )^{m_{2}} )

( ∑_{0≤m_{3}≤p−1} (\frac{x + y + z}{z} )^{m_{3}} )

= CT [\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}]

= COEF F_{[x^{p−1}y^{p−1}z^{p−1}]}[\frac{(x + y + z)^{p} − x^{p}}{y + z} × \frac{(x + y + z)^{p} − y^{p}}{x + z} ×

\frac{(x + y + z)^{p} − z^{p}}{x + y}] .

So far this is true for all p, not only p prime. Now take it mod p and get, since (x + y + z)^{p} ≡_{p} (x^{p} + y^{p} + z^{p}),

A(1, 1, 1; p) = COEF F_{[x^{p−1}y^{p−1}z^{p−1}]} (\frac{y^{p} + z^{p}}{y + z} × \frac{x^{p} + z^{p}}{x + z} × \frac{y^{p} + z^{p}}{y + z} )
= COEF F_{[x^{p−1}y^{p−1}z^{p−1}]} (y^{p−1}z^{0} − y^{p−2}z + y^{p−3}z^{2} + ... + y^{0}z^{p−1}) ×

(x^{p−1}z^{0} − x^{p−2}z + x^{p−3}z^{2} + ... + x^{0}z^{p−1}) × (x^{p−1}y^{0} − x^{p−2}y + x^{p−3}y^{2} + ... + x^{0}y^{p−1})

= COEF F_{[x^{p−1}y^{p−1}z^{p−1}]}[(∑_{j=0}^{p−1}(−1)^{j}x^{p−1−j}y^{j}) (∑_{k=0}^{p−1}(−1)^{k+1}z^{p−1−k}x^{k}) (∑_{l=0}^{p−1}(−1)^{l}y^{p−1−l}z^{l})] .

It is easy to see that to extract the x^{p−1}y^{p−1}z^{p−1} term in the above triple sum, we need j = k = l = (p − 1)/2, and hence get (−1)^{3∗(p−1)/2} expansion by multiplying (x^{p−1−j}y^{j})(z^{p−1−k}x^{k})(y^{p−1−l}z^{l}) exactly when j = k = l = (p − 1)/2. Hence the coefficient of x^{p−1}y^{p−1}z^{p−1} is

∑_{j=0}^{p−1}(−1)^{3j} = ∑_{j=0}^{p−1}(−1)^{j}. It follows that the coefficient is 1 for p > 2 and 0 for

p = 2. This completes the proof.

We make the following conjectures based on computer calculations.

(1) A(1, 1, 2; p) ≡ 2 (mod p), for p ≥ 5.

(2) A(1, 2, 2; p) ≡ 5 (mod p) , for p ≥ 11.

(3) A(2, 2, 2; p) ≡ 16 (mod p). for p ≥ 37. The following supercongruences are also true.

(1) A(1, 1, 1; p) ≡ 1 (mod p^{2}), for p ≥ 2.

(2) A(1, 1, 1; p) ≡ 1 (mod p^{3}), for p ≥ 2.

(3) A(1, 1, 2; p) ≡ 2 (mod p^{2}), for p ≥ 3.

(4) A(1, 1, 2; p) ≡ 2 (mod p^{3}), for p ≥ 3.

(5) A(1, 2, 2; p) ≡ 5 (mod p^{2}), for p ≥ 5 .

(6) A(1, 2, 2; p) ≡ 5 (mod p^{3}), for p ≥ 3 .

(7) A(2, 2, 2; p) ≡ 16 (mod p^{2}), for p ≥ 7.

(8) A(2, 2, 2; p) ≡ 16 (mod p^{3}), for p ≥ 5.

Similarly, if we define

A(r, s, t, u; p) := ∑_{m_{1}=0}^{rp−1} ∑_{m_{2}=0}^{sp−1} ∑_{m_{3}=0}^{tp−1} ∑_{m_{4}=0}^{up−1} \binom{m_{1} + m_{2} + m_{3} + m_{4}}{m_{1}, m_{2}, m_{3}, m_{4}} ,

for prime p and positive integers r, s, t and u, then we get the following conjectures. (1) A(1, 1, 1, 1; p) ≡ 1 (mod p), for p ≥ 3 .

(2) A(1, 1, 1, 2; p) ≡ 2 (mod p), for p ≥ 5.

(3) A(1, 1, 2, 2; p) ≡ 5 (mod p), for p ≥ 11 .

(4) A(1, 2, 2, 2; p) ≡ 16 (mod p), for p ≥ 37 .

Our last observation is the general multinomial case. For prime p > 2 and positive integers r_{i}, i = 1, 2, 3, …, k, if we define

A(r_{1}, r_{2}, …, r_{k}; p) := ∑_{m_{1}=0}^{r_{1}p−1} ∑_{m_{2}=0}^{r_{2}p−1} … ∑_{m_{a}=0}^{r_{k}p−1} \binom{m_{1} + m_{2} … + m_{a}}{m_{1}, m_{2}, …, m_{k}} .

Then, computer outputs support the following conjectures (1) A(1, 1, …, 1; p) = 1 (mod p), for p ≥ 2.

(2) A(1, 1, …, 1; p) = 1 (mod p^{2}), for p ≥ 2.

(3) A(1, 1, …, 1; p) = 1 (mod p^{3}), for p ≥ 2.

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

References

[1] M. Apagodu and D. Zeilberger, Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory, Adv. Appl. Math. 37(2006).

[2] 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.

Department of Mathematics, Virginia Commonwealth University, Richmond, VA 23284, USA