wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> putnam exam (pure math) >> paCpb
        
(Message started by: Eigenray on Jul 13^th, 2004, 11:58am)

Title: paCpb
Post by Eigenray on Jul 13^th, 2004, 11:58am

Prove that, if p is prime, then for any a,b
_paC_pb = _aC_b mod p².
When is it true mod p³?

Title: Re: paCpb
Post by Barukh on Jul 16^th, 2004, 1:58am

on 07/13/04 at 11:58:01, Eigenray wrote:

Prove that, if p is prime, then for any a,b
_paC_pb = _aC_b mod p²

Here’s a solution I saw in “Concrete Mathematics”. The well-known identity (called Chu-Vandermonde convolution) states that

[sum]_{(k_1+k_2=n)} _rC_{k_1}* _sC_{k_2} = _r+sC_n (1)
This generalizes to an arbitrary number of variables, and - applied to our case – may be written as:

_apC_bp = [sum]_{(k_1+…+k_a=bp)} _pC_{k_1}*…* _pC_{k_b}, (2)
where 0 [le] k_i [le] p. The key observation is that the inner product of C’s is not divisible by p² if and only if all of k’s are divisible by p (why?). This happens only in the following combination: there are exactly b k’s equal to p, and (a-b) k’s equal to 0. But the number of such combinations is exactly _aC_b, and the result follows.

Quote:

When is it true mod p³?

This was not in “CM”, but the same approach works. Referring to formula (2), we see that every combination of k’s where at least 3 k’s are not divisible by p, gives a product divisible by p³. So, it remains to see what happens in a combination where exactly two k’s are not divisible by p. Without loss of generality, assume these are k_1, k_2. Then obviously k_1+k_2 = p, and the overall contribution to the sum is – compare to (1):

[sum]_{(k_1+k_2=p)} _pC_{k_1}* _pC_{k_2} = _2pC_p – 2.
The -2 term is due to fact that k_1, k_2 cannot be 0. Now, it may be shown that for primes p [ge] 5, _2pC_p [equiv] 2 (mod p³) (this (http://groups.google.com/groups?hl=en&lr=&ie=UTF-8&selm=BwBzCJ.37G%40news.orst.edu) is an elementary proof of a similar result). So, the answer to this part is p > 3.

And now comes the most interesting part. While browsing the Web for the references of the last statement, I came across Wolstenholme’s Theorem (http://mathworld.wolfram.com/WolstenholmesTheorem.html), which shows a close relation between this problem and the one I posted several days ago! Isn’t it amazing?!

Title: Re: paCpb
Post by Eigenray on Jul 16^th, 2004, 6:26am

Attached is the solution I came up with a while ago. The similarities are remarkable.

It essentially uses both results from the problem you posted, which is why I immediately thought of it when I saw yours.