Automated Discovery and Proof of Congruence Theorems for Partial Sums of Combinatorial Sequences

By William Y.C. Chen, Qing-Hu Hou, and Doron Zeilberger

.pdf   .ps           [LaTeX source   .bbl]]

[Appeared in J. of Difference Equations and Applications 22 (2016), 780-788   ;
Written: Sept. 29, 2015

Many famous combinatorial sequences (e.g. the Catalan and Motzkin sequences) can be represented as constant terms of Q(x)P(x)i for some Laurent polynomials, P(x), Q(x), with integer coefficients. For these lucky seuqnces, if you add them up from the 0-th term to the (r*p-1)-th (for any given, fixed, r), and take it mod p, you can predict the answer right away, thanks to the neat, extremely simple, algorithm described in this article, and implemented in the Maple package.

Even more interesting is the general theorem, that under some conditions, there are always only finitely many congruence classes modulo p (of the studied partial sums), regardless of p, no matter how large!

This article was one of the fruits of my fruitful visit to "Bill Chen's field of dreams", where I enjoyed the amazing hospitality of my collaborators Bill Chen and Qing-Hu Hou, and I really enjoyed interacting with the brilliant young faculty and graduate students.

Here my picture standing in front of my office at the Center for Combinatorics, Aug. 12, 2015, kindly taken by Qing-Hu Hou.

Maple Package

Important: This article is accompanied by Maple package

  • CTcong.txt, a Maple package that discovers, and proves, congruence theorems for partial sums of important combinatorial sequences.

Sample Input and Output for the Maple package CTcong.txt

  • If you want to see congruence theorems for the partial sums to p-1, 2p-1, ..., 10p-1, for the Central Binomial, Catalan, Motzkin, and Central Pentagonal numbers, the

    input   yields the   output

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page