Weak Induction implies Strong Induction

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

Weak Induction:
If (i) ##S(1)## holds, and (ii) for every ##k \geq 1(S(k) \Rightarrow S(k+1)##. Then ##\forall n \geq 1##, ##S(n)## holds.

Strong Induction:
If (i) ##S(k)## is true and (ii) ##\forall m\geq k [S(k) \land \cdots \land S(m)]\Rightarrow S(m+1)##. Then for every ##n \geq k##, the statement ##S(n)## is true.

2. Relevant equations
n/a

3. The attempt at a solution
Base case: k = 1; If ##S(1)## is true and ##[S(1)\land\cdots \land S(m)]\Rightarrow S(m+1)##, then observe that this is the exact assertion of weak induction. So the base case holds.

Inductive case: Let ##N:=\{z \in \Bbb{N} \vert \text{z satisfying (i) and (ii) of strong induction}\Rightarrow \forall n \geq z(S(n) \text{is true.})\}##. Suppose ##k \in N##, ##S(k+1)## is true, and ##\forall m' \geq k+1[S(k+1)\land \cdots \land S(m')]\Rightarrow S(m'+1)##. Since ##k \in N \Rightarrow \forall n\geq k(S(n)\text{ is true})## and ##k+1 \gt k##, then ##\forall j\geq k+1 \gt k[S(j) \text{ is true.}]##. Therefore, ##k+1 \in N## and by weak induction, strong induction is true.
 
1,415
9
Thanks for the thread! This is an automated courtesy bump. Sorry you aren't generating responses at the moment. Do you have any further information, come to any new conclusions or is it possible to reword the post? The more details the better.
 

Want to reply to this thread?

"Weak Induction implies Strong Induction" You must log in or register to reply here.

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 Threads

Top