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

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: