This comment was posted to reddit on Mar 27, 2015 at 7:01 pm and was deleted within 12 hour(s) and 44 minutes.

The way you asked the question made it seem like you're confused about what strong induction is, but it seems like your question is really, "I understand what strong induction is, but how can we justify it?"

If we're talking about the natural numbers ℕ = {0, 1, 2, ...} with the usual ordering ≤ then strong induction and weak induction are equivalent (see below for a caveat). That means every statement which can be proven by strong induction can also be proven by weak induction (and vice versa).

**Strong Induction ⇒ Weak Induction**

Hopefully this is obvious! :)

**Weak Induction ⇒ Strong Induction**

This is trickier. Let *P(n)* be some statement over the natural numbers that you want to prove by strong induction. Define *Q(n)* as the statement "*P(k)* is true for all *k* with *1 ≤ k ≤ n*." I claim that:

*Q(n)*is true for all*n*if and only if*P(n)*is true for all*n*- Using weak induction to show that
*Q(n)*is true is equivalent to using strong induction to show that*P(n)*is true

**Caveat to the Equivalence**

In mathematical logic, there's a distinction between logical equivalence and material equivalence. Weak induction and strong induction are materially equivalent but not logically equivalent.

Logical equivalence is a syntactic concept. Whether two statements are logically equivalent only depend on the formal structure of the two statements and the rules of logic we're allowed to apply (e.g., modus ponens, modus tollens, etc.). No matter how we interpret the symbols involved, the two statements will be logically equivalent.

Material equivalent is a semantic concept. Whether two statements are materially equivalent depends on how we're interpreting the symbols. If you're in linear algebra, you've actually been exposed to this a bit. In linear algebra, we use symbols like *+* or *·* to mean different sorts of addition and multiplication than the addition and multiplication of integers. The symbols are the same, but their meaning is different. The fact that we can make similar statements about adding integers and adding certain vectors is entirely dependent on how we've decided to interpret the *+* symbol.

It shouldn't be too surprising that weak induction and strong induction aren't logically equivalent, then, since weak induction doesn't involve the symbol *≤* at all, whereas strong induction requires it. Putting it another way, we only need the idea of the natural numbers and a natural number's "successor" to express weak induction, whereas we need the idea of an ordering to express strong induction. Maybe there's a way we can define *≤* that behaves like our usual *≤* in all the ways we care about, but which breaks the equivalence between strong induction and weak induction?

In fact, it is. We can define a model of the natural numbers which satisfies all the Peano axioms and has total order *≤* such that

- The principle of strong induction holds
- The principle of weak induction
**does not**hold

This shows that there are (admittedly strange) universes where we can do Peano arithmetic, but where the principles of weak induction and strong induction are not equivalent. But with our usual definitions of the natural numbers, addition, and ≤, they are equivalent.