Date: 09/07/98 at 09:31:29 From: katie Subject: Mathematical induction I am doing a math report that involves mathematical induction. I have never come across this before and have heard a few explanations but they were not very clear. I would just like a simple, understandable explanation of mathematical induction. Thanks, Katie
Date: 09/07/98 at 10:00:10 From: Doctor Allan Subject: Re: Mathematical induction Hi Katie, The formal definition of induction is something like the following: Suppose you want to show that a statement holds for all whole number n. Then you must show: - The statement holds for the number 1. - If the statement holds for the number k, then the statement holds for the number k+1. If you can you show these two things, you have proven by induction that the statement holds for all numbers n. Let me give you an illustrative example taken from a Web page copyrighted by Alan M. Selby: Longer Chains of Reason http://whyslopes.com/PatternBasedReason/ch07.php Romeo and Juliet "Imagine a hero Romeo is riding a horse towards a tall building (a castle). There is a ladder up the side of the building leading to the room where Juliet lives. The bottom step of the ladder is two meters or more (several feet or more) away from the ground. The ladder is not broken. It is in good condition. A person getting to each step of the ladder can climb to the next. Question: Can an able-bodied individual Romeo reach Juliet via the ladder? The answer is yes provided Romeo can get to the bottom step of the ladder. It is no otherwise. The main logic-related ideas in this brief story are as follows. "There is a long ladder to be climbed. When any one step is reached, the next step can be reached. (The ladder must be in good condition for this to hold). The first step can be reached. This situation implies we (or Romeo) can reach each step of the ladder. "Note that the long ladder may have a finite number of steps, for example 183. Then we (or Romeo) can with enough time and patience, reach the last one, or any step in between. "On the other hand, we can imagine a ladder could have an infinite number of steps. For each step we take, a next is possible. For instance, the whole numbers we use for counting do not stop. Each whole number is followed by another - just add 1. "Now suppose or imagine we have a sequence of steps, a ladder, which goes on and on without stopping. Then with enough time and patience, we can reach anyone you mention. An example is met in counting. We can begin counting with the number 1, then 2, then 3 and so on. "When we begin to count, we may have only a finite number of objects to count. With a long enough life, and enough patience, the count will end. But if we count minutes there will always be one more to count. This minute count will never end. More precisely, each of us counters may end, but the counting of minutes in principle can continue. That is, this minute count can reach any large number you specify in advance with or without you. In principle all minutes after the beginning of the count will be met and counted. "To rephrase the above, on a ladder (or road) with finitely or infinitely many steps, the first step needs to be reachable. Further for each step, the next step needs to be reachable. When this occurs, any finite number of steps along the road or ladder in question is reachable. Note that in practice, if each step takes time, the number of steps reachable will depend on how much time is available. "Caution. The conclusion that all steps can be climbed or reached, does not follow from the principle of mathematical induction if the ladder is broken, or if the first step is not reachable. Check for these nasty situations when you want to use the principle to get a conclusion." Hope this helps. If you want a concrete example, please write again. Sincerely, - Doctor Allan, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.