Find the error in the following proof that everyone has the same name. We prove,

Question

Find the error in the following proof that everyone has the same name. We prove, by induction on n, that, in any set of n people, all n of them have the same name. The base case n = 1 is clear as any one person has the same name as herself. For the induction step, suppose the statement is true for a certain n. To prove it for n + 1, consider any set of n + 1 people. Temporarily put one person aside, and consider the n others. By the induction hypothesis, those n people all have the same name. So all of them, except possibly the one person that was put aside, have the same name. Now bring back the person you put aside and put a different person aside. You again have n people, including the one that had previously been put aside. These n all have the same name, by the induction hypothesis, so in particular the one that had originally been put aside has the same name as the rest.

Explanation / Answer

error:

for n+1

firstly excluding the last person, so get the group of n people, so by induction hypothesis , they all have the same name.

now excluding the first person from the original group, again get the group of n people so by induction hypothesis , they all have the same name.

Related Questions

Navigate

• Browse (All)
• Browse F
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.