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$
1
  • $\begingroup$ Note that both of these are specific cases of a more general technique called structural induction. $\endgroup$ – user541686 Sep 29 '18 at 9:36
8
$\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$
1
  • $\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