Mathematical InductionDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/