All People in Canada are the Same Age

Statement S(n): In any group of n people, everyone in that group has the same age.

If you're a little shaky on the principle of induction (which this proof uses), there's a brief summary of it below.

The Fallacious Proof of Statement S(n):

• Step 1: In any group that consists of just one person, everybody in the group has the same age, because after all there is only one person!

• Step 2: Therefore, statement S(1) is true.

• Step 3: The next stage in the induction argument is to prove that, whenever S(n) is true for one number (say n=k), it is also true for the next number (that is, n = k+1).

• Step 4: We can do this by (1) assuming that, in every group of k people, everyone has the same age; then (2) deducing from it that, in every group of k+1 people, everyone has the same age.

• Step 5: Let G be an arbitrary group of k+1 people; we just need to show that every member of G has the same age.

• Step 6: To do this, we just need to show that, if P and Q are any members of G, then they have the same age.

• Step 7: Consider everybody in G except P. These people form a group of k people, so they must all have the same age (since we are assuming that, in any group of k people, everyone has the same age).

• Step 8: Consider everybody in G except Q. Again, they form a group of k people, so they must all have the same age.

• Step 9: Let R be someone else in G other than P or Q.

• Step 10: Since Q and R each belong to the group considered in step 7, they are the same age.

• Step 11: Since P and R each belong to the group considered in step 8, they are the same age.

• Step 12: Since Q and R are the same age, and P and R are the same age, it follows that P and Q are the same age.

• Step 13: We have now seen that, if we consider any two people P and Q in G, they have the same age. It follows that everyone in G has the same age.

• Step 14: The proof is now complete: we have shown that the statement is true for n=1, and we have shown that whenever it is true for n=k it is also true for n=k+1, so by induction it is true for all n.

See if you can figure out in which step the fallacy lies. When you think you've figured it out, click on that step and the computer will tell you whether you are correct or not, and will give an additional explanation of why that step is or isn't valid.

See how many tries it takes you to correctly identify the fallacious step!

A Brief Review of the Principle of Induction

To state it more informally: suppose you have the number 1 in your collection, and for each number that you have in the collection, you also have it plus 1 in your collection. Then you have all the natural numbers.

Intuitively, the idea is that if you start with the number 1, and keep on adding 1 to it, you will eventually get to every number.

The principle of induction is extremely important because it allows one to prove many results that are much more difficult to prove in other ways. The most common application is when one has a statement one wants to prove about each natural number. It may be quite difficult to prove the statement directly, but easy to derive the truth of the statement about n+1 from the truth of the statement about n. In that case, one appeals to the principle of induction by showing

1. The statement is true when n=1.
2. Whenever the statement is true for one number n, then it's also true for the next number n+1.

As an example, consider proving that 1+2+3+· · ·+n = n(n+1)/2. To try to prove that equality for a general, unspecified n just by algebraic manipulations is very difficult. But it's easy to prove by induction, because it's true when n=1 (1 = 1(1+1)/2), and whenever it's true for one number n, that means 1+2+3+· · ·+n = n(n+1)/2, so 1+2+3+· · ·+n+(n+1) = n(n+1)/2 + (n+1) = (n+1)(n+2)/2, so it's also true for n+1. These two facts, combined with the principle of induction, mean that it's true for all n.