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