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?
Ok, but why?
The answer lies in fundamentals of logic.
Say, we have proved that P(1) holds (the base case - B)
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)
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....}
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)
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:
etc. 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
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.
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.
