# Examples where Strong Induction is more useful than “Regular” Induction?

The Principles of "Regular" and Strong Induction are equivalent (see for example here).

But are there any examples where something is more easily/elegantly proven with Strong rather than "Regular" Induction?

(And if not, what use is Strong Induction -- why do we even bother mentioning it?)

• Note that both of these are specific cases of a more general technique called structural induction. – user541686 Sep 29 '18 at 9:36

## 1 Answer

One common proof of the existence component of the fundamental theorem of arithmetic uses strong induction.

Suppose that every natural number less than n factors as a product of primes.

If $$n$$ is prime then it factors uniquely as a product of primes. If $$n$$ is not prime then it can be written as the product of two numbers less than $$n$$ which by the hypothesis of strong induction, can both be written as the product of primes. Hence $$n$$ can be written as a product of primes.

Notice that the argument wouldn't work with 'weak' induction.

• I think the Floyd-Warshal algorithm requires strong induction. – Wuestenfux Sep 29 '18 at 10:25