There are no bearded men in the world - What goes wrong in this proof? Several years ago in a textbook I read this example as a faulty use of proof by induction. I never really realized why it fails. Here it goes:

Theorem. There are no bearded men in the world.
  
  
*
  
*Proof by induction
  
  
  Base case: Suppose a person has n=1 facial hair. That's not enough to
  be called a beard.
Induction step: Assume as induction hypothesis that the statement
  holds true for n = k hair, meaning the person has n = k facial hair
  that are not enough to constitute a beard. Adding one hair to the set
  would not matter and the statement would still hold true.
Therefore no bearded man exists in the world.

What's the flaw here?
 A: The (lack of a) definition of what constitutes a beard is the flaw.
A: This is the so-called "Sorites paradox", or "heap problem", which is usually expressed in terms of a pile of sand and the same inductive problem. The Wikipedia article I've linked has a summary of the philosophical objections, but basically Eckhard is correct. Personally I've always thought of this sort of argument as having a hidden step in which the arguer carefully moves the definition of "pile" away from whatever semantic space the might-be-a-pile is about to be moved to.
A: There are three ways to disagree with an argument:
1 - Identify an ambiguous or incorrectly-used term
2 - Disagree with the premise
3 - Show that the conclusion does not actually follow from the premises
In this case, the simple reason to argue it's wrong is that disagree with the premise you stated: "Assume as induction hypothesis that the statement holds true for n = k hair"
The slightly more complex reason is the implied assumption that the number of individual hairs is what determines the presence or absence of a beard.
A: I don't agree that the lack of definition of what is a beard is the flaw. It's a flaw, sure, but I don't think it's the central flaw here.
The problem is more fundamental than that: this is the misapplication of sharply mathematical concepts to real world concepts that have what we might (no pun intended) call fuzzy definitions. The reality is that there is no definition of beard based on "number of whiskers" nor any sharp line that clearly divides "beard" from "not beard". We might even vary our idea of what constitutes a beard based on context. Among our widely clean shaven, and neatly trimmed, society we might consider even a feeble growth a beard whilst the same facial hair displayed among Edwardian gentleman would be mocked as barely worthy of a teenage boy.
A: The base case isn't problematic, as I doubt anyone would say that a man with a single whisker was bearded. The induction step, though, rests on the assumption that if $k$ hairs isn't enough to be called a beard, then neither is $k+1$ hairs. This is an extremely problematic claim, as (together with the base step) it is equivalent to stating that no finite number of hairs is enough to constitute a beard. Since a given person has only finitely many hairs on his face, then the induction step takes for granted that no person has a beard in order to prove that no person has a beard. Circular logic is bad, m'kay?
Ultimately, this fake proof amounts to trying to prove a claim about something that is not defined (or only vaguely defined). We can't logically discuss such objects, so such a pursuit will ultimately be fruitless.
A: How is this getting debated! It is nonsense to try and prove something is beard when you don't even know even know what a beard is!
A: This might repeat what others have said, but the induction principle requires that the predicate applies to the natural numbers.  Clearly, the predicate 'x is a person with n facial hairs' doesn't apply to the naturals.  Even though it's not a proof my mathematical induction, it still is an intuitively good argument, making use of repeated applications of modus ponens, together with the principle that for any n, if a person is n facials hairs is unbearded then a person with n+1 is unbearded.  There are a number of solutions to the sorities argument in the philosophical literature.  See, for example, Timothy Williamson's book Vagueness.  
A: The implicit "definition" of a beard as an arbitrary number of facial hairs is the primary issue. The proof starts with a very easy to grasp fact; 1 facial hair does not a beard make. A variable $k$ is then given the value 1, and the number of facial hairs an individual has, $n=k=1$, is not a beard.
By adding one hair to $k$, we don't change the answer; two hairs is still no beard. Three hairs, same thing. The proof then concludes that, for a given number of hairs n, because $n=k=1$ is no beard and $n=k+1$ doesn't change the answer, there is no $k$, produced by incrementing from the base case, that constitutes a beard. The "proof" is essentially stating that an arbitrary and undefined number of hairs $x$ is needed to make a beard, and $n=k<x \therefore n\neq x$ for all $n$.
It's a "boiling a frog" argument; drop a frog in a pan of boiling water and he'll hop out. But, put him in a pan of cold water, and heat it up by degree, the frog will just sit there, because each degree feels the same as the last. There is, however, a qualitative difference between water that is 211*F, and water that is 212*F, that does not exist between any two adjacent degrees of water temperature < 212 (until you get to 32). By the same token, somewhere between one hair and 8 million hairs, you'd call it a beard; perhaps it's scraggly, perhaps it's just a goatee, but a goatee is a beard and a scraggly beard is a beard.
A: 
Induction step: Assume as induction hypothesis that the statement holds true for n = k hair, meaning the person has n = k facial hair that are not enough to constitute a beard. Adding one hair to the set would not matter and the statement would still hold true.

Precisely define "beard" first.  Once you do that, the above statement will be false, since you'll have some $k$ where adding one hair makes it a beard.
Mathematics only deals with precise definitions. In almost any mathematics course, they will spend a lot more time that you think necessary to define things. Now you know why.
