Results 1 to 2 of 2
Like Tree1Thanks
  • 1 Post By HallsofIvy

Math Help - Basics of Counting: Induction Proof (Product Rule)

  1. #1
    Newbie
    Joined
    Oct 2012
    From
    Thousand Oaks
    Posts
    4

    Basics of Counting: Induction Proof (Product Rule)

    The question:

    *Use mathematical induction to prove the product rule for m tasks from the product rule for two tasks.*

    The Product Rule for counting states: The Product Rule: Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.


    Base Case: I choose P(m) = 4, which is the product rule for two tasks.

    Induction: I am using P(m) and consider P(m+1). My inductive hypothesis (guessing here) can be n1* n2 * ...*nm * nm+1,

    How do I prove this further in words or math computation? Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,405
    Thanks
    1328

    Re: Basics of Counting: Induction Proof (Product Rule)

    Quote Originally Posted by inflames098 View Post
    The question:

    *Use mathematical induction to prove the product rule for m tasks from the product rule for two tasks.*

    The Product Rule for counting states: The Product Rule: Suppose that a procedure can be broken down into a sequence of two tasks. If there are n1 ways to do the first task and for each of these ways of doing the first task, there are n2 ways to do the second task, then there are n1n2 ways to do the procedure.


    Base Case: I choose P(m) = 4, which is the product rule for two tasks.
    Where in the world did "4" come from? Your base case is two tasks: the first task can be done in n_1 ways and the second task can be done in n_2 ways, there are n_1n_2 ways in which both tasks can be done.

    Induction: I am using P(m) and consider P(m+1). My inductive hypothesis (guessing here) can be n1* n2 * ...*nm * nm+1, [/quote]
    Okay, assuming P(m) is "there are [tex]n_1[tex] ways to do task 1, n_2 ways to do task 2, ..., n_m to do task m, then there are n_1n_2\cdot\cdot\cdot n_m ways to do all m tasks.

    How do I prove this further in words or math computation? Thanks for any help.
    Let "task A" be "do all m tasks". The induction hypothesis, above, says there are n_1n_2\cdot\cdot\cdot n_m ways to do task A. If there are then n_1 ways to do task m+1, what does the basis "counting principle" say about the number of ways to do task A and task m+1?
    Thanks from inflames098
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof for Product Rule and Quotient Rule
    Posted in the Pre-Calculus Forum
    Replies: 4
    Last Post: August 24th 2010, 01:35 AM
  2. Proof of the Product Rule
    Posted in the Calculus Forum
    Replies: 6
    Last Post: April 23rd 2010, 03:03 PM
  3. proof of derivation product rule
    Posted in the Calculus Forum
    Replies: 4
    Last Post: November 17th 2008, 06:29 AM
  4. Proof of product rule for sucessive joint events
    Posted in the Advanced Statistics Forum
    Replies: 1
    Last Post: October 20th 2008, 10:31 AM
  5. Replies: 1
    Last Post: October 13th 2007, 01:19 AM

Search Tags


/mathhelpforum @mathhelpforum