1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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...