Archive

Monthly Archives: November 2016

The recent posts regarding Catalan and Motzkin numbers have been consolidated in two papers at arXiv. They are located at https://arxiv.org/pdf/1611.04910v1.pdf (Asymptotic density of Motzkin numbers modulo small primes) and https://arxiv.org/pdf/1611.03705v1.pdf (Asymptotic density of Catalan numbers modulo 3 and powers of 2).

Advertisements

In previous posts we have established the asymptotic densities of the Motzkin numbers modulo 2^{k}, k \in \{1, 2, 3 \} and 5. The main result of this note is that

Theorem 1. 

\lim_{N \to \infty} \frac {1}{N} \#\{n \leq N: M_n \equiv 0 \mod 3 \} = 1.

 

Firstly, let T(\, 01 )\, denote the set of natural numbers which have a base 3 expansion containing only the digits 0 and 1. The following theorem from [1] will be used to prove theorem 1.

Theorem 2. (Corollary 4.10 of [1]). The Motzkin numbers satisfy

M_n \equiv  -1 \mod 3 \quad if  \quad n \in 3T (\, 01 )\, - 1,

M_{n} \equiv 1 \mod 3 \quad  if  \quad n \in 3T(\, 01 )\quad or \quad n \in 3T(\, 01 )\, - 2,

M_n \equiv 0 \mod 3 \quad otherwise.

 

We will first examine the nature of the set T(\, 01 \,). We have

Theorem 3. The asymptotic density of the set T(\, 01 \,) is zero.

Proof: 

Choose k \in N: 3^{k} \leq N < 3^{k+1}. Then k = \lfloor log_3 (\, N )\, \rfloor and

\frac {1}{N} \# \{ n \leq N :  n \in  T(01) \}  \leq \frac {2^{k+1}}{N} \leq \frac {2^{k+1}}{3^{k}} \to 0 as N \to \infty.

\Box \, .

 

Proof of Theorem 1.

Since the asymptotic density of T(\, 01 \,) is zero, so is the asymptotic density of the sets 3T(\, 01 \,) - k for k \in \{0, 1, 2\}. Therefore Theorem 2 implies that

\lim_{N \to \infty} \frac {1}{N} \# \{n \leq N : M_n \equiv +-1 \mod 3 \} = 0

and the result follows.

\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

This note will establish formulae for the asymptotic densities in the natural numbers of two sets of numbers.  These sets are S_{1}(\, q, r, s, t )\, = \{ (\, qi + r )\, q^{sj + t} : i, j \in \mathbb{N} \} \quad

and

S_{2}(\, q, r, s, t )\, = \{ (\, qi + r )\, q^{sj + t} : i, j \in \mathbb{N}, j > 0 \}

for integers \quad q, r, s, t.

 

Theorem 1. Let \quad q, r, s, t \in \mathbb{Z} \quad with \quad q, r, s > 0 \quad and \quad 0 < r < q \quad. Then the asymptotic density of the set S_{1} \quad is \quad (\, q^{t + 1 - s} (\, q^{s} - 1 )\, )\, ^{-1} \quad. In addition the asymptotic density of the set \, S_{2} \, is \, (\, q^{t + 1} (\, q^{s} - 1 )\, )\, ^{-1}.

Proof.

We firstly look at S_{1}. We have, for fixed j \geq 0,

\#\{ i \geq 0: (\, qi + r)\, q^{sj + t} \leq N \} = \frac {N}{q^{qj+t+1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\,

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

U(N, s, t) =: \quad \lfloor  \frac {\log_q (\, N )\, - t - 1}{s} \rfloor \quad \,,

we have

\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some  \, i, j \in \mathbb{N} \}

= \sum_{j \geq 0} (\, \frac {N}{q^{sj + t + 1}}  - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\, = \sum_{j = 0}^{U} (\, \frac {N}{q^{sj+t + 1}}  - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\,

= \frac {N}{q^{t + 1} } \sum_{j = 0}^{U} (\, \frac {1}{q^{s}} )\,^{j} - E^{'}(\, N, q, r, s, t )\,

where the new error term E^{'} (\, N, q, r, s, t )\, satisfies 0 < E^{'} (\, N, q, r, s, t )\, < 2(\, U + 1 )\, .

Then

\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some  \, i, j \in \mathbb{N} \}

= (\, \frac {N}{q^{t+1}} )\, (\, 1 - (\, \frac {1}{q^{s}} )\, ^{U + 1} )\,  (\, 1 - \frac {1}{q^{s} } )\, ^{-1} - E^{'}

Since \lim_{N \to \infty} \frac {E^{'}(\, N, q, r, s, t )\, }{N} = 0 and \lim_{N \to \infty} \frac {1}{N} (\, \frac {1}{q^{s} } )\, ^{U + 1} = 0

\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some  \, i, j \in \mathbb{N} \}

= (\, q^{t + 1 - s} (\, q^{s} - 1 )\,)\, ^{-1}.

The proof for S_{2} is very similar. With E, E^{'} and U defined as above we have for fixed j \geq 1,

\#\{ i \geq 0: (\, qi + r)\, q^{sj + t} \leq N \} = \frac {N}{q^{qj+t+1}} - \frac {r}{q} - E(\, j, N, q, r, s, t )\,

and

\#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some  \, i, j \in \mathbb{N} \, with \, j \geq 1 \}

= \sum_{j \geq 1} (\, \frac {N}{q^{sj + t + 1}}  - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\, = \sum_{j = 1}^{U} (\, \frac {N}{q^{sj+t + 1}}  - \frac {r}{q} - E(\, j, N, q, r, s, t )\, )\,

= \frac {N}{q^{t + 1 + s} } \sum_{j = 0}^{U - 1} (\, \frac {1}{q^{s}} )\,^{j} - E^{'}(\, N, q, r, s, t )\,

= (\, \frac {N}{q^{t+1+s}} )\, (\, 1 - (\, \frac {1}{q^{s}} )\, ^{U} )\,  (\, 1 - \frac {1}{q^{s} } )\, ^{-1} - E^{'}

and

\lim_{N \to \infty} \frac {1}{N} \#\{n < N: n = (\, qi + r)\, q^{sj + t} \, for some  \, i, j \in \mathbb{N} \, with \, j \geq 1 \}

= (\, q^{t + 1 } (\, q^{s} - 1 )\,)\, ^{-1}.

 

\Box.

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.5 of [1]). 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

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