• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Weak induction is equivalent to strong induction

  • Thread starter wrldt
  • Start date
13
0
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 [itex]\in[/itex] S
(ii) n[itex]\in[/itex] S [itex]\Rightarrow[/itex] n+1 [itex]\in[/itex] 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 [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.
 
21,993
3,264
So assume weak induction, that is:

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

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

Physics Forums Values

We Value Quality
• Topics based on mainstream science
• Proper English grammar and spelling
We Value Civility
• Positive and compassionate attitudes
• Patience while debating
We Value Productivity
• Disciplined to remain on-topic
• Recognition of own weaknesses
• Solo and co-op problem solving
Top