# Induction

• May 19th 2011, 01:53 PM
beno1310
Induction
Hi there,
I need help with proving "weak induction--->string induction" using weak induction
Where to start? :D
• May 19th 2011, 02:08 PM
emakarov
Weak induction for natural numbers: P(0) -> ∀x (P(x) -> P(x+1)) -> ∀x P(x).
Strong induction for natural numbers: ∀x ((∀y < x Q(y)) -> Q(x)) -> ∀x Q(x).

To prove strong induction for a given property Q, apply weak induction where P(x) is ∀y < x Q(y).
• May 22nd 2011, 02:27 PM
beno1310
We want to prove that
P(0) and
(forall k. (forall m. m < k+1 implies P(m)) implies P(k+1))
implies
forall n. P(n)

The proof of this by mathematical induction won't go through unless
we strengthen what we're trying to prove to the following

P(0) and
(forall k. (forall m. m < k+1 implies P(m)) implies P(k+1))
implies
forall n. forall i. i < n implies P(i)

Now for the proof by mathematical induction on n.
Base case, n=0:
We need to show that forall i. i < 0 implies P(0).
This is vacuosly true because there is no natural number i such that i < 0.

Induction step:
The induction hypothesis is forall i. i < n implies P(i).
We need to show that forall i. i < n+1 implies P(i).
So we pick an arbitrary i where i < n+1 and need to prove P(i).
We consider the following two cases.
Case i < n:
Then by the induction hypothesis we have P(i).
Case i = n:
We consider two further subcases:
Case n = 0:
We have P(i) from the assumption P(0).
Case n > 0:
There is some k such that n = k + 1.
With this and the induction hypothesis we have forall i<k+1. P(i).
We can then apply the step assumption to get P(k+1), which is P(i).