This is strong induction on natural numbers with usual ordering. In general, strong induction can be used on any well-ordered set, and its proof is no more difficult.the Principle of Strong induction is:

Let P be property of N, assume:

1) P(1) holds

2) if P(1),...,P(n-1) hold, then P(n) holds ∀n≥2, then ∀n P(n)

Suppose you have a set A well-ordered by <. The strong induction principle is:

If for all x in A, (for all y < x, P(y)) implies P(x), then for all x in A, P(x).

You may wonder where the base case is. The set A has the least element, call in x0. Then the premise "for all y < x0, P(y)" is vacuously true: there are no y < x0. Therefore, "(for all y < x0, P(y)) implies P(x0)" is equivalent to P(x0). The idea is that in the induction step, you have to prove P(x) from all P(y) for y < x. Since x0 is the least element, you get no help and you have to prove P(x0) directly.

The easiest way to prove strong induction is by contradiction. Assume that for all x in A, (for all y < x, P(y)) implies P(x). Also, suppose that P(x) is not universally true. Consider the set {x in A | P(x) is false} and use the well-ordering property on this set.