Mathematical Induction

If P is a property of natural numbers such that

1. P(0) holds, and
2. for every natural number n: P(n) implies P(n+1),

then P holds for all natural numbers.

Rule (1) is known as the "base case" or "basis case". Rule (2) is known as the "induction step", or "inductive step".

A simple proof is by contradiction. Assume the result does not hold. In this case there is a least natural number, x, where P(x) does not hold. We know x≠0 by rule (1) above, therefore there is an x-1 such that P(x-1) holds. However, by rule (2) P(x-1) implies P(x) which is a contradiction.

Strong Induction

Another form of induction is strong induction which is defined as: if P is a property of natural numbers such that for every natural number n and for all natural numbers m<n, P(m) implies P(n), then P holds for all natural numbers.

We can prove strong induction using mathematical induction. What we want to prove is:

 
	  
[∀n.∀m<n.P(m)⇒P(n)] ⇒ ∀x.P(x)
	  
	

For any proof of A⇒B we assume A and demonstrate B. So we assume

	
∀n.∀m<n.P(m)⇒P(n)
	 
      

and let us call it our initial assumption. We now have to demonstrate ∀x.P(x). Instead of proving this we'll prove the easier ∀n.∀m<n.P(m) which suffices as ∀n.∀m<n.P(m) ⇒ ∀x.P(x). We'll use mathematical induction to do this:

Claim: ∀n.∀m<n.P(m).

Base case: Take n=0 and since there is no m<0 the result holds.

Induction step: Take n=k and assume ∀m<k.P(m) holds (our induction hypothesis). Consider n=k+1. We need to show that ∀m<k+1.P(m) holds which is the same as ∀m<k.P(m)∧P(k). The first conjunct (∀m<k.P(m)) is our induction hypothesis and when this is combined with the initial assumption this gives us the second conjunct (P(k)).

Hence the result is established by mathematical induction.

References

K. Doets. From Logic to Logic Programming. MIT Press, 1994.