CONGRUENCE THEOREMS FOR SEQUENCES DEFINED BY PARTIAL SUMS

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

Doron Zeilberger

Rutgers University, Department of Math., 110 Frelinghuysen Rd, Piscataway, NJ 08854

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.

The topic of interest is to find

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

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.

The constant term of a Laurent polynomial P (x_{1}, x_{2}, …, x_{n}), 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 coefficinet 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}}]}. 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 an integer modulo integer m. For example 6 mod 5 = 1 and 4 mod 5 = −1.

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

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

A(r; p) := ( ∑_{n=0}^{rp−1} \binom{2n}{n}) mod p . Then, A(1; 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{1 + x^{p} + \frac{1}{x^{p}}}{1 + x + \frac{1}{x}} ]
≡_{p} CT [\frac{1 + x^{p} + x^{2p}}{(1 + x + x^{2})x^{p−1}} ]
≡_{p} COEF F_{[x^{p−1}]} [\frac{1}{1 + x + x^{2}} ]
≡_{p} COEF F_{[x^{p−1}]} [\frac{1 − x}{1 − x^{3}} ]

The result folllows from series expansion of the last expression.

Corollary 1 (Corollary 2.3, [6]): A(2; p) = \{ \begin{matrix}3, if p ≡ 1 mod 3 \\ −3, if p ≡ 2 mod 3 . \end{matrix} Proof: Proceed as in the thoerem,

∑_{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 folllows 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)) mod p .

Then, A(1; 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) = \{ \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(1; 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 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].

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}.

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

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

CONGRUENCE THEOREMS FOR SEQUENCES DEFINED BY PARTIAL SUMS 5

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

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

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

Then, A(1, 1; 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 observe 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} ≡_{p} a^{p} + b^{p}, we can pass to modulo as before

∑_{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, 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

6 CONGRUENCE THEOREMS FOR SEQUENCES DEFINED BY PARTIAL SUMS

result now follows from the fact that this recurrence is equivalent to N^{3} − 1 = 0 and the solution to this recurrence:

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

Note that our partial sum is congruent to a(p − 1) for any prime p. Finally, for 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)}

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}) mod p .

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}} ] .

and if we let 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}), then we have

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

Repeating the above arguement verbatim, we get

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

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. Let

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) ≡_{p} 1.

Proof: Observe that

\binom{m_{1} + m_{2} + m_{3}}{m_{1}, m_{2}, m_{3}} = CT [\frac{(1 + x + y + z)^{m_{1}+m_{2}+m_{3}}}{x^{m_{1}}y^{m_{2}}z^{m_{3}}} ]

Using (x + y)^{p} ≡_{p} x^{p} + y^{p} and routine algebra, we get

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

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

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 .

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

with initial conditions a(0) = 1 and a(1) = −14, whose solution is given by

a(p) ≡_{p} 4(−8)^{p} − 3(−6)^{p} .

From the above equation, we know that A(1, 1, 1; p) ≡ a(p − 1) (mod p). Thus,

A(1, 1, 1; p) = a(p − 1) ≡_{p} 4(−8)^{p−1} − 3(−6)^{p−1} ≡_{p} 2^{p−1} .

. Now it suffices to show that 2^{p−1} − 1 ≡_{p} 0. But this follows fom

2^{p−1} − 1 = \frac{1}{2}(2^{p} − 2) = \frac{1}{2}((1 + 1)^{p} − 2) ≡_{p} \frac{1}{2}(1 + 1 − 2) = 0 .

Computer evidences suggest the following conjectures Conjecture 1: A(1, 1, 1; p) ≡_{p^{α}} 1 for α = 2, 3. Conjecture 2: The above computer data suggests that A(2, 2, 2; p) ≡_{p^{α}} 16 for p ≥ 17 and α = 1, 2, 3 For the general case, if we denote,

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

Then, one can show that A(1, 1, …, 1; p) ≡_{p} Coeff_{[x_{1}^{p−1}x_{2}^{p−1}...x_{a}^{p−1}]} \frac{1}{∏_{j=1}^{a}(1 + ∑_{i=1,i≠j}^{a} x_{i})}.

Proof (of i) : Observe that

\binom{m_{1} + m_{2} … + m_{a}}{m_{1}, m_{2}, …, m_{a}} = CT [\frac{(1 + x_{1} + x_{2} + … + x_{a})^{m_{1}+m_{2}+...+m_{a}}}{∏_{i=1}^{a} x_{i}^{m_{i}}} ]

