Showing that weak induction and strong induction are equivalent

[pc2-brazil]

Homework Statement

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

Homework 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))$$

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?

 

[lippyka]

Next, I will try to show that, if strong induction is an axiom, then weak induction is always true. So, the following is always true: (P(1) \wedge P(2) \wedge ... \wedge P(k) \wedge (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n)) That is, if P(1) is true and P(2), ..., P(k) are all 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, P(2), ..., P(k) are all true, and P(k) → P(k+1) is true. Then, the assertion P(k) \rightarrow P(k+1) is true for all k. So, (P(1) \wedge \forall k (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n)) is always true.Is this part right?