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.

**Proof of mathematical induction**

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

Now, using I, we can substitute

*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.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)) ) → ∀*n*P(*n*)

It is crucial to notice that the formula

Universal set

*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*)*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

*i*th 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(

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:

where
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

Let P(x) be a property: A tree (an undirected connected graph with no cycles) of x nodes always has x -1 edges.

**∀P. (**

**P(**

*m*) ∧**∀**

*k***.**

**P(**

*k*) →**P(**

*k*+1) ) → ∀*n*P(*n*)*m,*

*k*and

*n*belong to an applicable domain and

*k*

*≥ m.*

**Structural Induction**

*n-1*edges if it has

*n*nodes.

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

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.

*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.