Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Combinatorics Cameron - Lucas' Theorem Proof

  1. Jun 11, 2012 #1
    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 = a0 + a1p + . . . + akpk
    n = b0 + b1p + . . . + bkpk

    where 0 ≤ ai, bi < p for i = 0, . . ., k -1. Then:

    (m choose n ) ≡ [itex]\prod[/itex] (ai choose bi ) (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 = a0
    b = b0
    c = a1 + . . . + akpk-1
    d = b1 + . . . + bkpk-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!
     
  2. jcsd
  3. Jun 11, 2012 #2
    Re: Combinatorics Cameron -- Lucas' Theorem Proof

    It is the step of induction. Once it is proven, the theorem becomes a corollary.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook




Similar Discussions: Combinatorics Cameron - Lucas' Theorem Proof
  1. Proofs of theorems (Replies: 8)

Loading...