Home » Blog » Find the error in a “proof” by induction

Find the error in a “proof” by induction

Find the error in the “proof” that Apostol gives that all blonde girls have blue eyes. See I.4.4, Exercise #12, in Volume 1 for a statement of the false proof.


This proof assumes that the statement is true for n=3, i.e., it assumes that if there are three blonde girls one of which has blue eyes, then they all have blue eyes. Clearly, this is a false assumption.

3 comments

  1. Astute Chic says:

    Hi! I don’t think this solution is correct, as we may not know whether our assumptions in any other exercises are correct or not.
    An assumption cannot be wrong, as it still is a required procedure for the method of induction i.e. you HAVE to assume it is not false. For example, take an arbitrary claim, which is to be proven by the method of induction. How will we know whether the step, where we assume the claim is true for a value k, is correct or not? I think that in this case, we have to point out a logical flaw NOT in the assumption, but in the process of proving that k+1 yields what is not expected.
    This problem is very similar to the “all horses have the same color” problem, by the same person who posed this question. (Link: https://en.wikipedia.org/wiki/All_horses_are_the_same_color)
    SOLUTION: For the set of girls with n members, n=1, we have all girls with blue eyes. (given in the question).
    Assume this statement to be true: For the set of girls with n members, n=k, assume that they all have blue eyes.
    Now, for the set of girls with n members, n=k+1, we can separate them in two sets, the first k number of girls and the last k number of girls (i.e. first set doesn’t contain the newly added member whereas the second set doesn’t contain the first member). From our assumption, the first set must have all girls with blue eyes, as it has k number of girls and we know that it has at least one girl with blue eyes, as required by the question. Therefore, the second set has at least one blue girl because the first and the second set overlap, meaning that the second set, also with k number of girls, have blue eyes (This is also the method used in the book, to prove that the asserted statement is true). Therefore all girls have blue eyes…
    HOWEVER, this logic assumes that the first set and the last set overlap. And while this is true for pretty much any big set, it is not true for the set of girls with n members, n=2 (i.e. going from n=1 to n=2 illustrative of the process of going from k to k+1). Here the first set of girls (i.e. the first girl) consists of only 1 member, who has blue eyes, cause we must have one girl with blue eyes as a requirement from the question. However the second set also consists of one girl (the added member), who may or may not have blue eyes. In this case, the two sets do not overlap, and hence, we cannot say that this second set has at least one girl with blue eyes, which means that this added member does not necessarily have blue eyes. This is the error in the ‘proof’.
    Please let me know if I don’t make sense or if any of my arguments are incorrect.
    Thanks

Point out an error, ask a question, offer an alternative solution (to use Latex type [latexpage] at the top of your comment):