Originally Posted by

**emakarov** The equivalence of simple (or ordinary) and strong (or complete) induction is an interesting and deep fact. The proof is based on the choice of a different (what I call) induction statement.

Suppose we are allowed to use simple induction for any induction statement A. (In your formulation, A is a set, but I prefer to view it as a predicate that is true precisely on elements of the set. These views are equivalent.) We need to prove complete induction for some particular statement (set) B.

Since complete induction is an implication, to prove it we assume the premises:

(*) B(1) and

(**) for all n, B(n+1) follows from B(1), ..., B(n)

The goal is to show "for all n, B(n)".

(Optional remark: note that the combined premise B(1), ..., B(n) is stronger (i.e., implies) B(n). Therefore, the whole implication (**) is weaker (i.e., is implied) by the implication "B(n) => B(n + 1)". Thus, when we are faced with deriving "for all n, B(n)", we are given weaker assumptions than in simple induction and so cannot use simple induction without some change. Deriving B(n) from weaker assumptions is a more difficult task; therefore it is called "strong" induction.)

We need to show "for all n, B(n)". The proof of this last fact is done using simple induction; however, as the induction statement A(n) we choose not B(n) itself but "for all k <= n, B(k)". I.e., A(n) states that not only B(n) is true but B(1), ..., B(n) are all true.

Now our intermediate goal is to prove "for all n, A(n)", i.e., "for all n, for all k <= n, B(k)" using simple induction. The required conclusion of the complete induction "for all n, B(n)" easily follows from here using reflexivity of <=.

The base case of simple induction is A(1), i.e., B(1). It has been assumed as (*).

The induction step is "for all n, A(n) implies A(n + 1)". It is easy to see that this means proving B(1), ..., B(n), B(n + 1) from B(1), ..., B(n). Now, B(1), ..., B(n) are already contained in the assumption. One only has to derive B(n + 1) from (B(1), ..., B(n). But this is assumed as (**).

tl;dr: In proving complete induction from regular one, the key is to change the induction statement so that it pertains not just to one n but to all 1 <= k <= n.