Catalan and Motzkin numbers modulo 4 and 8 (Q932826)

\noindent Let \(C_n\) and \(M_n\) be the \(n\)th Catalan and Motzkin numbers, respectively. It is well-known and easy to prove that \(C_n\) is odd if and only if \(n+1\) is a power of \(2\). The values of \(n\) for which \(M_n\) is odd were classified by \textit{E.~Deutsch} and \textit{B. E. Sagan} [J. Number Theory 117, No. 1, 191--215 (2006; Zbl 1163.11310)]. This nice paper goes further and looks at Catalan and Motzkin numbers modulo \(4\) and \(8\). The Catalan numbers modulo \(8\) are classified in Theorem 4.2. For example, they are zero modulo 8 if the binary expansion of \(n+1\) has at least \(4\) bits. For values of \(n\) with \(n+1\) having at most three bits, \(C_n\) is not zero modulo \(8\). Further, \(C_n\) is never \(3\) modulo \(4\). The Motzkin numbers modulo \(8\) are classified in Theorem 5.5. As a byproduct of their results, the authors conclude that \(M_n\) is zero modulo \(4\) if and only if \(n+\delta=(4i+2\delta-1)4^{j+1}\) for some integers \(i\geq 0\), \(j\geq 0\), \(\delta\in \{1,2\}\), thus confirming a conjecture of Deutsch and Sagan. Furthermore, \(M_n\) is never zero modulo \(8\). The proofs use Kummer's theorem on the exponent of a prime dividing a binomial coefficient and Lucas' theorem giving the value of \({n\choose k}\) modulo a prime \(p\) in terms of the product of the binomial coefficients of the corresponding \(p\)-adic digits and involve a detailed analysis of the binary expansion of \(n\). For example, after finding \(C_n\) modulo \(8\) for all \(n\), the authors find \(M_n\) modulo \(8\) via the formula \[ M_n=\sum_{k\geq 0} {n\choose {2k}}C_k. \]