# Weak induction is equivalent to strong induction

1. Sep 8, 2011

### wrldt

1. The problem statement, all variables and given/known data

Prove that weak induction is equivalent to strong induction.

2. Relevant 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

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

2. Sep 9, 2011

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