Using the “Freshman’s Dream” to Prove Combinatorial Congruences

By Moa APAGODU and Doron ZEILBERGER

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! We conclude with some super-challenges.

[Added June 26, 2016: Roberto Tauraso [T], has pointed out that most of our conjectured supercongruences are already known, except for super-congruence 6, for which he supplied a beautiful proof].

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, so 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, we have

∑_{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 positive integer r. This leads to the following proposition, whose somewhat tedious proof we omit. Proposition 1”. For any prime 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] .

The sequence α_{r} is Sequence A6134 ([Sl],https://oeis.org/A006134). Note that α_{r} is the number of ways of tossing a coin < 2r times and getting as many Heads as Tails.

The most ubiquitous sequence in combinatorics is sequence A000108 in the OEIS ([Sl], https://oeis.org/A000108, that according to Neil Sloane is the longest entry!), the superfamous Catalan Numbers, C_{n} := \frac{(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)(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, since 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. In fact, one can keep r general, but then the proof is rather tedious, and we will spare the readers (and ourselves, from typing it).

Proposition 2’. Let C_{n} be the Catalan Numbers, then, for any positive integer r, we have

∑_{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 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 ≡ 3 (mod 4).

The same method, applied to a general r yields

Proposition 3’. Let M_{n} be the Motzkin numbers, and let p ≥ 3 be prime, then

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

where δ_{r} is the sequence of partial sums of the central trinomial coefficients, sequence A097893 in the OEIS([Sl], https://oeis.org/A097893) whose generating function is

∑_{r=0}^{∞} δ_{r}x^{r} = \frac{1}{(1 − x) \sqrt{(1 + x) (1 − 3 x)}} .

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-Variables

We now extend the Chen-Hou-Zeilberger method for discovery and proof of congruence theorems to multi-sums and multi-variables.

Proposition 5. Let p ≥ 5 be prime, 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} ≡_{p} a^{p} + b^{p}, we can pass to mod p as above, and 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 ≡ 0(mod 3), −1 when n ≡ 1 (mod 3), and 0 when n ≡ 2 ( mod 3). 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 extract the coefficient of y^{n}. Another way is by using the Apagodu-Zeilberger algorithm ([AZ]), that outputs that the sequence of diagonal coefficients, let’s call them a(n), 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, then we have

∑_{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{x^{p} + y^{p}}{x + y} )

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

With more effort, one can get the following generalization.

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

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 .

In fact, the following also holds.

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

Super Congruences

If a congruence identity that is valid modulo a prime p, is also valid modulo p^{2} (or better still, modulo p^{3} and beyond) then we have a super-congruence. The grandmother of all supercongruences is Wolstenholme’s Theorem([Wo], see also [We]) that asserts that

\binom{2p − 1}{p − 1} ≡_{p^{3}} 1 ,

that improves on the weaker version \binom{2p−1}{p−1} ≡_{p^{2}} 1, first proved by Charles Babbage ([B]), better known for more impressive innovations.

To our surprise, most (but not all!) the above congruences have super-congruence extensions. The method of [CHZ], as it stands now, is not applicable, since the “Freshman’s Dream” is only valid modulo p, hence we have no clue how to prove them. We leave them as challenges to our readers.

Super-Conjecture 1. For any prime p ≥ 5

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

More generally

Super-Conjecture 1”. For any prime p ≥ 5, and any positive integer, r,

∑_{n=0}^{rp−1} \binom{2n}{n} ≡_{p^{2}} \{ \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} .

Update, June 16, 2016: Dennis Stanton proved Super-Conjectures 1 and 1′. See his nice writeup

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/freshmanDennisStanton.pdf.

His method should also work for Super-Conjectures 2, and probably 2′. Update, June 17, 2016: Roberto Tauraso([T]) pointed out that Super-Conjecture 1 is already known, see [T] for references. Super-Conjecture 2. Let C_{n} be the Catalan Numbers, then, for every prime p ≥ 5,

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

Update, June 17, 2016: Roberto Tauraso([T]) pointed out that Super-Conjecture 2 is already known, see [T] for references.. More generally, Super-Conjecture 2’. Let C_{n} be the Catalan Numbers, then, for any positive integer r, we have

∑_{n=0}^{rp−1} C_{n} ≡_{p^{2}} \{ \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} .

We note that poor Motzkin does not seem to have a super-extension, but Proposition 5 sure does! Super-Conjecture 5. Let p ≥ 5 be prime, then

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

Update, June 17, 2016: Roberto Tauraso([T]) pointed out that Super-Conjecture 5 follows easily from what we called Super-Conjecture 1, see [T] for details. More generally Super-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^{2}} \{ \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} .

The most pleasant surprise is that Propositions 6 and 6’ can be “upgraded” to a cubic supercongruence, i.e. it is still true modulo p^{3}.

Super-Conjecture 6. Let p > 2 be prime, then we have

∑_{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^{3}} 1 .

Update, June 17, 2016: Roberto Tauraso([T]) has supplied a beautiful proof, highly recommended.

More generally

Super-Conjecture 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^{3}} κ_{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}} .

To our bitter disappointment, Propositions 7 and 7’, for n ≥ 4 summation signs, do not have super-upgrades.

Lots and Lots of Combinatorial Challenges

Perhaps the nicest proof of Fermat’s Little Theorem, a^{p} ≡_{p} a, is Golomb’s ([G]) combinatorial proof, that notes that a^{p} is the number of (straight) necklaces with p beads, using beads of a different colors, and hence a^{p} − a is the number of such (straight) necklaces that are not all of the same color. For any such necklace, all its p circular rotations are distinct (since p is prime), hence the set of such necklaces can be divided into families, each of them with p members, and hence there are (a^{p} − a)/p ‘circular’ necklaces (without clasp), and this must be an integer.

Each and every quantity in the above propositions and conjectures counts a natural combinatorial family. For example ∑_{n=0}^{p−1} \binom{2n}{n} counts the number of binary sequences with the same number of 0’s and 1’s whose length is less than 2p. Can you find a member of this set that when you remove it, and p ≡ 1 (mod 3), you can partition that set into families each of them with exactly p (or better still, for the super-congruence, p^{2}) members?, and when p ≡ 2 (mod 3), can you find two such members?

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 .

[B] Charles Babbage, Demonstration of a theorem relating to prime numbers, Edinburgh Philosophical J. 1(1819), 46-49.

[CHZ] William Y.C. Chen, Qing-Hu Hou, and Doron 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 .

[G] Solomon W. Golomb, Combinatorial proof of Fermat’s “Little” Theorem, American Mathematical Monthly 63(1956), 718.

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

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

[T] Roberto Tauraso, A (human) proof of a triple binomial sum supercongruence, http://arxiv.org/abs/1606.05543 .

[We] Eric W. Weisstein, Wolstenholme’s Theorem, From MathWorld–A Wolfram Web Resource.

http://mathworld.wolfram.com/WolstenholmesTheorem.html .

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

[Wo] Joseph Wolstenholme, On certain properties of prime numbers, Quart. J. Pure Appl. Math. 5 (1862), 35-39.

Moa Apagodu, Department of Mathematics, Virginia Commonwealth University, Richmond, VA 23284, USA; mapagodu at vcu dot edu .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA; zeilberg at math dot rutgers dot edu .

First Written: June 9, 2016 ; This version: June 26, 2016 . 13