Imposter induction middle step 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.
 A: 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.
A: 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.