As in the proof of Theorem 4,

∑_{m_{1}=0}^{p−1} … ∑_{m_{a}=0}^{p−1} \binom{m_{1} + m_{2} … + m_{a}}{m_{1}, m_{2}, …, m_{a}} = ∑_{m_{1}=0}^{p−1} … ∑_{m_{a}=0}^{p−1} CT [\frac{(1 + x_{1} + x_{2} + … + x_{a})^{∑_{j=1}^{a} m_{j}}}{∏_{i=1}^{a} x_{i}^{m_{i}}} ]
≡_{p} COEF F_{[x_{1}^{p−1}x_{2}^{p−1}...x_{a}^{p−1}]} \frac{1}{∏_{j=1}^{a} (1 + ∑_{i=1,i≠j}^{a} x_{i})}.

Computer evidence suggests that Conjecture 3: A(1, 1, …, 1; p) ≡_{p^{α}} 1 for p > 2 and α = 1, 2, 3.

Apéry Numbers: As our last example, we consider one of the most intriguing sequence, the Apery numbers, defined by

A(n) := ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2}

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

A(mp^{r}) ≡ A(mp^{r−1}) (mod p^{3r}) ,

for prime p ≥ 5 and positive integr r and

A (\frac{p − 1}{2}) ≡ ∑_{k=0}^{p−1} \binom{2k}{k}^{4}2^{−8k} ≡ γ(p) (mod p),

and

∑_{j=1}^{∞} γ(n)q^{n} = q ∏_{n=1}^{∞}(1 − q^{2n})^{4}(1 − q^{4n})^{4}.

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

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

Let p be a prime number and define

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

We can express a(p) as

∑_{n=0}^{p−1} ∑_{k=0}^{n} \binom{n}{k}^{2}\binom{n + k}{k}^{2} = ∑_{n=0}^{p−1} CT [(\frac{(1 + x)(1 + y)(1 + z)(1 + y + z + yz + xyz)}{xyz})^{n}]
= CT [R1(x, y, z) + R2(x, y, z)]
= CT [\frac{R1(x, y, z)}{x^{p−1}y^{p−1}z^{p−1}} ]
= CT [\frac{P (x, y, z)}{x^{p−1}y^{p−1}z^{p−1}Q(x, y, z)}]
≡_{p} COEF F_{[x^{p−1}y^{p−1}z^{p−1}]} \frac{P (x^{p}, y^{p}, z^{p})}{Q(x, y, z)}
≡_{p} COEF F_{[x^{p−1}y^{p−1}z^{p−1}]} [\frac{1}{Q(x, y, z)}]

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}

and

Q(x, y, z) = x^{2}y^{2}z^{2} + x^{2}y^{2}z + x^{2}yz^{2} + 2xy^{2}z^{2} + x^{2}yz + 3xy^{2}z + 3xyz^{2} + y^{2}z^{2} + xy^{2}

+4xyz + xz^{2} + 2y^{2}z + 2yz^{2} + 2xy + 2xz + y^{2} + 4yz + z^{2} + x + 2y + 2z + 1 . Therefore,

a(p) ≡ α(p − 1, p − 1, p − 1)(mod p)

where

Q(x, y, z) = ∑_{m,n,k} α(m, n, k)x^{n}y^{m}z^{k} .

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)} .

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

( ∑_{k=0}^{rp−1} ∑_{n=0}^{sp−1} ∑_{n=0}^{tp−1} CT (P (x, y, z)^{n}Q(x, y, z)^{k}R(x, y, z)) ) mod p

is congruent to a P -finite sequence and can be expressed as a finite linear combi-

nation of coefficients of \frac{1}{T (x, y, z)}.

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.

References

[1] S. Ahlgreen and K. Ono. A Gaussian hypergeometric series evaluation and Apéry number congruences. Journal fur die Reine und Angewandte Mathematik, pages 187–212, 2000.

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

[3] F. Beukers. Another congruence for the Apéry numbers. Journal of Number Theory, 25(2):201– 210, 1987.

[4] E. Rowland and D. Zeilberger. A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences. Journal of Difference Equations and Applications, 20(7):973–988, 2014.

[5] Z.-W. Sun. Congruences involving generalized central trinomial coefficients. Science China Mathematics, 57(7):1375–1400, 2014.

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