PLEASE explain what is the difference between these two theorems of induction. L
ID: 2943826 • Letter: P
Question
PLEASE explain what is the difference between these two theorems of induction.
Let P1, P2. . . be a sequence of propositions. Suppose that P1 is true. For each n N, if Pn is true, then Pn+1 is true. Then all of the propositions P1 P2, . . . are true. Suggestion: Let S be the set of indices n N which have the property that the proposition Pn is true. Using (1), (2), and Proposition 47, prove that S = N. Let P1, P2. . . be a sequence of propositions. Suppose that P1 is true For each n N, if P1, P2, . . ., Pn are true, then P n + 1 is true. Then all of the propositions P1, P2, . .. are true. Suggestion: Solo flight. We will refer to Proposition 50 as the principle of strong mathematical induction .Explanation / Answer
The difference between these two theorems is in the induction step:
Theorem 49's induction step states that if Pn is true then Pn+1 is true, where as Theorem 50's induction step states that if all P1, P2...Pn are true then Pn+1 is true.
Theorem 49 would display weak induction, where 50 would display strong induction. The reason why theorem 49 is a weaker argument than 50 because it starts in the middle of the ladder so to speak, whereas 50 starts at the bottom. Induction so works because it states that if the previous proposition is true then the next is true and so on. Theorem 49 differs from 50 because for Pn+1 to be true, only Pn has to be true. In 50, for Pn+1 to be everything preceding it has to be true. Intuitively this might seem weird because if you proved that P1 is true and if Pn is true, then Pn+1 is true, wouldn't that be good enough to say that P1, P2, P3,... are all true? While in finite sets, this is good enough, and weak and strong induction are essentially the same, but where weak induction breaks down is in transfinite sets.
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.