# Asymptotic densities of Catalan numbers modulo 2^k

The Catalan numbers are defined by

$C_n = \frac{1}{n + 1} \binom {2n} {n}.$

Corollary 2 of the previous post established that

$\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \sum_{i = k+1}^{i = t} \binom{t} {i}.$

This result can be used to show that the asymptotic density of the set $\#\{n < N: C_{n} \equiv 0 \mod {2^k} \}$ is $1.$

To this end let $N \in \mathbb{N}: 2^{r} \leq N < 2^{r+1}$ for some $r \in \mathbb{N}.$ Then  $r = \lfloor \log_2(\, N)\, \rfloor$ and

$\#\{n < N: d(\, \alpha (\, n )\, )\, = k \} \leq \#\{n < 2^{r+1}: d(\, \alpha (\, n )\, )\, = k \} = \binom {r+1} {k + 1}.$

So, as mentioned in the previous post

$\#\{n < N: C_{n} \equiv 0 \mod {2^k} \} = N - \#\{n < N: d(\, \alpha (\, n )\, )\, < k \}$

$= N - \sum_{i = 0}^{i = k - 1} \#\{n < N: d(\, \alpha (\, n )\, )\, = i \} \geq N - \sum_{i = 0}^{i = k - 1} \binom {r+1} {i + 1}.$

And so

$\frac {1}{N} \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} \geq 1 - \frac {1}{N} P_{k} (\, r )\,$

$= 1 - \frac {1}{N} P_{k} (\, \lfloor \log_2 (\, N )\, \rfloor )\,$

where $P_{k} (\, r )\,$ is a polynomial in $r$ of degree $k$ with coefficients depending on $k$. Since $k$ is fixed and $lim_{N \to \infty} \frac {1}{N} (\, log_2{N} )\, ^{k} = 0$ for fixed $k$ the second term above is zero in the limit and

$lim_{N \to \infty} \frac {1}{N} \#\{n < N: C_{n} \equiv 0 \mod {2^k} \} = 1.$

This result is not surprising given the highly composite nature of the Catalan numbers. In general we would also expect that the same result holds with $2^{k}$ replaced by any natural number.

Advertisements