# Asymptotic densities of Motzkin numbers modulo 5

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 [1]

Theorem 1 (Theorem 5.4 of [1]). The Motzkin number $M_n$ is divisible by $5$ if and only if $n$ is one of the following forms

$(\, 5i + 1 )\, 5^{2j} - 2,\, (\, 5i + 2 )\, 5^{2j-1} - 1,\, (\, 5i + 3 )\, 5^{2j-1} - 2,\, (\, 5i + 4 )\, 5^{2j} - 1$

where $i, j \in \mathbb{N}$ and $j \geq 1$.

Theorem 2: The asymptotic density of numbers of the first form in theorem 1 is $\frac {1}{120}$. Numbers of the fourth form also have asymptotic density $\frac {1}{120}$. The asymptotic density of numbers of the second and third forms in theorem 1 is $\frac {1}{24}$ each.

Corollary 3: The asymptotic density of $\#\{n < N: M_{n} \equiv 0 \mod {5} \}$ is $\frac {1}{10} \,$.

Remark 4: Corollary 3 follows immediately from theorems 1 and 2 and the disjointness of the 4 forms of integers listed in theorem 1.

Remark 5: Numerical tests also show that roughly 22.5% of Motzkin numbers are congruent to each of $1, 2, 3, 4 \mod {5}$.

Proof of Theorem 2.

Firstly consider numbers of the form $(\, 5i + 1)\, 5^{2j} - 2\,$. As we are interested in asymptotic density it is enough to look at numbers of the form $(\, 5i + 1)\, 5^{2j}\,$. We have, for fixed $j \geq 1$,

$\#\{ i \geq 0: (\, 5i + 1)\, 5^{2j} \leq N \} = \frac {N}{5^{2j+1}} - \frac {1}{5} - E(\, j, N )\,$

where $0 \leq E( \, j, N ) < 1$ is an error term introduced by not rounding down to the nearest integer. So,

$\#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= \sum_{j \geq 1} (\, \frac {N}{5^{2j+1}} - \frac {1}{5} - E(\, j, N )\, )\, = \sum_{j = 1}^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\, \rfloor} (\, \frac {N}{5^{2j+1}} - \frac {1}{5} - E(\, j, N )\, )\,$

$= \frac {N}{125} \sum_{j = 0}^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\, \rfloor - 1} (\, \frac {1}{25} )\,^{j} - E^{'}(\, N )\,$

where the new error term $E^{'} (\, N )\,$ satisfies $0 \leq E^{'} (\, N )\, < \frac{3}{5} (\, \log_{5} (\, N )\,$. Then

$\#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \}$

$= (\, \frac {N}{125} )\, \frac {1 - (\, \frac {1}{25} )\,^{\lfloor \frac{1}{2} (\, \log_{5} (\, N )\,- 1 )\, \rfloor} }{1 - \frac {1}{25} } - E^{'}(\, N )\,$.

Since $\lim_{N \to \infty} \frac {E^{'}(\, N )\, }{N} = 0$

$\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, 5i + 1)\, 5^{2j} \, for some \, i, j \in \mathbb{N} \, with \, j \geq 1 \} = \frac {1}{120}$.

A similar argument can be used to establish the asymptotic densities of the other 3 forms of numbers in the theorem.

$\Box$.

## References

[1] Deutsch, E., & Sagan, B. E. (2006). Congruences for Catalan and Motzkin numbers and related sequences. Journal of Number Theory, 117(1), 191–215. http://doi.org/10.1016/j.jnt.2005.06.005