5
$\begingroup$

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?)

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.