Problem: Prove that: In a classroom with n student, if there is a girl student, all students of this class are girl.

Solving: Let f(n) is the clause: In the class, if there is 1 girl student, all of n students are girl.

First: with n=1 ---> the clause f(1) is right (of course)

Second: with n=k, assume that the clause f(k) is right

we will prove that the clause f(k+1) is right.

Consider a set of (k+1) students {a1, a2, a3,....a(k),a(k+1)} (with a1 is the girl student)

  • with first k student A= {a1, a2, a3,....ak}: using the inductive supposition above, we have all student in A are girl.

  • Now we have B= {a1, a2, a3,....a(k-1),a(k+1)}: also using the inductive suppositon, we have have all student in B are girl.

So the f(k+1) clause is right.

Conclusion: In the class, if there is a girl student, all student are girl !!!!!!!!!!!

I can't find the wrong in this proof. Please help me. thanks



What happens to $A$ and $B$ for $k = 2$?

  • $\begingroup$ exactly the proof breaks down at $k=2$, well-used induction example failure $\endgroup$ – Nikos M. Aug 16 '14 at 9:19
  • $\begingroup$ Oh. that's it... $\endgroup$ – T.Nhan Aug 16 '14 at 9:20

In a proof by induction, going from the $k$ step to the $k+1$ step must work for every specific value of $k$. Does it in this case?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.