Proof by Induction

In a proof by induction we need to show two things...

1. That the statement is true for the 1st case. 2. That if the statement is true for the nth case, it is therefore true for the n+1th case.

Find the flaw in this argument.

S(n)='Any n people in Central Park at the same time all have the same birthday.'

1. Is this true for n=1? Yes, self-evidently.

2. Does S(n) imply S(n+1). Consider a time when central park contains n people. We assume that S(n) is true to see if we can derive S(n+1), so we can assume that these n people all have the same birthday. Let a new person enter the park. We now have n+1 people in the park, but we do not know the birthday of our new entrant. Let one person other than the new arrival leave. We now have n people in the park and by S(n) they must all have the same birthday. This is only possible if our new entrant has the same birthday as the original n people, hence S(n) implies S(n+1).

Hence the statement 'Any n people in Central Park at the same time all have the same birthday' is true for all positive integer values of n.

Isn't it?

No. The proof above doesn't work if n=2; you end up with two people, for which it is true that if each was alone in the park, he would have the same birthday as himself, but there is no relationship between them. And of course, once n=2 is out of the picture, n=3 won't work, and so forth.

Here's a different, sillier, one:

S = 'All men are bald'; where n= the number of hairs on their head. Assume uniform hair length of about a centimeter for all men.

1. If a man has a single n=1 hair on his head, he is obviously bald. 2. If a man with n hairs on his head is bald, adding a single hair will hardly make a difference. Thus, a man with n+1 hairs is also bald.

All men are bald. QED.

This was a real example from my 9th grade math book on how not to use induction, btw.

I first saw this argument in a delightful book entitled 'Stress Analysis of a Strapless Evening Gown,' containing various spoofs of scientific papers. One of the included papers used the above argument to prove that all horses were white, a lemma necessary to the Big Theorem: Alexander the Great did not exist and had an infinite number of limbs.

The proof ran somewhat like this:

1. All horses are of the same color, using the argument given above, with obvious modifications.

2. All things are of the same color, generalizing [1].

3. All things are white, by [2] and the existence of one white thing. For the latter, see Twain, Mark, 'The Stolen White Elephant,' proof by blatant assertion.

4. Historical record tells us that if Alexander the Great existed he rode a black horse named Bucephalus.

5. [3] shows that Bucephalus could not have been black, hence [4] proves that A. the G. did not exist.

6. Before setting out to conquer Persia, Alexander consulted an oracle who warned him that he would shorten his life by doing so.

7. Forewarned is four armed, so with his two legs astride Bucephalus Alexander had six limbs in all.

8. Six is an even number, but an odd number of limbs for a human being.

9. The only number which is both even and odd is infinity.

10. Putting [7], [8], and [9] together we conclude that A. the G. had an infinite number of limbs.

11. [5] and [10] together prove the desired result: Alexander the Great did not exist and had an infinite number of limbs. Unless, of course, there's a flaw in the proof somewhere, which would be a horse of a different color.

12. ... so the proof must be flawless, because by [1] there is no such thing as a horse of a different color.

it doesn't work because you have altered the 'original' S(n). Although it was arbitrary, you have changed those arbitrary conditions by inserting a random element.

Unfortunately for this argument, a counter-example is very easy to come up with.

Imagine that Central Park is totally empty of people, and a pair of twins (P1 and P2) enters. This case S(2) is obviously true (usually).

Now, one of the twins (P2) leaves, and at the same time, someone else (P3) enters the park. The chance of P3 having the same birthday as the twins is approximately 1/365 if we ignore the year, and significantly less if we include the year. This case S(2) is therefore false for most pairs of people.

The absent twin now returns. This S(3) is also false, as P3 hasn't left the park yet.

Having said that, however, the general formula for a proof by induction is correct - the large hole in the argument presented is in step 2 - left as an exercise.....

Usually I see this argument applied to horses. The horse has two legs in back and forelegs in front making six legs...

The conclusion is correct. The main flaw in the argument is that it's much longer than it needs to be. A shorter argument is

A. All people are the same under their skin B. Removal of skin does not affect a person's birthday C. All people have the same birthday.

'Your horse has forelegs in front and hind legs in back.' 'Four legs in front and nine legs in back? What I got, a centipede?'

This is reminiscent of the following chestnut:

Put eighteen packets of sugar into three cups of tea so that each cup contains an odd number of packets. No putting cups inside cups, either.

One in the first cup, one in the second cup and sixteen in the third cup. Sixteen is an odd number of packets to put in a cup of tea.