Imposter induction middle step

Question

So, proof by induction. When I was in high school, with competitive exams for university entry and all these stuff, we were supposed to present the following template:

Prove the statement holds for n=0 (or whatever first step)
Assume the statement holds for some n
Prove that, if the statement holds for n, then it holds for n+1

I could never understand step 2 and its duplicate presence into step 3. I never got a clear answer from any of my tutors, and sure enough in university, the internet, and everywhere else, I never met that step again.

Is there some theory/school of thought or anything else where this step 2 was a part of the process? I can't help but feel that someone saw this somewhere and just decided to include it everywhere.

I don't know, but it surely looks useless. Anyway, perhaps that you could post your question at the Mathematics Educators Stack Exchange site. — José Carlos Santos, Aug 27 '21 at 18:32
You are correct. Step 2 is unnecessary because $n=0$ is some $n$. — John Douma, Aug 27 '21 at 18:34
Gee, Stack Exchange is growing faster than I can detect. @Jose thanks for the tip. — George Menoutis, Aug 27 '21 at 18:34
Step 2 is plain stupid. Why not throw in "assume the moon is a balloon" as well? — Rob Arthan, Aug 27 '21 at 20:34

score 2 · Accepted Answer · answered Aug 27 '21 at 18:56

You're right; step 2 is performed in the proof described in step 3. However, as written it's redundant because you have already shown that your statement is valid for at least one value of $n$. Usually this statement is phrased along the lines of "Let $n=k$ for any $k$." Then, in your third step, you will show that if the statement is true for $n=k$, it is also true for $n=k+1$.

So, for example, you change your list to

Given a statement $P(n)$, prove a base case (e.g. $P(0)$) is true.

Suppose $n=k$ for any $k$ [you can specify the set here if you need to].

Prove that if $P(k)$ is true, then $P(k+1)$ is true.

Nevertheless, your step 2 isn't necessary because you perform step 2 during step 3.

score 2 · Answer 2 · answered Aug 27 '21 at 20:48

Put in terms of formal (second-order) logic, the usual principle of mathematical induction is the following:

$$ \forall \phi(\phi(0) \land (\forall n(\phi(n) \to \phi(n+1)) \to (\forall n\phi(n)) $$

Here $\phi$ denotes the property (of natural numbers) that you are trying to prove. If you write it out as a principle for informal reasoning, it says that to prove $\phi(n)$ holds for all $n$, it is sufficient to prove:

$\phi(0)$ holds.
whenever $\phi(n)$ holds, then so also does $\phi(n+1)$.

I.e., points 1 and 3 in the template are the relevant ones and point 2 is irrelevant. When you are proving point 2, the standard way to proceed is like this:

A. Assume $\phi(n)$ holds for some arbitrary $n$,

B. Using assumption A, show that $\phi(n+1)$ also holds.

The template you refer to is an incorrect mishmash of the relevant ideas.

Imposter induction middle step

2 Answers2