# Weak Induction implies Strong Induction

#### Terrell

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.

Related Calculus and Beyond Homework News on Phys.org

#### PF_Help_Bot

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.

"Weak Induction implies Strong Induction"

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