1. Not finding help here? Sign up for a free 30min 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!

Mathematical induction ''all horses are the same color''

  1. Aug 12, 2014 #1

    Maylis

    User Avatar
    Gold Member

    1. The problem statement, all variables and given/known data
    Find the error in the following proof that \all horses are the same color" 4.

    Claim: In any set of h horses, all horses are the same color.

    Proof: By induction on ##h##:

    Base Case: For ##h = 1##. In any set containing just one horse, all horses are clearly the same color.

    Induction step: For ##k \ge 1## assume that the claim is true for ##h = k## and prove that it is true for
    ##h = k + 1##. Take any set ##H## of ##k + 1## horses. We will now show that all the horses in this set are
    the same color:

    ##\bullet## Remove one horse from this set to obtain the set ##H_{A}## with just k horses. By the induction
    hypothesis, all the horses in ##H_{A}## are the same color.
    ##\bullet## Now return the removed horse and remove a different one to obtain a new set ##H_{B}## with just
    ##k## horses. By the same argument, all the horses in ##H_{B}## are the same color.
    ##\bullet## Since ##H_{A}## and ##H_{B}## have some overlapping horses, it must be that all the horses in ##H## must
    be the same color, and the proof is complete.


    1. Carefully follow the induction steps of the proof when going from two horses to three horses and
    indicate if there is a step in the proof which is invalid (i.e. start by assuming that, in any set of
    two horses, all horses are the same color):
    Answer:


    2. Carefully follow the induction steps of the proof when going from one horse to two horses and
    indicate if there is a step in the proof which is invalid (i.e. start from the obvious fact that, in
    any set of one horse, all horses are the same color):
    Answer:



    2. Relevant equations



    3. The attempt at a solution
    This is such a weird question that ended up on an exam in a previous year. Well, I know for induction you start with the base case, assume its case ##k## is true, then show it is true for ##k+1##. But I have no clue what to make out of this one
     
    Last edited: Aug 12, 2014
  2. jcsd
  3. Aug 12, 2014 #2

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Think about the value of h for which the inductive step fails. Hint: it only fails for one value of h.
     
  4. Aug 12, 2014 #3

    AlephZero

    User Avatar
    Science Advisor
    Homework Helper

    That's correct.

    The conclusion that "all horses are the same color" is obviously wrong. The question is asking you to go carefully through the argument when k = 2 and k = 1, and find exactly where it goes wrong.

    It's hard to give too many hints without just telling you the answer, but think about any assumptions that are made in the proof, but not actually proved.
     
  5. Aug 13, 2014 #4
    In order to see the problem, you need to see why it might work.
    If you knew that all sets of 10 horses had the same color, then you would also know that all sets of 11 horses were the same color because:
    In the set of 11 horses, the first 10 are the same color, and the last 10 are the same color. But there's one more statement you need to make before you can say that all 11 are the same color. It's so obvious, that it's easy to just think it without saying it.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Mathematical induction ''all horses are the same color''
  1. Mathematical Induction (Replies: 9)

  2. Mathematical Induction (Replies: 6)

  3. Mathematical Induction (Replies: 5)

  4. Mathematical induction (Replies: 8)

  5. Mathematical Induction (Replies: 11)

Loading...