- #1
wrldt
- 13
- 0
Homework Statement
Prove that weak induction is equivalent to strong induction.
Homework Equations
To prove this...we assume weak induction. That is
(i) 1 [itex]\in[/itex] S
(ii) n[itex]\in[/itex] S [itex]\Rightarrow[/itex] n+1 [itex]\in[/itex] S for all n in N
The Attempt at a Solution
So to prove strong induction we need to prove the following:
(i) 1 [itex]\in[/itex] S
This is given by our assumption of weak induction.
(ii) {1...n} [itex]\in[/itex] 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.