Results 1 to 3 of 3

Math Help - Analyzing an Induction Proof

  1. #1
    Junior Member
    Joined
    Nov 2010
    Posts
    57

    Analyzing an Induction Proof

    Consider the statement:
    Any set of coins chosen from a box will have the same denomination.

    This is obviously not a true statement, since in general a set of coins will contain more than one denomination. Yet I have an argument that seems to prove the statement is true by mathematical induction. What is the flaw in the "Proof"?

    "Proof": Let P(n) be the statement "Any set of n coins chosen from a box all have the same denomination."

    P(1) is clearly true.

    Suppose that P(k) is true. Consider any set of k+1 coins: Remove one coin. Since P(k) is true, the remaining coins all have the same denomination: Now put that coin back, and remove a different coin. Again, since P(k) is true, the remaining k coins all have the same denomination. Therefore, all k+1 coins have the same denomination, that is, P(k+1) is true. Thus, by the principle of mathematical induction, P(n) is true for all n.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Mar 2011
    From
    Tejas
    Posts
    3,401
    Thanks
    762

    Re: Analyzing an Induction Proof

    the argument that P(k) -->P(k+1) uses the fact that there are at least 2 coins in the box ("...and remove a different coin...."). so the proof is not complete unless we can prove P(2). but P(2) is clearly false, since we might have two different denominations in the box.

    to put it another way, the proof shows that if we form two different subsets of k coins, A and B, from a set of k+1 coins, and each has all coins of the same denomination, then the "base case" is actually where removing one coin leaves one coin. that is, we have two coins. and the base case fails.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor
    Prove It's Avatar
    Joined
    Aug 2008
    Posts
    11,656
    Thanks
    1479

    Re: Analyzing an Induction Proof

    Think of an infinite row of dominoes. If you push the first one, then any domino will push the next one over.

    Mathematical Induction works the same way. The Inductive Step is the proof that the pushing of any domino will push the next one over. But NONE of them will fall unless the Base Step is satisfied as well, in other words, that the first domino is pushed in the first place.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Analyzing q further
    Posted in the Differential Geometry Forum
    Replies: 0
    Last Post: March 2nd 2010, 03:09 PM
  2. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  3. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM
  4. analyzing a function
    Posted in the Pre-Calculus Forum
    Replies: 3
    Last Post: January 5th 2008, 06:44 AM
  5. Analyzing a graph
    Posted in the Pre-Calculus Forum
    Replies: 5
    Last Post: November 26th 2007, 07:23 PM

Search Tags


/mathhelpforum @mathhelpforum