Using the “Freshman’s Dream” Identity to Prove Combinatorial Congruences By Moa APAGODU

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! Introduction In a recent elegant article ([CHZ]) 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 single variable (for example, the central binomial coefficient \binom{2k}{k} is the coefficient of x^{0} in (x + \frac{1}{x})^{2k}) .

• r is a specific positive integer .

• p is an arbitrary prime . Let x ≡_{p} y mean x ≡ y (mod p), in other words, that x − y is divisible by p. The [CHZ] method, while ingenious, is very elementary! The main “trick” is: The Freshman’s Dream Identity ([Wi]): (a + b)^{p} ≡_{p} a^{p} + b^{p} . Recall that the easy proof follows from the Binomial Theorem, and noting that \binom{p}{k} is divisible by p except when k = 0 and k = 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 [CHZ] method is even more elementary! It is: Sum of a Geometric Series:

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

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 two directions. The summand a(k), may be the constant term of a Laurent polynomial of 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})]. The general coefficient of x_{1}^{m_{1}}x_{2}^{m_{2}}..x_{n}^{m_{n}} in P (x_{1}, x_{2}, …, x_{n}) is denoted by COEF F_{[x_{1}^{m_{1}} x_{2}^{m_{2}} ..x_{n}^{mn}]}P (x_{1}, x_{2}, …, x_{n}). For example,

