I'm proving something via induction (which has turned into strong induction) and there's something I've never really fully understood about strong induction. The name "strong induction" does make it sound like a more 'powerful' version of induction - but surely this is somewhat counter-intuitive (at least in my mind) given the implications of strong induction?
Just going to the definition of strong induction, it lets you assume that not only does the inductive hypothesis hold for some integer, but also that it holds for all integers less than it as well.
In my mind, assuming something is true for more than one cases isn't as powerful as assuming it's true for only one value and using that as a basis. In my proof, I've had to use not only the $n=k$ assumption, but also the assumption it holds for $n = k-1$, and I really can't see how this is 'strong' or 'complete' induction.
I'm sure someone can enlighten me! Thanks everyone.
Answer
When you say "assuming something is true for more than one cases isn't as powerful as assuming it's true for only one value" you have the direction wrong. Assuming it is true for one value is one thing, assuming it is true for many values is clearly stronger-you have more to work with. As others have said, you can't prove anything from strong induction that you can't prove from weak induction, but that is a significant result in logic. Bigger assumptions are weaker than smaller ones, because you might need something that is in the big one and not in the small one.
No comments:
Post a Comment