Problem 11165
(American Mathematical Monthly, Vol.112, June-July 2005) Proposed by Y. More (USA).
Let Ck be the kth Catalan number, k+11 2kk. Prove that, for each positive integer n, Pn1Ck ≡1 ( mod 3) if and only if the base 3 expansion of n + 1 contains the digit 2. Find similar characterization for the other two cases, in which the sum is congruent to0 or 2 modulo 3.
Solution proposed by Roberto Tauraso, Dipartimento di Matematica, Universit`a di Roma “Tor Vergata”, via della Ricerca Scientifica, 00133 Roma, Italy.
First we note that if k + 1 6≡ 0 (mod 3) then
Ck Ck
−1
= 1 k+ 1
2k k
1 k
2(k − 1) k−1
= k
k+ 1·(2k)!
k!k! ·(k − 1)!(k − 1)!
(2k − 2)! =4k − 2
k+ 1 ≡1 (mod 3)
and
Ck
−1 ≡ Ck ≡ Ck+1 (mod 3) if k ≡ 0 (mod 3).
Therefore, since C1= 1, then
n
X
1
Ck ≡
1 − Cn+1≡1 − Cn if n = 0 (mod 3)
1 if n = 1 (mod 3)
1 + Cn≡1 + Cn+1 if n = 2 (mod 3) .
If n = 0 (mod 3) then by Lucas theorem
Cn = 1 n+ 1
2n n
≡2n n
≡(2n)t
nt
· · ·(2n)1
n1
(2n)0
n0
(mod 3)
where [(2n)t. . .(2n)1(2n)0] and [nt. . . n1n0] are the ternary expansions of the numbers 2n and n. If the expansion of n contains a digit 2 then there is a carry when adding n and therefore one of the binomial coefficients (2n)(n)i
i is equal to 12 = 0 and Cn ≡0 (mod 3).
On the other hand if the digits of n are 0 or 1 then (2n)i= 2(n)i and Cn≡ 21δ(n)
≡(−1)δ(n) (mod 3) where δ(n) is the number of 1’s in the expansion of n. Hence
n
X
1
Ck ≡
1 if n = 0 (mod 3) and the 3-expansion of n contains the digit 2 1 − (−1)δ(n) if n = 0 (mod 3) and the 3-expansion of n does not contain 2
1 if n = 1 (mod 3)
1 if n = 2 (mod 3) and the 3-expansion of n + 1 contains the digit 2 1 + (−1)δ(n+1) if n = 2 (mod 3) and the 3-expansion of n + 1 does not contain 2
.
Finally we can summerize our result as follows
n
X
1
Ck≡
1 iff the 3-expansion of n + 1 contains the digit 2
2 iff the 3-expansion of n + 1 does not contain 2 and the number of 1’s is even 0 iff the 3-expansion of n + 1 does not contain 2 and the number of 1’s is odd
.
