A method for determining the mod-$2^k$ behaviour of recursive sequences, with applications to subgroup counting

Manuel Kauers; Christian Krattenthaler; T. Mueller

doi:10.37236/2433

A method for determining the mod-$2^k$ behaviour of recursive sequences, with applications to subgroup counting

Manuel Kauers
, Christian Krattenthaler
, T. Mueller

Research Institute for Symbolic Computation

Research output: Contribution to journal › Article › peer-review

Abstract

We present a method to obtain congruences modulo powers of $2$ for sequences given by recurrences of finite depth with polynomial coefficients. We apply this method to Catalan numbers, Fu\ss--Catalan numbers, and to subgroup counting functions associated with Hecke groups and their lifts. This leads to numerous new results, including many extensions of known results to higher powers of $2$.

Original language	English
Pages (from-to)	1-76
Number of pages	76
Journal	The Electronic Journal of Combinatorics
Volume	18
Issue number	2
DOIs	https://doi.org/10.37236/2433
Publication status	Published - 2012

Fields of science

101001 Algebra
101002 Analysis
101 Mathematics
102 Computer Sciences
102011 Formal languages
101009 Geometry
101013 Mathematical logic
101020 Technical mathematics
101025 Number theory
101012 Combinatorics
101005 Computer algebra
101006 Differential geometry
101003 Applied geometry
102025 Distributed systems

JKU Focus areas

Computation in Informatics and Mathematics

Access to Document

10.37236/2433

Cite this

@article{61823cc5c04a475b9601cb1a2f7da5bb,

title = "A method for determining the mod-\$2\textasciicircum{}k\$ behaviour of recursive sequences, with applications to subgroup counting",

abstract = "We present a method to obtain congruences modulo powers of \$2\$ for sequences given by recurrences of finite depth with polynomial coefficients. We apply this method to Catalan numbers, Fu\textbackslash{}ss--Catalan numbers, and to subgroup counting functions associated with Hecke groups and their lifts. This leads to numerous new results, including many extensions of known results to higher powers of \$2\$.",

author = "Manuel Kauers and Christian Krattenthaler and T. Mueller",

year = "2012",

doi = "10.37236/2433",

language = "English",

volume = "18",

pages = "1--76",

journal = "The Electronic Journal of Combinatorics",

issn = "1077-8926",

number = "2",

}

TY - JOUR

T1 - A method for determining the mod-$2^k$ behaviour of recursive sequences, with applications to subgroup counting

AU - Kauers, Manuel

AU - Krattenthaler, Christian

AU - Mueller, T.

PY - 2012

Y1 - 2012

N2 - We present a method to obtain congruences modulo powers of $2$ for sequences given by recurrences of finite depth with polynomial coefficients. We apply this method to Catalan numbers, Fu\ss--Catalan numbers, and to subgroup counting functions associated with Hecke groups and their lifts. This leads to numerous new results, including many extensions of known results to higher powers of $2$.

AB - We present a method to obtain congruences modulo powers of $2$ for sequences given by recurrences of finite depth with polynomial coefficients. We apply this method to Catalan numbers, Fu\ss--Catalan numbers, and to subgroup counting functions associated with Hecke groups and their lifts. This leads to numerous new results, including many extensions of known results to higher powers of $2$.

U2 - 10.37236/2433

DO - 10.37236/2433

M3 - Article

SN - 1077-8926

VL - 18

SP - 1

EP - 76

JO - The Electronic Journal of Combinatorics

JF - The Electronic Journal of Combinatorics

IS - 2

ER -