I was looking at two sequences of integers, both with prominent place is combinatorics. The first one appears, for instance, in Stieltjes moment sequences for pattern-avoiding permutations (see page 23) $$a_n=\sum_{k=0}^n\frac{\binom{2k}k\binom{n+1}{k+1}\binom{n+2}{k+1}}{(n+1)^2(n+2)}.$$ The second appears in lattice path enumerations as Motzkin numbers (a close cousin of Catalan numbers) $$b_n=\sum_{k=0}^{\lfloor\frac{n}2\rfloor}\frac{\binom{n}{2k}\binom{2k}k}{k+1}.$$

In modulo $2$ arithmetic, I run into what seems to be a (happy) coincidence. Let me ask:

QUESTION. Is this true? $$a_n\equiv b_n \mod 2.$$

ADDED. $a_n$ or $b_n$ is even iff $n$ is part of this sequence listed on OEIS. In fact, whenever that happens, $\nu_2(a_n)=1$ and $\nu_2(b_n)\in\{1,2\}$.


1 Answer 1


Let's start with $b_n$. Since Catalan number $C_k$ is odd iff $k=2^m-1$, from Lucas theorem it follows that $$b_n=\sum_{k=0}^n \binom{n}{2k}C_k \equiv\sum_{m\geq 0}\binom{n}{2(2^m-1)}\equiv 1+\nu_2(\lfloor n/2\rfloor+1)\pmod2,$$ where $\nu_2(\cdot)$ is the 2-adic valuation.

Now consider $a_n$. From the recurrence given in OEIS A005802, $$(n^2 + 8n + 16)a_{n+2}=(10n^2 + 42n + 41)a_{n+1}-(9n^2 + 18n + 9)a_n,$$ we have $a_{2k+1}\equiv a_{2k}\pmod2$ for all $k$. It's therefore sufficient to consider even $n$, when $$a_n = \frac{1}{(n+1)^2}\sum_{k=0}^n C_k \binom{n+1}{k+1} \binom{n+1}{k} \equiv \sum_{m\geq 0} \binom{n+1}{2^m} \binom{n+1}{2^m-1}\equiv \nu_2(n+2)\pmod2.$$

Hence, for all $n$ we have $$a_n\equiv b_n\pmod{2}.$$

  • $\begingroup$ Max: can you say a few words on the reason for congruence with the $2$-adic valuations? $\endgroup$ Oct 22, 2021 at 16:08
  • $\begingroup$ @T.Amdeberhan: By Lucas theorem $\binom{n}{2(2^m-1)}\equiv \binom{\lfloor n/2\rfloor}{2^m-1}\pmod2$, and the latter binomial coefficient is odd iff $\lfloor n/2\rfloor\equiv 2^m-1\pmod{2^m}$, i.e. $\nu_2(\lfloor n/2\rfloor+1)\geq m$. $\endgroup$ Oct 22, 2021 at 16:13

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.