Understanding how Strong Induction works

honestrosewater

My book gives a proof that "The Strong Principle of Induction follows from the Weak Principle of Induction." I don't understand one step in the proof or how to use it for specific cases (when he asks for a proof by strong induction on something). (He includes 0 as a natural number (the least, BTW).)
Weak Prinicple of Induction:
(1) [tex]\frac{P0, \forall n [Pn \Rightarrow P(n + 1)]}{\forall n (Pn)}[/tex]
Strong Principle of Induction:
(2) [tex]\frac{\forall n [\forall m < n (Pm) \Rightarrow Pn]}{\forall n (Pn)}[/tex]
where [itex]\forall m < n (Pm)[/itex] means "all numbers m smaller than n have the property P".
The proof is briefly:
Define a new property, Q:
(3) [tex]Qn \Leftrightarrow_{df} \forall m < n (Pm)[/tex]
Now the induction hypothesis becomes:
(4) [tex]\forall n [Qn \Rightarrow Pn][/tex].
Since [itex]\forall m < 0\ (Pm)[/itex] is vacuously true (there is no m in N smaller than 0):
(5) Q0
Let n be any natural number and assume that Qn holds. Infer from (4) that Pn holds. (Here's the step I don't get:) "But by (3) Qn means [itex]\forall m < n (Pm)[/itex]. Therefore what we have shown is that
(6) Pm holds for all m < n."
The rest of the proof is just showing that (m < n) <=> (m < (n + 1)) and putting everything back together- I understand this.

So weak and strong induction are equivalent. But strong induction seems quite magical to me since we seem to get Q0 for free- and I don't mean "magical" in a good way. It would help a lot if someone could quickly work through an example- or just give me a hint. The example he uses for weak induction is [0 + 1 + 2 + ... + n = (n(n + 1))/2]. Or I have an actual problem from the book here. Thanks, I know I'm asking a lot. I've really tried to do it on my own.

HallsofIvy

The way you've stated "strong induction", it would be magical!

Weak induction says: if P(0) is true and P(n) true implies P(n+1) true, then P(n) is true for all non-negative integers n.

Strong induction says: if P(0) is true and P(m) true for all m< n implies P(n) true then P(n) is true for all non-negative integers n.

Both require that P(0) be true.

honestrosewater

Okay, just looking at the weak induction part:
[tex]\frac{Q0, \forall n [Qn \Rightarrow Q(n + 1)]}{\forall n (Qn)}[/tex]
If [itex]Qn \Leftrightarrow_{df} \forall m < n (Pm)[/itex], Q0 is vacuously true. If Pm holds for all m < n, Qn -> Q(n + 1). That is the step I don't understand. How does he deduce that Pm holds for all m < n?

matt grime

The difference between strong and weak induction is simply that weak uses simply the previous statement to deduce the next, where as strong uses all the previous statements to deduce the next. And they are reasonably obviously equivalent if you stop trying to write it in symbolic logic since you can by induction deduce that if P(0) then P(1) then P(2) then... so all P(m) for m<n are true by weak induction...

HallsofIvy

No! Strong induction does not assume P(m) is true for all m< n!

It requires that IF P(m) is true for all m< n, then P(n) is true. Notice that IF!

You must still show that P(0) is true in order to "start" the chain.

honestrosewater

Okay, I was copying out of the book because the book is about symbolic logic, and my work has to be written in symbolic logic. But I'll let the symbols go. I don't understand how a proof by strong induction proceeds. You prove Pb, where b is the least member of the set to whose members you're assigning the property P. You then assume that, for arbitrary i and k such that b < i < k, if Pi, then P(k + 1). Right? So you're trying to prove the conditional, right? You do so by assuming the conditional and using it to prove P(k +1)? Once you've proven the conditional, you've proven P(k + 1) since Pi can be Pb. Yes?
And since he already has Q0, he gets P0 by changing (m < n) to (m < n). Right? That is the step I don't understand.

Thank you both. I'm really not trying to be difficult.

mathwonk

the principle of weak induction says that in order to prove something true, it is enough to know it for the one previous case (and for the original case).

in strong induction, in order to show something is true, you get to assume it for ALL previous cases (after proving the original case).

certainly knowing it for all previous cases would include knowing the one previous case.

