A Method for Determining the Mod-$2^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ß--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$.