Combinatorics Cameron - Lucas' Theorem Proof

[RiceRiceRice]

Combinatorics Cameron -- Lucas' Theorem Proof

Hi everybody --

Im currently going through Peter Cameron's combinatorics book, and I'm having trouble understanding a step in the proof of Lucas' Theorem, given on page 28 for those of you with the book.

The theorem states for p prime,

m = a₀ + a₁p + . . . + a_kp^k
n = b₀ + b₁p + . . . + b_kp^k

where 0 ≤ a_i, b_i < p for i = 0, . . ., k -1. Then:

(m choose n ) ≡ [itex]\prod[/itex] (a_i choose b_i ) (mod p), where the product is taken from i = 0 to i = k.

The proof then states:

It suffices to show that, if m = cp + a and n = dp + b, where 0 ≤ a, b < p, then

(m choose n ) [itex]\equiv[/itex] (c choose d) * (a choose b) (mod p) FOR

a = a₀
b = b₀
c = a₁ + . . . + a_kp^k-1
d = b₁ + . . . + b_kp^k-1

I understand the proof of this statement, but I don't know why proving this is sufficient to proving the original theorem.

Any help would be greatly appreciated! Thanks!

 

[Millennial]

It is the step of induction. Once it is proven, the theorem becomes a corollary.