The principle of mathematical induction can be extended as follows. A list of propositions is true provided (i) is ture, (ii) is true whenever is true and .
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) is true and (ii) for all : is true, provided is trueNow a somewhat unhappy formulation of the principle of strong induction would be
then is true for all
If (i) is true and (ii) for all : is true provided is true for all withI wrote "unhappy formulation" because the principle of strong induction should, in my opinion, really be formulated like this:
then is true for all
If for all : is true provided that is true for all withNote that in this formulation we do not need a separate clause to require that holds, because if you set in the above you can see, that this requires you to be able to prove without presupposing the truth of any other , with , since for this choice of n there is no k that satisfies .
then is true for all
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.
The "strong" principle of induction usually is stated as
If (1) P(1) is true and (2) if P(k) is true for all [tex]k\le i[/itex] then P(i+ 1) is true
then P(n) is true for all positive integers n.
Changing "P(1)" to "P(m)" and asserting that "then P(n) is true for all is not precisely the "strong" principle but follows easily from it.