# Asymptotic density of Motzkin numbers modulo 8

The Motzkin numbers $M_n$ are defined by $M_n := \sum_{k \geq 0} \binom {n}{2k} C_{k}$

where $C_{k}\,$ are the Catalan numbers. The following result is established in 

Theorem 1 (Theorem 5.5 of ). The nth Motzkin number $M_n$ is even if and only if $n = (4i + \epsilon)4^{j+1} - \delta$ for $i, j \in \mathbb{N}, \epsilon \in \{1, 3\}$ and $\delta \in \{1, 2\}$. Moreover, we have $M_n \equiv 4 \mod 8$ if $(\, \epsilon, \delta )\, = (\, 1, 1 )\,$ or $(\, 3, 2 )\,$ $M_n \equiv 4y + 2 \mod 8$ if $(\, \epsilon, \delta )\, = (\, 1, 2 )\, or (\, 3, 1 )\,$

where $\, y \,$ is the number of digit 1’s in the base 2 representation of $\, 4i + \epsilon - 1$.

Remark 2. The 4 choices for $(\, \epsilon, \delta )\,$ in the above theorem give 4 disjoint sets of numbers $n = (4i + \epsilon)4^{j+1} - \delta$.

Theorem 3. Each of the 4 disjoint sets defined by the choice of $(\, \epsilon, \delta )\,$ in Theorem 1 has asymptotic density $\frac {1}{12}$ in the natural numbers.

Proof: Use the result for the set $S_{1}$ of Theorem 1 of the post here with $q = 4, r = \epsilon, s = 1, t = 1$. $\Box \,$.

Corollary 4: The asymptotic density of $\{ n < N: M_n \equiv 0 \mod 2 \}$ is $\frac {1}{3}$.

The asymptotic density of $\{ n < N: M_n \equiv 4 \mod 8 \}$ is $\frac {1}{6}$.

The asymptotic density of each the sets $\{ n < N: M_n \equiv 2 \mod 8 \}$ and $\{ n < N: M_n \equiv 6 \mod 8 \}$ is $\frac {1}{12}$.

Remark 5: The first 2 statements of Corollary 4 follows immediately from theorems 1 and 3. The third statement follows from the observation that the numbers of 1’s in the base 2 expansion of $i$ is equally likely to be odd or even and therefore the same applies the the number of 1’s in the base 2 expansion of $4i + \epsilon - 1$. Since the asymptotic density of the 2 sets combined is $\frac {1}{6}$ (from Theorems 1 and 3), each of the two sets has asymptotic density of $\frac {1}{12}$.

## Reference

 Eu, S.-P., Liu, S.-C., & Yeh, Y.-N. (2008). Catalan and Motzkin numbers modulo 4 and 8. European Journal of Combinatorics, 29(6), 1449–1466. http://doi.org/10.1016/j.ejc.2007.06.019