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

preprint2015arXivOpen access

Abstract

Many combinatorial sequences (for example, the Catalan and Motzkin numbers) may be expressed as the constant term of P(x)kQ(x)P(x)^k Q(x), for some Laurent polynomials P(x)P(x) and Q(x)Q(x) in the variable xx with integer coefficients. Denoting such a sequence by aka_k, we obtain a general formula that determines the congruence class, modulo pp, of the indefinite sum ∑k=0rp−1ak\sum_{k=0}^{rp -1} a_k, for {\it any} prime pp, and any positive integer rr, as a linear combination of sequences that satisfy linear recurrence (alias difference) equations with constant coefficients. This enables us (or rather, our computers) to automatically discover and prove congruence theorems for such partial sums. Moreover, we show that in many cases, the set of the residues is finite, regardless of the prime pp.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.