Automated discovery and proof of congruence theorems for partial sums of combinatorial sequences

DOI10.1080/10236198.2016.1142541zbMATH Open1368.11020arXiv1509.09070OpenAlexW2173952281MaRDI QIDQ2816619FDOQ2816619

Authors: William Y. C. Chen, Qing-Hu Hou, Doron Zeilberger 

Publication date: 25 August 2016

Published in: Journal of Difference Equations and Applications (Search for Journal in Brave)

Abstract: Many combinatorial sequences (for example, the Catalan and Motzkin numbers) may be expressed as the constant term of $P(x{)}^{k}Q(x)$, for some Laurent polynomials $P(x)$ and $Q(x)$ in the variable $x$ with integer coefficients. Denoting such a sequence by $a_k$, we obtain a general formula that determines the congruence class, modulo $p$, of the indefinite sum $su{m}_{k=0}^{rp-1}{a}_k$, for {it any} prime $p$, and any positive integer $r$, 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 $p$.

Full work available at URL: https://arxiv.org/abs/1509.09070

Recommendations

• Using the ``Freshman's dream to prove combinatorial congruences
• Automatic congruences for diagonals of rational functions
• Congruences and telescopings of \(P\)-recursive sequences
• Constant term evaluation and two kinds of congruence
• On congruence schemes for constant terms and their applications

zbMATH Keywords

polynomialsLaurent seriesLegendre symbolcombinatorial sequences

Mathematics Subject Classification ID

Symbolic computation and algebraic computation (68W30) Combinatorial identities, bijective combinatorics (05A19) Other combinatorial number theory (11B75)

Cites Work

• Factoring polynomials with rational coefficients
• A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences
• Another congruence for the Apéry numbers
• Congruences involving generalized central trinomial coefficients
• A combinatorial identity with application to Catalan numbers

Cited In (9)

• A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences
• On two conjectural supercongruences of Apagodu and Zeilberger
• The research and progress of the enumeration of lattice paths
• Automatic proofs for formulae enumerating proper polycubes
• Elementary proof of congruences involving sum of binomial coefficients
• How to Generate All Possible Rational Wilf-Zeilberger Pairs?
• CTcong.txt
• Using the “Freshman′s Dream” to Prove Combinatorial Congruences
• Constant term evaluation and two kinds of congruence

This page was built for publication: Automated discovery and proof of congruence theorems for partial sums of combinatorial sequences

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2816619)