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! :)
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994- The Math Forum at NCTM. All rights reserved.