Proving mathematical induction using predicate logic

Mathematical induction is a very useful proof technique which is commonly used to reason in many areas of mathematics and computer science. It seems to work out of the box. This article explores the ideas behind induction, why it is correct, and where it works - as it would be quite embarrassing to not be able to reason the correctness of our reasoning tool!

Mathematical induction over natural numbers can be stated as follows:

• Base case: A property P(x) is true (or "holds") for x=1. i.e, P(1) holds.

• Inductive step: Assuming P(k) holds for a natural number k, then P(k+1) holds.

If both of the above are provable, then P(n) is true for any natural number n.

Ok, but why?

The answer lies in fundamentals of logic. 

Proof of mathematical induction

Say, we have proved that P(1) holds (the base case - B)

• P(1)

and that P(k+1) holds when P(k) is assumed to hold, or, in other words, P(k) implies P(k+1) (the inductive step - I)

• P(k) → P(k+1)

Now, using I, we can substitute k = 1 and hence: P(1) implies that P(2) holds. Since we have B which states that P(1) holds, we can infer that P(2) holds (using Modus Ponens). Similarly, substituting k = 2, we know P(3) holds. Hence, we can repetitively argue up till n that P(n) holds.

P(1) → P(2) → P(3) → P(4) → P(5) → ... → P(n) 

Image credits: http://cliparts.co/cliparts/gce/AAp/gceAApLXi.jpg

More formally, using predicate logic, we can describe proof by induction for natural numbers as: 

For a property P, the following formula in predicate logic holds to be true in natural numbers.

f = ( P(1) ∧ ∀k. (P(k) → P(k+1)) ) → ∀nP(n)

It is crucial to notice that the formula f cannot be proved using natural deduction as it is claimed to be satisfiable only by a specific model M described as follows:

Universal set A = N = {0, 1, 2, 3, 4....}

Set of predicates IP = {P} where

• P is a unary predicate

Set of functions IF = {succ, 0} where 

• succ: A → A which maps a number to it's successor
• 0 is a nullary function or a constant

Note: k+1 is syntactic sugar for succ(k)

The proof above proves semantic entailment i.e, proves that our model M satisfies the formula f. This means that induction can be used only within the defined model with a specific domain and will fail when used an arbitrary model/domain. For example: f cannot be used to prove a property P(x) on model M' with A' = {0, 32, -98, 1097, 41}. f only works for an ordered set of numbers where the i+1 th number is greater than ith number in the order by 1. But, on the brighter side, induction or a variant of induction can be used, if it can be proved that it holds in the domain of concern.

Another way to prove induction, is to use proof by contradiction:

Say, we have already proved the base case and inductive step. Assume that P(n) does not hold where n = m+1 for some m. As P(m+1) does not hold, by contraposition of implication (Modus Tollens), P(m) does not hold. We can repeat this argument till we reach P(2). And since P(2) does not hold, P(1) does not hold. But this contradicts our base case which we have already proved. Hence, our assumption must be wrong. Therefore, P(k+1) must hold.

        Induction is not limited strictly to natural numbers. From our proof above, we can see that it can be used as a proof technique for "similar" models. Examples are:

• A = {0, 1, 2, 3, 4....} where P(0) is the base case
• A = {-2, -1, 0, 1, 2, 3, 4....} where P(-2) is the base case
• A = {12, 13, 14....} where P(12) is the base case

etc. 

Since we have chosen an arbitrary property P, we can claim that proof by induction holds for any property! Unfortunately, first order predicate logic can't express this, so we turn to a second order formalization:

∀P. ( P(m) ∧ ∀k. P(k) → P(k+1) ) → ∀nP(n)

where m, k and n belong to an applicable domain and k ≥ m. 
Structural Induction
Induction is not limited to just sequence of numbers - it can be used on some structures too! Let us take the example of proving that a tree has exactly n-1 edges if it has n nodes.
Let P(x) be a property: A tree (an undirected connected graph with no cycles) of x nodes always has x -1 edges.

Base case: P(1) holds as a tree with 1 node has 0 edges.

Inductive hypothesis: Assume P(k) holds i.e., a tree with k nodes has k-1 edges.

To prove: P(k+1) i.e, a tree with k+1 nodes has k edges.

Now consider a tree T of k nodes. 

Image credit: http://www.ics.uci.edu/~eppstein/0xDE/triplerake.png

Let us try to add a new node x to T to make a new tree T'. In doing so, you can add exactly one edge from any one of the existing nodes in the tree T to x, because, if you added more than one edge to x from other nodes in the tree, then you would introduce a cycle - and it wouldn't be a tree anymore by definition. As a result, a our new tree T' of k+1 nodes has k-1+1 (=k) edges. This proves that P(k+1) holds. As a result, P(n) holds.

There are other variants of induction like course of values induction. But the underlying idea behind all of them are very similar: A formal representation of induction must be formulated and proved to be satisfiable in a given model. Post which, we can use the formulated induction to prove any property in the model.

Isn't proof by induction just beautiful? It's a very powerful, yet simple and elegant tool.