All People in Canada are the Same Age (1997)

It doesn't just assume that, it proves it - but the proof has the hidden assumption that there are at least 3 elements in the set (of k+1 elements).

The basic principle of induction is to prove k+1 in terms of k. If we can show it's true for k=1, then it's true for all k>1 as well. But assuming that it's true for k is a basic part of inductive proofs. It's like falling dominoes. You show the first domino falls; you show that, if the previous domino falls, the next domino will also fall; and thus all the dominoes fall.

The trick in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1, which invalidates the generalization that the induction depends on. The steps obscure an extra predicate on the generalization, so that it's not fully general.

If the proof (of some other property) didn't have that hidden predicate, or something like it, it would be fine. The problem really is that far down.

Note that Step 9 can be read as introducing an entity that is known to exist, or introducing a variable to be universally quantified over. It isn't until Step 13 that we see that Step 9 should be read as the former.

Edit: Let me try to be as clear as possible.

Your confusion comes from the language in the question of "ANY SPECIFIC N" versus "ANY, as in ALL N".

Say, n=3. Then, we assume S is true for the value n=3, but we don't yet know if S holds for any other n (1,2,4,100 etc.), which we have not assumed. However, we show that IF S is true for n=3, THEN that alone implies it's also true for 4 (n+1). Of course then, we could probably show the same process for SOME value of n, 3 or otherwise, and the corresponding n+1! So instead of writing n=3, we just write n and save ourselves the task of having to check all those numbers. Nevertheless, our assumption was that S was true for one specific n, and not all n at the same time!

So we do two things, and it makes sense to think of it in reverse order.

First, if S is true for any specific n we pick (and not necessarily ALL other n), is it THEN also true for n+1? At this stage, we have identified two "n" for which S holds of all possible n. More precisely, we have picked one and assumed S holds, and then found a second one. However, note that the choice of which n we assume to be true was "free" among ALL n. Think of "dynamics" instead of "state" if you are an engineer. But we started with the assumption that S is true for at least one n, the n we chose. Maybe we can not find such an n, in which case it doesn't matter that it would also be true for n+1. Therefore, the second question is: can we find an n for which S is true?

Then it's true for ALL n! But we need the two components. We need to know the relationship of n->n+1, and we need at least one "real" value of n where S does in fact hold.

Your second question is similar. The author means: Pick any two members of G, but you gotta pick two specific members. Since the proof works independently of whom you pick, it goes through for all others. However, it does not mean that you "pick all members" of G!

The "gotcha" moment you had, seeing that the choice of the two members was arbitrary, is usually what completes such a proof. You show the thing you want to show for two specific members of G, but then you circle back and state proudly: "But see, I could have picked ANY member of G. Hence, this must holds for all "dyads" of two people in G!"

Edit: And to understand why the proof fails - the author does not actually proof the n->n+1 step for any arbitrary n, only for n>=2. The specific "real" value he finds, however, is n=1. Therefore, the two steps are disconnected, the n->n+1 does not hold if n=1.

And this is precisely where the "ANY n" versus "ANY as in ALL n" comes into play again. n=1 is qualitatively very different to n=2. S is obviously true for n=1 (one person), but it's obviously not always true for n=2 (two people). While the author proofs that n=2 implies S for all n, this is not true if we start with n=1. However, n=1 is the only thing we can actually show to be really true. In that sense, for the purpose of showing that all Canadians are of the same age, the asserted step of n->n+1 (given n>1) is irrelevant, because we can not find such an n>1 where we can show that this is true!

Here you can see that while we do the proof for any arbitrary but specific n, not assuming it is true for any other value of n, we still need to ensure that we do in fact mean ANY of the n we can pick, including n=1!

I know how induction works, believe it or not

> in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1,

Yes and those are steps 7 and 8, not step 9. Because that "proof" is already wrong. It comes from a wrong premise, surely, but that's already wrong at this time

This is why I'm calling BS on step 9 being the fallacy there.

> Step 5: Let G be an arbitrary group of k+1 people

> Step 7: Consider everybody in G except P. These people form a group of k people, so they must all have the same age (Right conclusion from wrong premises)

> The trick in this proof is that the steps for proving k+1 in terms of k don't work for all k > 1,

7 and 8 doesn't work for any k > 1, it's not "for all" it's "for any". That's why this is so ridiculous

Step 9 fails for kSo yeah the induction doesn't work, but it's not only because of step 9, it's because of 7/8 (which are just erroneous conclusions of a false premise)