Originally Posted by

**novice** The principle of mathematical induction can be extended as follows. A list $\displaystyle P_m, P_{m+1}, \cdot \cdot \cdot $ of propositions is true provided (i) $\displaystyle P_m$ is ture, (ii) $\displaystyle P_{n+1} $is true whenever $\displaystyle P_n$ is true and $\displaystyle n\geq m$.

Question: Is the above what we called the Strong Induction?

It looks like it, but I must say the formulation seems a bit lacking in precision.

The principle of mathematical induction could be stated, I guess from your question, like this:

If (i) $\displaystyle P_m$ is true and (ii) for all $\displaystyle n\geq m$: $\displaystyle P_{n+1}$ is true, provided $\displaystyle P_n$ is true

then $\displaystyle P_n$ is true for all $\displaystyle n\geq m$

Now a somewhat unhappy formulation of the principle of strong induction would be

If (i) $\displaystyle P_m$ is true and (ii) for all $\displaystyle n\geq m$: $\displaystyle P_{n+1}$ is true provided $\displaystyle P_k$ is true for all $\displaystyle k$ with $\displaystyle m\leq k \leq n$

then $\displaystyle P_n$ is true for all $\displaystyle n\geq m$

I wrote "unhappy formulation" because the principle of strong induction should, in my opinion, really be formulated like this:

If for all $\displaystyle n\geq m$: $\displaystyle P_n$ is true provided that $\displaystyle P_k$ is true for all $\displaystyle k$ with $\displaystyle m\leq k<n$

then $\displaystyle P_n$ is true for all $\displaystyle n\geq m$

Note that in this formulation we do not need a separate clause to require that $\displaystyle P_m$ holds, because if you set $\displaystyle n := m$ in the above you can see, that this requires you to be able to prove $\displaystyle P_m$ without presupposing the truth of any other $\displaystyle P_k$, with $\displaystyle k\geq m$, since for this choice of n there is *no* k that satisfies $\displaystyle m\leq k<n$.

This would become much clearer if we were allowed to write the above with connectives of implication, conjunction, and quantification from first-order logic, I think.