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

DOI10.1080/10236198.2016.1142541MaRDI QIDQ2816619zbMATH OpenOpenAlexFDO

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)

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

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)

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

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

Cites work

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

Cited in

(12)

• Constant term evaluation and two kinds of congruence
• A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences
• How to generate all possible rational Wilf-Zeilberger pairs?
• Using the ``Freshman's dream to prove combinatorial congruences
• 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
• CTcong.txt
• Congruence properties of combinatorial sequences via walnut and the Rowland-Yassawi-Zeilberger automaton
• Reduction for congruences of partial sums of P-recursive sequences
• Congruences and telescopings of \(P\)-recursive sequences

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)