Associated Topics || Dr. Math Home || Search Dr. Math

### 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

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
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/
```
Associated Topics:
High School Definitions
High School Logic
Middle School Definitions
Middle School Logic

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search