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

### Mathematical Induction

```
Date: 07/01/98 at 08:57:26
From: teo eng soon
Subject: Mathematical induction

"Proof by induction does not prove anything, because in the inductive
step, one makes the assumption that P(k) is true. Since one has to do
this for each k, one has assumed what was to be proved in the first
place, and so the proof is invalid."

What is wrong with the above argument?
```

```
Date: 07/01/98 at 09:30:09
From: Doctor Allan
Subject: Re: mathematical induction

Hi there!

Here is what goes wrong in the argument:

When you generally prove something using induction, you first prove
that the theorem is true for (typically) n = 1. This is called the
basis of the proof. Afterwards you prove that if it is true for P(k)
then it is true for P(k+1).

As the argument states, it is true that you assume P(k) in order to
prove P(k+1), but you can do that because you have proven the
statement for P(1). So the argument forgets the basis of the proof:

Let me give you an example:

Say I want to prove that n = n+1 for all n, and I assume P(k) as in
the argument. Then k = k+1. I need to prove that k+1 = k+2 (the
statement P(k+1)). But k+1 = k + 1 = k+1 + 1 = k+2 (here the second
equality comes from the fact that we have assumed P(k). This is
nonsense, and it only works because I have forgotten to prove the
basis: that 1 = 1+1 = 2, and of course I cannot do that.

So as you see it is quite easy to prove weird things using induction
if you forget the basis of the proof, and that is exactly the case
with the argument you mention. If you prove P(1) and thereafter prove
'if P(k) then P(k+1)' then proof by induction is a completely sound
method of proof.

I hope this helped. If something in my explanation is unclear please
write again.

- Doctor Allan, The Math Forum
http://mathforum.org/dr.math/
```
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
Math Forum Home || Math Library || Quick Reference || Math Forum Search