How to prove using induction correctly

In our school, we learned that proving using induction has three steps:

1. Prove it for the smallest number of $n$. (Usually, $n=1$)




2. Think it is true for $n$.




3. Prove it is true for $n+1$.

But recently, when I was watching Olympiad video series, it told me that it is not a right way and you should follow this way:

1. Prove it for the smallest $n$.




2. Think it is true for $n+1$.




3. Prove it is true for $n$.




4. You proved it is true for $n$. Now from that, prove it for $n+1$.

Now I am really confused that how to use induction? Can you tell me what is the best way to use introduction, and give me a guarantee that it always works?

Answer

The second method used in the video was probably this. When one is struggling with proving the inductive step $\,P_n\,\Rightarrow\, P_{n+1},\,$ it is often convenient to look not only at things that are implied by $\,P_n,\,$ but also at what things are equivalent to $\,P_{n+1}.\,$ For example, we might prove $\,P_n\,\Rightarrow\,A\,\Rightarrow\, A'\,$ and also $\,P_{n+1}\!\iff B\iff B' \iff A',\,$ so connecting the arrows

$$P_n\Rightarrow A\Rightarrow A'\Rightarrow B' \Rightarrow\ B\Rightarrow P_{n+1}$$

we obtain a complete proof of the inductive step. To do this we can assume that $\,P_{n+1}\,$ is true and then deduce the chain of equivalent statements $\,B^{(k)}\,$ by using only reversible steps, e.g. applying an invertible operation such as adding or subtracting some value to both sides of an equation (e.g. see this recent question). Note in particular that it does not suffice to deduce the wrong-direction unidirectional inferences $\,P_{n+1}\!\Rightarrow B\Rightarrow B'\Rightarrow\cdots$ since they do not allow us to connect the inferences to obtain the sought complete inference displayed above.

For an example of such deductions see this answer, where I deduce that the inductive step is equivalent to the truth of a recurrence $\,g_{n+1}- g_n = f_{n+1}\,$ when analyzing inductive proofs equivalent to telescopic sums (it will prove instructive to write out that equivalence in more detail to examine how the inferences reverse using addition and subtraction).

Such proof methods exploiting simultaneous forward and backward deduction is sometimes called (forward and) backward chaining, or more generally, (inductive) analysis and synthesis.