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](https://arxiv.org/pdf/2001.00393.pdf) (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](https://en.wikipedia.org/wiki/Motzkin_number) (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](https://oeis.org/A081706) listed on OEIS. In fact, whenever that happens, $\nu\_2(a\_n)=1$ and $\nu\_2(b\_n)\in\{1,2\}$.



A moment sequence and Motzkin numbers. Modular coincidence?
Let's start with $b\_n$. Since Catalan number $C\_k$ is odd iff $k=2^m-1$, from [Lucas theorem](https://en.wikipedia.org/wiki/Lucas%27s_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](http://oeis.org/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}.$$


