# Showing that weak induction and strong induction are equivalent

#### pc2-brazil

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

Show that the principle of mathematical induction and strong induction are equivalent; that is, each can be shown to be valid from the other.

2. Relevant equations

Weak induction:
$$(P(1) \wedge \forall k (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n))$$
Strong induction:
$$(P(1) \wedge P(2) \wedge ... \wedge P(k) \wedge (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n))$$

3. The attempt at a solution

First, I will try to show that, if weak induction is an axiom, then strong induction is always true. So, the following is always true:
$$(P(1) \wedge \forall k (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n))$$
That is, if P(1) is true and P(k) implies P(k+1), then P(n) is true for all positive integers.
For this, assume that P(1) is true and, for some k, P(k) → P(k+1) is true, then P(n) is true for all positive integers. So, for this value of k, P(1), P(2), ..., P(k) are all true. Then, the assertion $P(1) \wedge P(2) \wedge...\wedge P(k) \rightarrow P(k+1)$ is true. So,
$$(P(1) \wedge P(2) \wedge ... \wedge P(k) \wedge (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n))$$
is always true.
Is this part right?

Last edited:
Related Calculus and Beyond Homework News on Phys.org

"Showing that weak induction and strong induction are equivalent"

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