Congruences and the Thue-Morse sequence

Emeric Deutsch Department of Mathematics Polytechnic University Brooklyn, NY 11201, USA

deutsch@duke.poly.edu

Bruce E. Sagan Department of Mathematics Michigan State University East Lansing, MI 48824-1027

sagan@math.msu.edu

www.math.msu.edu/˜ sagan

1. Central binomial coefficients

2. Catalan numbers

3. Motzkin numbers

4. Open problems 1. Central binomial coefficients Let

ρ_{3}(n) = remainder of n on division by 3. Consider

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ ρ_{3} \binom{2n}{n} & 1 & 2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 2 \end{matrix}

Let

(n)_{3} = n_{l} … n_{0}, sequence of digits of n base 3. Let

T (01) = {n : (n)_{3} has only zeros and ones }. and

ω_{3}(n) = number of ones in (n)_{3}.

Benoit Cloitre and Reinhard Zumkeller conjectured the following. Theorem 1 (D & S) We have

\binom{2n}{n} ≡ \{ \begin{matrix}(−1)^{ω_{3}(n)} & if n ∈ T (01), \\ 0 & else. \end{matrix} \} (mod 3)

Theorem 2 (Lucas, 1877–8) Let p be prime and let (n)_{p} = n_{l} … n_{1}n_{0} and (k)_{p} = k_{l} … k_{1}k_{0}. Then

\binom{n}{k} ≡ \binom{n_{l}}{k_{l}} ⋯ \binom{n_{1}}{k_{1}}\binom{n_{0}}{k_{0}} (mod p).

Corollary 3 If there is a carry in computing the sum (k)_{p} + (n − k)_{p} then

\binom{n}{k} ≡ 0 (mod p).

Proof Let i be the right-most place where there is a carry. So k_{i} > n_{i} and \binom{n_{i}}{k_{i}} = 0. Now use Lucas.

Theorem 1 (D & S) We have

\binom{2n}{n} ≡ \{ \begin{matrix}(−1)^{ω_{3}(n)} & if n ∈ T (01), \\ 0 & else. \end{matrix} \} (mod 3)

Proof If there is a 2 in (n)_{3} then there is a carry in (n)_{3} + (n)_{3} so \binom{2n}{n} ≡ 0 (mod 3) by the Corollary.

Otherwise n ∈ T (01). So n_{i} = 1 iff the ith digit of 2n is 2. So by Lucas

\binom{2n}{n} ≡ \binom{2}{1}^{ω_{3}(n)} ≡ (−1)^{ω_{3}(n)} (mod 3).

Theorem 1 (D & S) We have

\binom{2n}{n} ≡ \{ \begin{matrix}(−1)^{ω_{3}(n)} & if n ∈ T (01), \\ 0 & else. \end{matrix} \} (mod 3)

The Thue-Morse sequence is t = (t_{0}, t_{1}, t_{2}, …) defined recursively by t_{0} = 0 and for n ≥ 1

(t_{2^{n}}, …, t_{2^{n+1} −1} ) = 1 − (t_{0}, …, t_{2^{n}−1} ).

So

t = (0, 1, 1, 0, 1, 0, 0, 1, …)

Benoit Cloitre conjectured the following.

Theorem 4 (D & S) We have

(ρ_{3}(n) : \binom{2n}{n} ≡ 1 (mod 3)) = t

and

(ρ_{3}(n) : \binom{2n}{n} ≡ −1 (mod 3)) = 1 − t.

Proof This follows easily by induction using the definition of t and Theorem 1.

2. Catalan numbers The Catalan numbers are

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

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ ρ_{2}(C_{n}) & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ (n)_{2} & ∅ & 1 & 10 & 11 & 100 & 101 & 110 & 111 & 1000 \end{matrix}

The exponent of n modulo 2 is

ξ_{2}(n) = the largest power of 2 dividing n. Theorem 5 We have

ξ_{2}(C_{n}) = ω_{2}(n + 1) − 1.

Thus C_{n} is odd iff n = 2^{k} − 1 for some k. Proof One can prove the displayed equation using Kummer’s Theorem. D & S give a combinatorial proof using group actions on binary trees. For the “Thus”: C_{n} is odd iff ξ_{2}(C_{n}) = 0. But then ω_{2}(n + 1) = 1 which is iff n + 1 = 2^{k}.

3. Motzkin numbers

The Motzkin numbers are

M_{n} = _{k≥0}^{∑} \binom{n}{2k}C_{k}.

A run in a sequence is a maximal subsequence of consecutive, equal elements.

Define a sequence r = (r_{0}, r_{1}, r_{2}, …) by

r_{n} = number of elements in the first n runs of t.

Since

t = (ˆ0, ˆ1, 1 , ˆ0, ˆ1, ˆ0, 0 , 1, …)

we have

r = (1, 3, 4, 5, 7, …).

The following theorem is implicit in a paper of Klazar & Luca.

Theorem 6 (D & S) The Motzkin number M_{n} is even if and only if either n ∈ 4r − 1 or n ∈ 4r − 2.

Proof Use induction and the description of M_{n} in terms of ordered trees where each vertex has at most 2 children.

4. Open problems

(i) Alter and Kubota have characterized the divisibility of C_{n} by primes and prime powers using Kummer’s Theorem. Is it possible to find combinatorial proofs of their results for p ≥ 3?

(ii) Explain the occurence of the sequence r in the characterization of the parity of M_{n}, e.g., by proving the result combinatorially.

(iii) D & S have characterized the residue of M_{n} modulo 3 and 5. What can be said for other primes or prime powers? The following conjecture is due in part to Amdeberhan.

Conjecture 7 (D & S) The Motzkin number M_{n} is divisible by 4 if and only if

n = (4i + 1)4^{j+1} − 1 or n = (4i + 3)4^{j+1} − 2

for nonnegative integers i, j.

Furthermore we never have M_{n} divisible by 8.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 \\ ρ_{3} \binom{2n}{n} & 1 & 2 & 0 & 2 & 1 & 0 & 0 & 0 & 0 & 2 \\ (n)_{3} & ∅ & 1 & 2 & 10 & 11 & 12 & 20 & 21 & 22 & 100 \end{matrix}

8