Using the "Freshman's Dream" to Prove Combinatorial Congruences

By Moa Apagodu and Doron Zeilberger


Appeared   in the American Mathematical Monthly, v. 124 No. 7 (Aug.-Sept. 2017), 597-608.


Original version: .pdf   .ps   .tex  


First written: June 9, 2016

This version: June 26, 2016


Appeared   in the American Mathematical Monthly, v. 124 No. 7 (Aug.-Sept. 2017), 597-608.


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.


Update, June 16, 2016: Dennis Stanton proved super-conjectures 1 and 1', and kindly permitted me to post his nice proofs here  

Update, June 16, 2016: Dennis Stanton informed us that his method of proof also applies to super-conjecture 2, and most probably (with a little more work) to super-congruence 2'.

Update, June 16, 2016: Roberto Tauraso informed (and sent us a draft) of a nice proof of super-conjecture 6. As soon as it posted in the internet, we will put a link to it here.

Update, June 26, 2016: Roberto Tauraso wrote a nice proof of super-congruence 6 to the arxiv, in a paper entitled A (Human) proof of a triple binomial sum congruence.

Update, July 11, 2016: Tewodros Amdeberhan and Roberto Tauraso found far-reaching generalizations in a paper entitled Two Triple binomial sum supercongruences.


Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page