• Support PF! Buy your school textbooks, materials and every day products via PF Here!

Showing that weak induction and strong induction are equivalent

  • Thread starter pc2-brazil
  • Start date
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:

Want to reply to this thread?

"Showing that weak induction and strong induction are equivalent" You must log in or register to reply here.

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
Top