Examples where Strong Induction is more useful than "Regular" Induction?

Question

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 09:36

score 8 · Accepted Answer · answered Sep 29 '18 at 07:58

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

Examples where Strong Induction is more useful than "Regular" Induction?

1 Answers1

Linked