- #1
pc2-brazil
- 205
- 3
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:
[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]
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: