Mathematical Induction

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/