inducation

If you google "why does induction work?", you will find a lot of discussion and analogies. Basically, it works because the set of Natural numbers is well-ordered. That is, if you have any Natural number, you know that adding 1 gives you the next Natural number.

This excerpt (from Quora) -- written by Shai Simonson -- seems like a good, short answer:

What you "prove" in an inductive proof is the fact that if the proof works for all the cases previous to the one you are considering, then it will also work for the one you are considering. It is the "leverage" of going from the smaller cases to the bigger one that matters. For example, if I know I can make any amount of change up to some number, using just 3-cent and 2-cent coins, then I can show how to make change for one penny more. If the change for the previous case has a 2-cent coin, then I exchange it for a 3-cent coin. If there are no 2-cent coins, then I exchange a 3-cent coin for two 2-cent coins. Either way, I now have change for one penny greater than the case I knew works. Once you do this, and you can prove it for any particular starting case, then the chain reaction of inferences from your "proof" implies that it is true for all of them.
 
You must log in or register to reply here.
Top