- 205

- 2

**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:

[tex] (P(1) \wedge \forall k (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n)) [/tex]

Strong induction:

[tex] (P(1) \wedge P(2) \wedge ... \wedge P(k) \wedge (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n)) [/tex]

**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:

[tex] (P(1) \wedge \forall k (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n)) [/tex]

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 [itex]P(1) \wedge P(2) \wedge...\wedge P(k) \rightarrow P(k+1)[/itex] is true. So,

[tex] (P(1) \wedge P(2) \wedge ... \wedge P(k) \wedge (P(k) \rightarrow P(k+1))) \rightarrow \forall n(P(n)) [/tex]

is always true.

Is this part right?

Last edited: