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!

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