# A moment sequence and Motzkin numbers. Modular coincidence?

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

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}.$$
• Max: can you say a few words on the reason for congruence with the $2$-adic valuations? Oct 22, 2021 at 16:08
• @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$. Oct 22, 2021 at 16:13