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

Homework Help: Fundamental Counting Principle

  1. Jan 6, 2012 #1
    Hey Guys,

    So, I am trying to prove the Fundamental Counting Principle using induction. I have no clue where to start or even how to use induction to prove it. I would appreciate some help.

    The Question in a mathematical form: Let [itex]^\sharp (A) = m[/itex] and [itex] ^\sharp (B) = n[/itex]. Proove by induction that [itex] ^\sharp (A \times B) = mn [/itex]
  2. jcsd
  3. Jan 6, 2012 #2


    Staff: Mentor

    well induction proofs have two parts:
    1) select an m and n and proof its true like #A=m=0 and #B=n=0
    2) assume there's an n and m that is true
    and add an element to the B set which then adds m elements to AxB set right?
  4. Jan 6, 2012 #3
    Well, that doesn't really sound right, if [itex]^\sharp (A) = 0[/itex], it means [itex]A = \emptyset [/itex]. As far as I understand induction, it has to do with adding our initial assumption to the second assumption and getting to the third assumption. Adding an emptyset doesn't make that much sense.

    If I initially start with sets with 1 elements, then assume [itex]^\sharp (A) = m[/itex] and [itex]^\sharp (B) = n[/itex], How can I show if [itex]^\sharp (A) = m +1 [/itex] then [itex]^\sharp (A \times B) = mn + n[/itex] without using the fundamental counting principle, which is what I am trying to prove.
    Last edited: Jan 6, 2012
  5. Jan 6, 2012 #4


    Staff: Mentor

    if you cross the empty set with the empty you get? drum roll please the empty set right?

    hence #A is zero and #B is zero and the empty set is zero right?

    suppose the A set is the set of vowels and the B set is the consonants and neither set has Y.

    #A=5 and #B=20 so #(AxB) = 100 now adding Y to A (its the hidden vowel of english) changes #A to 6

    and since AxB means pairing Y with each element of B how many new elements are added to AxB?

    Read up on induction there are two parts to the proof:

  6. Jan 6, 2012 #5
    Haha, thanks for the explanation. I love the drum roll part. Anyhow lets get back to the question:

    I obviously know and understand whats going on. The problem is showing whatever is happening mathematically. Remember, Duh or an example is not a proof.

    So I know that [itex]\emptyset \times \emptyset = \emptyset[/itex]. Lets look at the structure of an induction outside of this context.

    Let [itex]A = \left\{n \in A | P(n) \right\} [/itex]. I want to show if [itex]1 \in A[/itex] and [itex]k \in A[/itex] and [itex] k+1 \in A[/itex] then [itex]A = \mathbb{Z}^+[/itex], where [itex]p(n)[/itex] is the condition for A.

    The theory of induction stands on the fact that it starts with one. Showing that [itex] ^\sharp (\emptyset \times \emptyset) = 0[/itex] serves no purpose. Other than that, I understand that if I add 1 to m and make it 1+m the total number will be n+nm. But what is the mathematical justification for that, how can I show this without using the fundamental counting principle, since it is what I am trying to prove?
    Last edited: Jan 6, 2012
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook