[seqfan] Re: A000108(n) ≡ 1 (mod 6)
israel at math.ubc.ca
israel at math.ubc.ca
Thu Dec 3 03:06:45 CET 2015
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.
More information about the SeqFan
mailing list