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

Institut für Symbolisches Rechnen

Publikation: Beitrag in Fachzeitschrift › Artikel › Begutachtung

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

Originalsprache	Englisch
Seiten (von - bis)	1-76
Seitenumfang	76
Fachzeitschrift	The Electronic Journal of Combinatorics
Volume	18
Ausgabenummer	2
DOIs	https://doi.org/10.37236/2433
Publikationsstatus	Veröffentlicht - 2012

Wissenschaftszweige

101001 Algebra
101002 Analysis
101 Mathematik
102 Informatik
102011 Formale Sprachen
101009 Geometrie
101013 Mathematische Logik
101020 Technische Mathematik
101025 Zahlentheorie
101012 Kombinatorik
101005 Computeralgebra
101006 Differentialgeometrie
101003 Angewandte Geometrie
102025 Verteilte Systeme

JKU-Schwerpunkte

Computation in Informatics and Mathematics

Zugriff auf Dokument

10.37236/2433

Dieses zitieren

@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 -