so if the weak induction principle holds, then certainly "strong" induction holds.

i.e. if I can accomplish a job with the help of just my wife, then I can certainly accomplish it with the help of my whole family (if they do not start arguing).


this stuff is confusing, but in my experience students can learn how to use induction correctly, easier than they can learn how to state it correctly.

honestrosewater

What I don't understand is that assuming the conditional [Pi -> P(k +1)] only helps you if you also assume Pi. Just assuming that the conditional and P(k + 1) are both true, it doesn't follow that Pi is true- and, presumably, you would use the assumption that Pi is true in order to prove P(k + 1). So you do assume both Pi and the conditional, yes?
Edit: That is, you're trying to prove the conditional, right? So you assume both the conditional and the antecedent and prove that the consequent follows from those assumptions. Surely that proves the conditional, since the conditional only fails when the antecedent is true and the consequent is false.
I was getting the impression that you don't assume the antecedent- but you must assume the antecedent if you want to prove the conditional. So which is it? Are you trying to prove the conditional xor do you not assume the antecedent?

HallsofIvy

Well, that's what we've been saying isn't it? Knowing Pi-> P(k+1) for all i<= k only helps if you also know P0- Just as for weak induction, knowing Pk->P(k+1) only helps you if you also know P0.

(I would say "assume Pi". You must SHOW P0. You must prove "if you assume Pi, then you can prove P(k+1)".)

honestrosewater

Okay, sorry, I must not have understood what you were saying. I realize you have to prove P0 or P(whatever the least member is). But you do also have to assume Pi - but Pi is different from P0 because i is arbitrary. Yes?
Edit: I get that there's two parts- and that proving the conditional isn't enough, as it doesn't prove P is a property of any members of your set. But in the step where you prove the conditional, you must assume the antecedent, yes?
Sorry, I see where you said that. And thank you.

HallsofIvy

You also seem to be missing the fact that you DON'T "assume Pi".

You prove that "IF Pi for i< n, then Pn".

honestrosewater

How do you prove "IF Pi for i< n, then Pn" without assuming Pi? "IF Pi for i< n, then Pn" is false iff Pi is true and Pn is false.
I think you prove "IF Pi for i< n, then Pn" by ruling out the one case where it's false: Pi is true and Pn is false. So if you assume Pi is true and it follows that Pn is true, then "IF Pi for i< n, then Pn" is true and you're done.

Hurkyl

I don't see exactly what the problem is, so I'll take a shot in the dark:

Our hypothesis is:

[tex]\forall n [Qn \Rightarrow Pn][/tex]

And from this, we can prove P0. We don't get P0 for "free" -- when we want to use induction, we have to prove this hypothesis, and proving P0 is part of that work.

Now, if we assume Qn, then, by the definition of Q, we may deduce:

[tex]\forall m [(m < n) \Rightarrow Pm][/tex]

and by the inductive hypothesis, we may also deduce:

[tex]\forall m [(m = n) \Rightarrow Pm][/tex]

In other words,

[tex]\forall m [((m < n) \vee (m = n)) \Rightarrow Pm][/tex]

But, we know [itex]m \leq n \equiv (m < n) \vee (m = n)[/itex]...

honestrosewater

So you do assume the antecedent of your inductive hypothesis- i.e. Pi.
So I'm just incredibly dense. How do you get [itex]\forall m [(m = n) \Rightarrow Pm][/itex]?

matt grime

I think people are using "assume" in slightly different senses. When we show P(m) implies P(m+1) we do and don't assume P(m) in two senses. Ie, it matters not whether P(m) is true or false, only that we can deduce P(m+1) from it. However since false implies true is true, we only care about proving the case when P(m) is "true".

For instance the proposition

If n is even n squared is even, we "assume" 2 divides n, because that is the only case we have to prove.

This is one of the reasons why I don't understand why some institutions teach logic to some of their first years, as "false implies true is true" only ever causes problems.

honestrosewater

Do you really mean that, or are you just venting?

matt grime

No, I really mean it, though if you think I'm referring to you I apologize; I am not. The confusing nature of the word "assume" and false things implying anything is not a useful thing to teach at the start of a university course in my experience leading to a standard position of the student thinking that "if grass is red then I am god" means they proved they are god.