Weak Induction implies Strong Induction

[Terrell]

Homework Statement

[/B]
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.

Homework Equations

n/a

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.

 

[mighty2000]

Thank you for your post on the topic of weak and strong induction. I wanted to provide some additional insights and clarifications on the topic.

Firstly, I want to clarify that weak and strong induction are two different proof techniques that are used to prove statements about natural numbers. They are both based on the principle of mathematical induction, which states that if a statement is true for the first natural number (base case) and if it can be shown that the truth of the statement for any natural number implies the truth of the statement for the next natural number (inductive case), then the statement is true for all natural numbers.

Now, let's take a closer look at the two types of induction. Weak induction is also known as the principle of mathematical induction and it is the most commonly used form of induction. It follows the basic principle mentioned above, i.e., if the statement is true for the first natural number and if the truth of the statement for any natural number implies the truth of the statement for the next natural number, then the statement is true for all natural numbers.

On the other hand, strong induction is a more powerful form of induction. It follows the same basic principle, but the inductive case is slightly different. In strong induction, we assume that the statement is true not just for the next natural number, but for all natural numbers up to and including the next natural number. This allows us to prove statements that cannot be proved using weak induction alone.

In your attempt at a solution, you have correctly identified the base case and the inductive case for strong induction. However, I would like to point out that the definition of the set N that you have used is not entirely accurate. N should contain all natural numbers k for which the statement is true, not just those that satisfy (i) and (ii) of strong induction.

Additionally, I would like to mention that strong induction can be used to prove statements about any set of numbers, not just natural numbers. This is because the inductive case is based on the assumption that the statement is true for all numbers up to and including the next number, rather than just the next number itself.

In conclusion, both weak and strong induction are valuable proof techniques that can be used to prove statements about natural numbers. While weak induction is the more commonly used form, strong induction can be used to prove statements that cannot be proved using weak induction alone.

I hope this helps to clarify