Archive

Number Theory

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

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

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.

 

Summary

The Catalan numbers are defined by

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

This note will use results obtained by Liu and Yeh in [1] to obtain a formula for the number of C_n < 2^{ t } which are divisible by 2^{ k }   where   t,  k   \in   \mathbb{N}.

Firstly, as in [1], let the p-adic order of a positive integer n be defined by

\omega_p(\, n )\, := max\{\alpha \in \mathbb{N} : p^{\alpha} | n\} .

and the cofactor of n with respect to  p^{ \omega_p(\, n )\, }  be defined by

CF_p(\, n )\,  := \frac {n} {p^{\omega_p(\, n )\,}} .

In addition the function \alpha : \mathbb{N} \to \mathbb{N}  is defined by

\alpha (\, n )\, := \frac {CF_2(\, n + 1 )\, - 1} {2}.

For a number p, we write the base p expansion of a number n as

[\, n ]\,_{p} = \langle n_{r} n_{r-1} ... n_{1} n_{0} \rangle

where n_{i} \in [\, 0, p - 1]\,  and n = n_{r} p^{r} + n_{r-1} p^{r-1} + ... + n_{1} p + n_{0}.

Then the function d : \mathbb{N} \to \mathbb{N} := d (\, n )\, = n_{r} + n_{r-1} + ... + n_{1} + n    is the sum of the p-adic digits of a natural number n (i.e. the sum of the digits of n when n is written in base p). Here we will only be interested in the case p = 2 . Then

Theorem   1:   \#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \binom {t} {k + 1}.

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

Corollary   3:   \#\{n < 2^t: C_{n} \equiv 2^{k-1} \mod {2^k} \} =  \binom{t} {k}.

Proofs.

Proof of Theorem 1:

Let   \alpha = \alpha (\, n )\, = \frac {CF_2(\, n + 1 )\, - 1} {2} .  Then

n + 1 = 2^{s} (\, 2^{\alpha} + 1 )\,

for some arbitrary s \in \mathbb{N} : s  \geq 0 .  Writing n + 1  in base 2 we have

[\, n + 1 ]\,_{2} = \langle [\, \alpha ]\,_{2}, 1, 0 ... 0, 0 \rangle  where there are s  0’s at the end and s \geq 0  is arbitrary. So,

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 ... 1, 1 \rangle  where there are s  1’s  at the end and s \geq 0  is arbitrary. It can be seen that d(\, n )\, = d(\, \alpha )\, + s.

Since n < 2^{t}  and  d(\, \alpha (\, n )\, )\, = k  the possible base 2 representations of n are

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0 \rangle  with \alpha < 2^{t - 1}

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1 \rangle  with \alpha < 2^{t - 2}

.

.

.

[\, n ]\,_{2} = \langle [\, \alpha ]\,_{2}, 0, 1, 1, ... 1 \rangle  with \alpha < 2^{k}  and (\, t - k - 1)\,   1’s at the end.

Therefore, counting each of these possibilities and using the fact that d (\, \alpha )\, = k  gives

\#\{n < 2^t: d(\, \alpha (\, n )\, )\, = k \} = \sum_{i = k}^{i = t - 1} \binom{i} {k} = \binom{t} {k + 1}.

\Box

 Proof of Corollary 2.

The following result appears in [1].

Theorem 4 (Corollary 4.3 of [1]): In general, we have \omega_{2} (\,  C_{n} )\, = d (\, \alpha )\, .   In particular,  C_{n} \equiv 0 (\,  mod  2^{k}  )\,  if and only if  d (\, \alpha )\, \geq k   ,  and  C_{n} \equiv 2^{k - 1} (\,  mod   2^{k}  )\,    if and only if  d (\, \alpha )\, = k - 1.

 

Corollary 2 follows from Theorem 1 and Theorem 4 above since

\#\{n < 2^t: C_{n} \equiv 0 \mod {2^k} \} = \#\{n < 2^t: d(\, \alpha (\, n )\,  )\,  \geq k \}  from Theorem 4

= 2^{t} - 1 -  \sum_{i = 0}^{i = k - 1} \#\{n < 2^t: d(\, \alpha (\, n )\,  )\,  = i \}

= 2^{t} - 1 - \sum_{i = 0}^{i = k - 1} \binom{t} {i + 1}  from Theorem 1

= 2^{t} - \sum_{i = 0}^{i = k} \binom{t} {i}

= \sum_{i = k + 1}^{i = t} \binom{t} {i}  since   2^{t} = \sum_{i = 0}^{i = t} \binom{t} {i}

\Box

Proof of Corollary 3.

From Theorem 4,

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

= \binom{t} {k}  from Theorem 1.

\Box

Reference

[1]  Liu, S.-C., & Yeh, J. (2010). Catalan numbers modulo 2^k. J Integer Sequences. Vol 13 (2010) Article 10.5.4