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: 
that you prove P(1) to start with.

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/