A Method for Determining the Mod-$2^k$ Behaviour of Recursive Sequences, with Applications to Subgroup Counting

  • M. Kauers
  • C. Krattenthaler
  • T. W. Müller


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