Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Inductive Misunderstanding

Date: 04/26/2012 at 21:22:18
From: Brandon
Subject: Mathematical induction logically flawed

Hello again!

I have a question about mathematical induction.

I'm sure my reasoning is out of line somewhere, but I can't seem to get
past thinking that it is not useful in the sense of being a proof. Would
you be so kind as to show me the hole in my thinking? :)

I have had mathematical induction explained to me two separate ways (one
of which must be erroneous).

Given A1, Ar, and Ar + 1:

a.) One must ASSUME that Ar holds true. If Ar is true, and the base 
case -- A1 -- is also true, and we illustrate that if Ar holds true for 
Ar + 1, we may assume that Ar is proven true and that it holds true for 
all integers.

b.) One must KNOW that Ar holds true. If Ar is true, and the base 
case -- A1 -- is also true, and we illustrate that Ar holds true for 
Ar + 1, we may assume that Ar is proven true and that it holds true for
all integers.

It might help to look at an example. Let's suppose we have the example of
an arithmetic series. Let us follow method b.

           Ar = n(n + 1)/2 

Proving for 1 (base case):

   1(1 + 1)/2 = 1

       Ar + 1 = a + 1(a + 2)/2

(I cheated, but if you do the math, it works).

Using method b, we have, at least to my understanding, proven Ar to be
true. However, it was known that Ar was true beforehand, so what is the
sense in proving it again? That suggests that mathematical induction (at
least in the form of method b) is useless. It proves only what has already
been proven to be true!

Conversely, if one thinks about method a, it is equally as useless.

Given method a, let's suppose the following:

Ar = 1 such that Ar is any integer, including an integer larger than 1,
such as 2. Remember, we're assuming Ar to be true, so we can theoretically
do this.

            1 = 1 (base case)
       Ar + 1 = 1 + 1

Recall that Ar = 2, and therefore, Ar + 1 also is equal to one. That
insinuates that we can assume anything at all to be true, and we can prove
it, regardless of whether or not it is in alignment with reality.

That leaves us only with method b as the valid use of mathematical
induction, and we mentioned before that it is useless.

I just can't seem to see wrap my mind around how mathematical induction
could be useful, nor do I see the error in my thinking. 



Date: 04/27/2012 at 13:29:52
From: Doctor Rick
Subject: Re: Mathematical induction logically flawed

Hi, Brandon,

Thanks for writing to Ask Dr. Math.

Both descriptions of mathematical induction you present are flawed. Many
students miss the same critical elements of the method that are missing in
your descriptions.

Let's say we want to prove that a certain proposition is true for all
integer values of n greater than zero. I'll call the proposition P(n): it
says that something is true for a *particular* value of n.

We must first prove that the proposition to be proved is true for the
least value of n, which is 1 in my example (as is commonly the case). That
is, we prove that P(1) is true. That's the "base case."

Now, we assume that P(n) is true -- for some *particular* value of n. On
this assumption, we prove that a *different* proposition is 
true -- namely, P(n + 1). We aren't assuming what we want to prove; we're
proving that one proposition, P(n + 1), follows from the truth of
another, P(n).

This second part of the proof provides sort of a template for an infinite
set of proofs, an infinite line of reasoning, as follows:

First, we have proved that P(1) is true.

Then, using the template, we can prove that, given that P(1) is true (and
we know it is), therefore P(2) must be true. The logic holds, so now we
know that P(2) is true.

Next, again using the template, we can prove that, given that P(2) is true
(and we know it is), therefore P(3) must be true. Thus P(3) has been
established as true.

The path has been laid for proving in the same way that P(4) is true, and
P(5) is true, and so on, up to any finite integer k for which you wish to
prove P(k). Knowing HOW to prove that P(k) is true, we don't have to do it
all the way out to P(1000000) or whatever; we know it's true.

We aren't assuming what we want to prove, or proving what we already know;
you're right, the first would be a logical fallacy, and the second would
be unnecessary. Rather, we're proving that IF one thing is true, THEN the
NEXT thing must be true. We set one step of an infinite staircase in
place, and provide a blueprint showing how to build any step while
standing on the step below it. Following the blueprint repeatedly, we can
build the infinite staircase one step at a time. That's what mathematical
induction is.

Does that make sense?

- Doctor Rick, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 04/28/2012 at 18:24:02
From: Brandon
Subject: Thank you (Mathematical induction logically flawed)

Thanks so much for the response! That was certainly not something I could
have chewed through by myself!

You have saved me a great deal of grief. I'm very bad at abandoning
problems when I don't have any leads, and this one ended up being a little
time sucker.

May you continue to experience success in your pursuit of mathematics! :)
Associated Topics:
High 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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/