In this post I’m going to discuss two “proofs” by induction. That is, they’ll both be attempts at proving a statement, but they’ll both have flaws in their arguments. My hope is to alert people to potential errors when attempting to prove a statement by induction.
Claim 1: For all n, .
“Proof”: Let denote that claim that . Suppose that is true for some k; that is, suppose . Now, is the claim that . If is true, then , which proves that the truth of implies the truth of . By the principle of mathematical induction, then, is true for all n; that is, for all n.
Claim 2: For all , all people in a group of size n share the same birthday.
“Proof”: Let denote the claim that all people in a group of size n have the same birthday. Clearly, is true, as all people in a group of size 1 have the same birthday. Now, suppose that is true; that is, all people in a group of size k have the same birthday. Suppose now that we have a group of people. Single out one of those people; perhaps his name is Al. Without Al, we have a group of k people, all of whom must, by our inductive hypothesis, share the same birthday. Now, swap Al with one of those other k people. Now Al is in a group of k people. Again, by hypothesis all of them must share the same birthday. So Al must have the same birthday as all the others in his group. Thus these people all share the same birthday, and so is true. By the principle of mathematical induction, then, every member of a group of size n must have the same birthday.
Clearly, both Claim 1 and Claim 2 are incorrect. The question, then, is this: Where are the errors in their “proofs”?
For the “proof” of Claim 1, the argument that implies is actually valid. The logic error lies in the failure to prove a base case. And in fact, is false for any base case you can think of, so any attempt to prove a base case will fail. And if there’s no valid base case, then the chain-like logic of induction doesn’t have an initial link to start with. Thus the “proof” is invalid. The moral of the story here is that, while proving the base case may seem perfunctory, it’s actually crucial to the logic of induction.
For the “proof” of Claim 2, the error is more subtle. The argument for the base case is valid. The argument for implies is also valid—except for one, single, solitary value of k. When , and we remove Al from the group of two people, we then have Al and a group of size 1. Swapping Al with that one other person does put Al in a group of size 1, and he does share the same birthday as everyone else in the group (namely, just himself), but he doesn’t necessarily share the same birthday with that one other person. So does not imply , even though does imply for all larger values of k. Thus while the first link in a chain-like induction argument holds, the attempt to attach a second link to the first one fails. So we can’t attach any more links, and so the “proof” is invalid. The moral of the story here is that, for an induction argument to work, implies has to be true for all values of k (well, values greater than the value for k used in the base case). If it fails for even one value of k, then the induction chain breaks at that point, and the statement may not be true for any values larger than k.