Weak induction is equivalent to strong induction

[wrldt]

Homework Statement

Prove that weak induction is equivalent to strong induction.

Homework Equations

To prove this...we assume weak induction. That is

(i) 1 \in S
(ii) n\in S \Rightarrow n+1 \in S for all n in N

The Attempt at a Solution

So to prove strong induction we need to prove the following:
(i) 1 \in S
This is given by our assumption of weak induction.
(ii) {1...n} \in is a subset of S.
SInce we know 1 is in S, we can make 2...n by 1+1, 1+1+1, 1+...+1 (n times)
(iii) if (ii) is true than n+1 is in S.
I think this is true because our assumption guaranteed this.

This is a rough sketch of what I wan to say. Am I on the right track.

 

[micromass]

So assume weak induction, that is:

If
(i) 1\in S
(ii) n\in S~\Rightarrow~n+1\in S
then S=\mathbb{N}.

You need to prove that strong induction holds. That is, you assume that
(a) 1\in S
(b) \{1,...,n\}\in S~\Rightarrow~n+1\in S.
You need to prove from (a) and (b) that S=\mathbb{N}. You don't need to prove (a) and (b), they are given.