CT [\frac{1}{xy} + 3 + 5xy − x^{3} + 6y^{2}] = 3 , COEF F_{[xy]} [\frac{1}{xy} + 3 + 5xy + x^{3} + 6y^{2}] = 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.

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 Central Binomial Coefficients, sequence A000984 in the great OEIS ([Sl], https://oeis.org/A000984).

Proposition 1. For any prime p ≥ 5

∑_{n=0}^{p−1} \binom{2n}{n} ≡_{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 the Freshman’s Dream identity, (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} ) + COEF F_{[x^{p}]} ( ∑_{i=0}^{∞}(−1) · x^{3i+2} ) .

The result follows from extracting the coefficient of x^{p} in the above geometrical series.

Proposition 1’

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

Proof:

∑_{n=0}^{2p−1} \binom{2n}{n} = ∑_{n=0}^{2p−1} CT [(2 + x + \frac{1}{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}]

= COEF F_{[x^{2p−1}]} [\frac{1 + 4x^{p}}{1 + x + x^{2}} ] = COEF F_{[x^{2p−1}]} [\frac{1}{1 + x + x^{2}} ] + 4 · COEF F_{[x^{p−1}]} [\frac{1}{1 + x + x^{2}} ]

= COEF F_{[x^{2p−1}]} [\frac{1 − x}{1 − x^{3}} ] + 4 · COEF F_{[x^{p−1}]} [\frac{1 − x}{1 − x^{3}} ]

= COEF F_{[x^{2p−1}]} [\frac{1}{1 − x^{3}} ]+COEF F_{[x^{2p−1}]} [\frac{−x}{1 − x^{3}} ]+4·COEF F_{[x^{p−1}]} [\frac{1}{1 − x^{3}} ]+4·COEF F_{[x^{p−1}]} [\frac{−x}{1 − x^{3}} ]

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

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

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 ∑_{n=0}^{rp−1} \binom{2n}{n} for any specific positive integer r. This lead to the following conjecture, that we (rigorously) proved (with a computer) for r ≤ 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.

Conjecture 1” For any priem p ≥ 5, and any positive integer, r,

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

where

α_{r} = ∑_{n=0}^{r−1} \binom{2n}{n}

For the record, here are the first ten terms of the integer sequence α_{r}:

[1, 3, 9, 29, 99, 351, 1275, 4707, 17577, 66187] .

To our surprise, at this time of writing (June 9, 2016), the sequence α_{r} is not (yet) in the OEIS, but α_{r} − 1 is Sequence A066796 [[Sl],https://oeis.org/A066796]. Note that α_{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 α_{r} − 1 excludes the lazy option of doing nothing).

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

Proposition 2: Let C_{n} be the Catalan Numbers, then, for every prime p ≥ 5,

∑_{n=0}^{p−1} C_{n} ≡_{p} \{ \begin{matrix}1, & if p ≡ 1 (mod 3) ; \\ −2, & if p ≡ 2 (mod 3) . \end{matrix} ,

Proof: Since C_{n} = \binom{2n}{n} − \binom{2n}{n−1}, it is readily seen that C_{n} = CT [(1 − x)(\frac{1}{2+x+ \frac{1}{x}})^{n}]. We have

∑_{n=0}^{p−1} C_{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}] = COEF F_{[x^{p−1}]} [\frac{1 − x}{1 + x + x^{2}} ] = COEF F_{[x^{p−1}]} [\frac{(1 − x)^{2}}{1 − x^{3}} ]

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

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

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 ∑_{n=0}^{rp−1} C_{n} for any specific positive integer r. This lead to the following conjecture, that we (rigorously) proved (with a computer) for r ≤ 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.

Conjecture 2’: Let C_{n} be the Catalan Numbers, then, for any positive integer r, there

∑_{n=0}^{rp−1} C_{n} ≡_{p} \{ \begin{matrix}β_{r}, & if p ≡ 1 (mod 3) ; \\ −γ_{r}, & if p ≡ 2 (mod 3) , \end{matrix}

where

β_{r} = ∑_{n=0}^{r−1} C_{n} , γ_{r} = ∑_{n=0}^{r−1}(3n + 2)C_{n} .

For the record, the first ten terms of the sequence of integer pairs [β_{r}, −γ_{r}] are

[[1, −2], [2, −7], [4, −23], [9, −78], [23, −274], [65, −988], [197, −3628], [626, −13495], [2076, −50675], [6918, −191673]] .

We note that the sequence β_{r} is sequence A014137 in the OEIS ([Sl], https://oeis.org/A014137) but at this time of writing (June 9, 2016), the sequence γ_{r} is not there (yet).

Not as famous as the Catalan numbers, but not exactly obscure, are the Motzkin numbers, M_{n}, sequence A001006 in the great OEIS ([Sl], https://oeis.org/A001006), that may be defined by the constant term formula

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

Proposition 3: Let M_{n} be the Motzkin numbers, then for any prime p ≥ 3, we have

∑_{n=0}^{p−1} M_{n} ≡_{p} \{ \begin{matrix}2, & if p ≡ 1 (mod 4) ; \\ −2, & if p ≡ 3 (mod 4) . \end{matrix}

Proof:

∑_{n=0}^{p−1} M_{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} CT [\frac{(1 − x^{2}) (1 + x^{p} + \frac{1}{x^{p}} − 1)}{1 + x + \frac{1}{x} − 1}] = CT [\frac{(1 − x^{2}) (x^{p} + \frac{1}{x^{p}} )}{x + \frac{1}{x}}] = CT [\frac{x(1 − x^{2}) (x^{p} + \frac{1}{x^{p}} )}{1 + x^{2}}]

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

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

and the result follows from extracting the coefficient of x^{p} from the first and second geometric series above, by noting that when p ≡ 1 (mod 4) i is even in the first series, and odd in the second one, and vice-versa when p ≡ 1 (mod 4).

The same method yieds

Conjecture 3’: Let M_{n} be the Motzkin numbers, and let p ≥ 3 be prime, then for any positive integer r, there exists an integer δ_{r} such that

∑_{n=0}^{rp−1} M_{n} ≡_{p} \{ \begin{matrix}δ_{r}, & if p ≡ 1 (mod 4) ; \\ −δ_{r}, & if p ≡ 3 (mod 4) . \end{matrix}

Using the present method ([CHZ]) we rigorously proved that the first ten terms of the integer sequence δ_{r} are

[2, 4, 10, 24, 62, 164, 446, 1232, 3446, 9724] .

At this time of writing (June 9, 2016), the sequence δ_{r} is not (yet) in the OEIS.

Challenge: Can you find an expression for δ_{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].

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),

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

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

Multi-Sums and Multi-Variable

We now go to the new material.

Proposition 5. Let p ≥ 5 be a prime number, then

∑_{n=0}^{p−1} ∑_{m=0}^{p−1} \binom{n + m}{m}^{2} ≡_{p} \{ \begin{matrix}1, & if p ≡ 1 (mod 3) ; \\ −1, & if p ≡ 2 (mod 3) . \end{matrix}

Proof: Let

P (x, y) = (1 + y) (1 + \frac{1}{x})

and

Q(x, y) = (1 + x) (1 + \frac{1}{y} )

Then

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

We have

∑_{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 the Freshman’s Dream ((a + b)^{p} ≡ (a^{p} + b^{p}) mod p), we can pass to mod p as above, we get

∑_{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)}] .

It is possible to show that the coefficient of x^{n}y^{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

Conjecture 5’. For any prime p ≥ 5, and any pair of positive integers, r, s, we have

∑_{n=0}^{rp−1} ∑_{m=0}^{sp−1} \binom{n + m}{m}^{2} ≡_{p} \{ \begin{matrix}ϵ_{rs}, & if p ≡ 1 (mod 3) ; \\ −ϵ_{rs}, & if p ≡ 2 (mod 3) , \end{matrix}

where

ϵ_{rs} = ∑_{m=0}^{r−1} ∑_{n=0}^{s−1} \binom{n + m}{m}^{2} .

We finally consider partial sums of trinomial coefficients.

Proposition 6. Let p > 2 be prime,

∑_{m_{1}=0}^{p−1} ∑_{m_{2}=0}^{p−1} ∑_{m_{3}=0}^{p−1} \binom{m_{1} + m_{2} + m_{3}}{m_{1}, m_{2}, m_{3}} ≡_{p} 1 .

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 [( ∑_{m_{1}=0}^{p−1} (\frac{x + y + z}{x} )^{m_{1}}) ( ∑_{m_{2}=0}^{p−1} (\frac{x + y + z}{x} )^{m_{2}}) ( ∑_{m_{3}=0}^{p−1} (\frac{x + y + z}{x} )^{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, using the Freshman’s Dream in the form (x + y + z)^{p} ≡_{p} x^{p} + y^{p} + z^{p}, that

∑_{m_{1}=0}^{p−1} ∑_{m_{2}=0}^{p−1} ∑_{m_{3}=0}^{p−1} \binom{m_{1} + m_{2} + m_{3}}{m_{1}, m_{2}, m_{3}} ≡_{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}]} (∑_{i=0}^{p−1}(−1)^{i}y^{i}z^{p−1−i}) (∑_{j=0}^{p−1}(−1)^{j}z^{j}x^{p−1−j}) (∑_{k=0}^{p−1}(−1)^{k}x^{k}y^{p−1−k})

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

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

∑_{i=0}^{p−1}(−1)^{3i} = ∑_{i=0}^{p−1}(−1)^{i} = (1 − 1 + 1 − 1 + … + 1 − 1) + 1 = 1 .

Based on ample computer data, we conjecture Proposition 6’. Let p ≥ 3 be prime, and let r, s, t be any positive integers, then

∑_{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}} ≡_{p} κ_{rst} ,

where

κ_{rst} = ∑_{m_{1}=0}^{r−1} ∑_{m_{2}=0}^{s−1} ∑_{m_{3}=0}^{t−1} \binom{m_{1} + m_{2} + m_{3}}{m_{1}, m_{2}, m_{3}} .

The same method of proof used in Proposition 6 yields (with a little more effort) a multinomial generatlization. Proposition 7. Let p ≥ 3 be prime, then

∑_{m_{1}=0}^{p−1} … ∑_{m_{n}=0}^{p−1} \binom{m_{1} + … m_{n}}{m_{1}, …, m_{n}} ≡_{p} 1 .

More generally, we conjecture Proposition 7’. Let p ≥ 3 be prime, and let r_{1}, …, r_{n} be positive integers, then

∑_{m_{1}=0}^{r_{1}p−1} … ∑_{m_{n}=0}^{r_{n}p−1} \binom{m_{1} + … m_{n}}{m_{1}, …, m_{n}} ≡_{p} κ_{r_{1}...r_{n}} ,

where

κ_{r_{1}...r_{n}} = ∑_{m_{1}=0}^{r_{1}−1} … ∑_{m_{n}=0}^{r_{n}−1} \binom{m_{1} + … m_{n}}{m_{1}, …, m_{n}} .

References

[AZ] Moa Apagodu and Doron Zeilberger, Multi-Variable Zeilberger and Almkvist-Zeilberger Algorithms and the Sharpening of Wilf-Zeilberger Theory, Adv. Appl. Math. 37 (2006), 139-152.

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/multiZ.html .

[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 before print), DOI:10.1080/10236198.2016.1142541. Volume and page tbd. Available from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/ctcong.html .

[Sl] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, http://oeis.org/ .

[St] Richard Stanley, “Catalan Numbers”, Cambridge University Press, 2015.

[Wi] The Wikipedia Foundation, The Freshman’s Dream .

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

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

First Written: June 8, 2016 ; This version: June 8, 2016 .