[seqfan] Re: A000108(n) ≡ 1 (mod 6)

[israel at math.ubc.ca]

Actually what we need is Lucas's theorem: binomial(n,m) == product_i 
binomial(n_i, m_i) (mod p) where n_i and m_i are the base-p digits of n and 
m, with the convention that binomial(a,b) = 0 if a < b, together with the 
fact that C(n) = binomial(2n,n) - binomial(2n,n+1) In the case p=3, 
binomial(a,b) (mod 3) has the following values:

    b = 0  1  2  
a=0     1  0  0
  1     1  1  0
  2     1  2  1

Let n = 3s + x, and suppose the conjecture is true for numbers < n. We have 
the following cases:

1) x = 0. Then n+1 = 3s+1 and 2n = 3(2s); binomial(2n,n) == binomial(2s,s) 
(mod 3) and binomial(2n,n+1) == 0 (mod 3), so C(n) == 0 (mod 3) iff 
binomial(2s,s) == 0 (mod 3), i.e. iff s has at least one 2. If s has at 
least one 2, then both n and n+1 have a 2, while if s has no 2 then n has 
no 2. So the conjecture would be true for n.

2) x = 1. Then n+1 = 3s+2 and 2n = 3(2s) + 2; binomial(2n,n) == 2 
binomial(2s,s) (mod 3) and binomial(2n,n+1) == binomial(2s,s) (mod 3), so 
C(n) == 0 (mod 3) iff binomial(2s,s) == 0 (mod 3) iff s has at least one 2. 
Again if s has at least one 2, then both n and n+1 have a 2, while if s has 
no 2 then n has no 2. So again the conjecture would be true for n.

3) x = 2. Then n+1 = 3(s+1)+0 and 2n=3(2s+1)+1; binomial(2n,n) == 0 (mod 3) 
and binomial(2n,n+1) == binomial(2s+1,s+1) (mod 3), so C(n) == 0 (mod 3) 
iff binomial(2s+1,s+1) == 0 (mod 3). Now by Kummer's theorem, 
binomial(2s+1,s+1) == 0 (mod 3) iff the addition s + (s+1) in base 3 has at 
least one carry. The only way s + (s+1) can fail to have a carry is that 
s+1 consists of all 0's and 1's: thus in this case n+1 has no 2's. Again, 
the conjecture would be true for n.

Thus by mathematical induction (after establishing the base case n=0), the 
conjecture is proved.

Cheers,
Robert

On Dec 2 2015, israel at math.ubc.ca wrote:

>The fact that binomial(2n,n) == 0 (mod 3) iff the base 3 representation of 
>n contains at least one 2 follows directly from Kummer's theorem on 
>binomial coefficients.