A sum of binomial coefficients modulo p

(The Proof of (11))


By induction on n: For we must have n=k and the only possible value of m in the sum is j, so that the result is trivial. Now assume that , and write m and n in base p. Then


for each m in the sum in (11), as for each i. Thus, by Lucas' Theorem, the sum in (11) is congruent to

where the sum is over all -tuples of integers satisfying (25) and not all zero. This is exactly the sum of the coefficients of in , which equals

(11) then follows from the induction hypothesis as and .