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
    Commented Sep 29, 2018 at 9:36

1 Answer 1

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
    Commented Sep 29, 2018 at 10:25

You must log in to answer this question.