Talk:Mathematical induction

From Wikipedia, the free encyclopedia

From the article : "...If m is prime then it is certainly a product of primes...". I suppose you take 1 to be a prime, and if so, since it is not by the common convention, please state that explicitly or (better) change the example.

I know many people have trouble understanding that where does the "ordinary" m "disappears" in the example (and the manipulation is done on m + 1). Should that be clariefied?

How about making a case where induction fails and dissecting that? ---

This is my first visit to this website. It is amazing. I've never seen anything this great on the internet.

My request: Can you guys put up some more example problems and solutions? It would really be great for CS and Math majors.

Can I make the following suggestion? The reasons for the changes are as follows

I want to include 0 with the natural numbers. (The "first n integers", by the way, is not really correct since the integers also contain negative numbers)
the notation A= {Ai: i=1,2,3,...,n} is not trivial. I know that you are building a proposition here by taking the conjunction of an infinite number of propositions, but I am not sure if that is immediately clear to anyone. So below is my suggestion. -- Jan Hidders

Replacing a well understood word like proposition with a jargon word like "predicate" reduces understanding.

Both notations {Ai:...} and P(n) aren't necessary. Basic concepts like induction need to be described in common, non technical, language, or the lay reader will never learn anything.

I'm not so sure that the term proposition is not jargon. It doesn't look like it but it has a quite specific meaning in logic. But I agree that everything should be as jargon free as possible. So I've adapted my version below a little. Let me know what you think. And, as usual, if you think some more explanation should be added, please do. -- JanHidders

1 Mathematical induction
2 First use of induction?
3 problem of induction
4 Proposed reorganization
- 4.1 Special significance of the n = 2 case
5 Logistics of proposed merger
6 "Start at b" is obviously the wrong section for merger
7 "motivation"
- 7.1 Motivation
8 Proving induction
9 Frog example
10 Cut-the-knot reference?
11 Elevator proof
12 Who is JRSpriggs?
13 I have added some links to a video Podcast and they were remove
14 "Floating" link

[edit] Mathematical induction

Mathematical induction is the standard way of proving that a certain statement about a number n holds for all natural numbers. Such a proof consists of two steps:

Showing that the statement holds for the number 0.
Showing that if the statement holds for a number n then the same statement also holds for n + 1.

Heres an alternative version of the example, which I think is easier for the lay reader... Comment? GWO

Yes, better. Although I would like to have spaces around '+' and '='. And I'm wondering why you don't change the definition in a similar way. Then you get "showing that the statement holds for n = 0" and "showing that if the statement holds for n = m then the same statement also holds for n = m + 1. -- JanHidders

Re: Spaces. You're right, and I think you're right about the definition too. Do you want to make the changes on Mathematical induction itself? GWO

I will do it. Thank you for helping. -- JanHidders

Example:

Suppose we wish to prove the statement that the sum of the first n natural numbers, that is 1 + 2 + 3 + ... + n, is equal to n(n + 1)/2.

The proof that the statement is true all natural numbers proceeds as follows:

(1) Check it is true when n=0. Clearly, the sum of the first 0 natural numbers is 0, and 0(0 + 1)/2 = 0. So the statement is true when n=0.
(2) We have to show that if the statement holds when n=m, then it holds when n=m+1. This can be done as follows.
- Assume the statement is true for n=m holds, i.e.,

                                m(m + 1)
              1 + 2 + ... + m = --------
                                   2

- Adding m + 1 to both sides gives

                                          m(m + 1)
              1 + 2 + ... + n + (m + 1) = -------- + (m + 1)
                                             2

- By algebraic manipulation we have

                    m(m + 1)   2(m + 1)   (m + 2)(m + 1)
                 =  -------- + -------- = --------------
                       2          2              2

- Thus we have

                                      ((m+1))((m+1)+1)
              1 + 2 + ... + (m + 1) = ----------------
                                              2

- So the statement is true for n=m+1.
(3) By induction we conclude that the statement holds for all natural numbers n.

i see no logical conclusion here you assumed a statement and proceeded to add equal terms to both sides, and then somehow concluded that the whole shebang works? this seems to me like assuming x=x, adding one to both sides, and calling x+1=x+1 a proof of something. all it proves is that the quantity you added to both sides are equal

Your version

Example:

Let P(n) be the statement that the sum of the first n natural numbers, that is 1 + 2 + 3 + ... + n, is equal to n(n + 1)/2. The proof that shows that P holds for all natural numbers proceeds as follows.

(1) P(0) says that the sum of the first zero natural numbers equals 0(0 + 1)/2. This is true since 0(0 + 1)/2 = 0.
(2) We have to show that if P(n) holds then also P(n + 1) holds. This can be done as follows.
- Assume that P(n) holds, i.e.,

                                n(n + 1)
              1 + 2 + ... + n = --------
                                   2

- Adding n + 1 to both sides gives

                                          n(n + 1)
              1 + 2 + ... + n + (n + 1) = -------- + (n + 1)
                                             2

- By algebraic manipulation we have

                    n(n + 1)   2(n + 1)   (n + 2)(n + 1)
                 =  -------- + -------- = --------------
                       2          2              2

- This shows that P(n + 1) holds:

                                      (n + 2)(n + 1)
              1 + 2 + ... + (n + 1) = --------------
                                            2

(3) By induction we conclude that P(n) holds for all natural numbers n.

I'm wondering if this definition of "mathematical induction" applies to the proofs by mathematical induction that I remember doing in logic. --LMS

Well it certainly should do ... what do you remember about them? GWO

The term is often generalized to not just the natural numbers but anything that is countable. So you can prove something for all integers greater than 6 or for every string that is described by a certain syntax. Sometimes the schema is generalized to (1) prove for n=0 (2) show that if it holds for all m <= n then it holds for n+1. All those generalizations can be reformulated so that they fit the current definition, but that is something that probably needs a little explaining. Is that what you mean? -- JanHidders

That is precisely what I mean, Jan, thanks. Essentially, mathematical induction is a way of making a proof recursive, which is something that is used in logic when the proofs are not about numbers per se. --LMS

I have removed the "proof" of mathematical induction, which I believe to be only slightly better than the "domino effect" argument. The principle of mathematical induction is always stated as an axiom (e.g. Peano's system), a proof seems to be unnecessary. --Wshun

Someone has put down the following three terms:

Proof of method Mathematical induction is taught in schools, and most students learn it by rote without fully understanding how it works. It is possible to base a proof of mathematical induction on other mathematical principles.

But one of those mathematical principles is EQUIVALENT to the principle of mathematical induction!

Related methods An induction variant is used in computer science to prove that expressions which can be evaluated are equivalent, and this is known as structural induction.

Hmm, the related article is not wikified. Anyway, it could be put back later.

Alternative Formulations An alternative formulation of the principle of mathematical induction is the Well-Ordering Principle, which states that any nonempty set of natural numbers must have a smallest element. This principle is equivalent to mathematical induction, as follows:

Suppose that the well-ordering principle is true, and that the conditions of the proof by induction are true, namely, that for some property P, we know that P(0) is true, and that if P(n) is true for any natural number n, then P(n+1) is also true. We wish to prove that P(n) is true for all natural numbers n. Let S be the set of natural numbers for which P is not true. Let us suppose that S has a smallest element, say m. m cannot be 0, because P(0) is true by hypothesis. So m-1 is a natural number, and in particular m-1 is not an element of S, because m is the smallest element of S. So P(m-1) is true, and by hypothesis P(m) is also true, and we have a contradiction. Thus we conclude that S has no smallest element, and so by the well-ordering principle, S must be empty. P(n) therefore holds for all natural numbers n.

Conversely, we can prove the well-ordering principle inductively. Let S be a set of natural numbers. We want to prove that either S has a smallest element or else that S is empty. Let P(n) be the statement that no element of S is smaller than n. P(0) is certainly true, since there is no natural number smaller than 0. Suppose that P(n) is true for some n. If P(n+1) were false, then S would have an element smaller than n+1, but it could not be smaller than n, because P(n) was true, and so S would have a minimal element, namely n, and we would be done. So P(n) implies P(n+1) for all n, or else S has a minimal element. But if P(n) implies P(n+1) for all n, then by induction we know that P(n) is true for all n, and therefore for all n, no element of S is smaller than n. But this can only be vacuously true, if S has no elements at all, since every natural number is smaller than some other natural number. Thus we are done.

An analogous proof holds for any well-ordered set; see transfinite induction.

Is it too technical to be placed on Wikipedia?

--wshun 04:21, 10 Aug 2003 (UTC)

Regarding only the Alternative Formulations section: I didn't think it was too technical when I put it in. I also think it would be illuminating for a certain audience---people who are familiar with the idea of induction, but who haven't studied set theory yet. It seems strange to me that you decided to remove this section when you yourself weren't sure if it should be removed.

--Dominus 06:46, 10 Aug 2003 (UTC)

Oh, it is my strange style :P I like to remove materials that I am not sure if they should be added to the article. BTW, now we have proof of mathematical induction and three forms of mathematical induction, we can move something here and there to reduce redundance. -- wshun 23:23, 10 Aug 2003 (UTC)

Nothing is too technical for Wikipedia provided all the necessary prerequisites are also on Wikipedia! Phys

This section looks odd to me: Proofs by transfinite induction typically need to distinguish three cases:

m is a minimal element, i.e. there is no element smaller than m
m has a direct predecessor, i.e. the set of elements which are smaller than m has a largest element
m has no direct predecessor, i.e. m is a so-called limit-ordinal

The first point says there is no element < m, yet the second implies there is a element smaller than m. Also, the third one contradicts the second: "m has a direct predecessor'", "m has no direct predecessor"

Of course they contradict each other; that's why they are distinct cases that are distinguished from each other!! Michael Hardy 00:42, 30 Mar 2005 (UTC)

[edit] First use of induction?

From ArXiv:

Diophantus' 20th Problem and Fermat's Last Theorem for n=4: Formalization of Fermat's Proofs in the Coq Proof Assistant. [cs.LO/0510011]
<a href="http://arxiv.org/find/cs/1/au:+Delahaye_D/0/1/0/all/0/1">David Delahaye</a> (CEDRIC), <a href="http://arxiv.org/find/cs/1/au:+Mayero_M/0/1/0/all/0/1">Micaela Mayero</a> (LIPN) in cs.LO updates on arXiv.org
Oct 5, 04:30 AM
We present the proof of Diophantus' 20th problem (book VI of Diophantus' Arithmetica), which consists in wondering if there exist right triangles whose sides may be measured as integers and whose surface may be a square. This problem was negatively solved by Fermat in the 17th century, who used the "wonderful" method (ipse dixit Fermat) of infinite descent. This method, which is, historically, the first use of induction, consists in producing smaller and smaller non-negative integer solutions assuming that one exists; this naturally leads to a reductio ad absurdum reasoning because we are bounded by zero. We describe the formalization of this proof which has been carried out in the Coq proof assistant. Moreover, as a direct and no less historical application, we also provide the proof (by Fermat) of Fermat's last theorem for n=4, as well as the corresponding formalization made in Coq.

Maybe we should start a history section? --- Charles Stewart 02:41, 27 October 2005 (UTC)

Um, on that note, isn't Euclid's proof of the infinitude of primes basically inductive? At least from what I remember of a (unfortunately rather literally translated) version of his proof, it was...

[edit] problem of induction

Is the mathematical induction suscpetable to the problem of induction? Why yes/not?

First, to answer this question we must look at this in a very broad point of view. Think that science and mathematics are branches of history; science is the study of our interpretation of past observations to try to predict future events; mathematics is the study of patterns, or, loosely, history of numbers. Now, because we know for certain what we do and don't know (i.e., postulates, theorems, properties, ect.), we can 100% correctly anticipate what will happen mathematically, based on those theorems. If you use only what you know for certain, you shall never run up into the problem of induction.

The above is extraordinarily philosophically POV, to say the least. That's fine on a talk page, but it should also be mentioned that mathematical induction is a form of deductive rather than inductive reasoning. Michael Hardy 02:25, 30 December 2005 (UTC)

I don't see the problem here: the answer is no. Mathematical induction works when we want to demonstrate a statement involving quantification over sets that can be given a recursive characterisation. The problem of induction arises when we want to demoinstrate such statements where there is no such mechanism for covering its totality. if you really want to make a problem, looking at Wittgenstein's puzzle's over rule following would be the right sort of place to look, but I'd say it's not the same problem at all as Hume's problem. --- Charles Stewart 02:47, 30 December 2005 (UTC)

Strange. I remember someone once telling me that there's a big problem with the way we reach conclusions with mathematical induction. I was sure that he was referring to the problem of induction. Guess it was something else. CommandoGuard 17:26, 31 December 2005 (UTC)

[edit] Proposed reorganization

This article's description of strong induction is longer than the strong induction article's! Also, there are a few more variants of induction that this article could mention, especially if it absorbs the insights from Three forms of mathematical induction. So I propose the following organization:

intro: keep (it's a method of math proof; generalizes to well-founded structures; deductive, not inductive; first used by Maurolico)
Description of basic method: keep (basis step, inductive step, domino analogy)
Example: keep (1 + ... + n = n(n + 1)/2)
Variants commonly used: in practice, induction proofs may be organized differently

Starting at b
Double induction: induction on two counters, n and m (and, possibly, even more)
Induction on binary functions: this is where we absorb maybe two of the examples from Three forms of mathematical induction

Validity of mathematical induction on natural numbers: axiom of natural numbers, equivalent to well-ordering axiom
Strong induction: absorb strong induction; mention transfinite induction; explain generalization to well-founded structures

Also, I vigorously vote that we start the natural numbers at 0; this is common practice in logic, which is the domain of this article. Joshuardavis 13:46, 9 March 2006 (UTC)

This sounds good. I wonder if it makes sense to have induction on several counters in the middle but not general well-founded structures until the end; I guess it works as long as the middle bit isn't too long. As for starting at 0, I have no strong opinion, but I note that it would be consistent with Recursion. Melchoir 01:21, 10 March 2006 (UTC)

For the purposes of working it into this article, I am including my reformulation of Michael Hardy's disputed Three forms of mathematical induction article here. Also, to give credit where it is due, I would like to acknowledge that Ryan Reich mentioned this interpretation before I did. Joshuardavis 19:16, 12 March 2006 (UTC)

Okay with me. I'll add the magic tags. Melchoir 21:20, 12 March 2006 (UTC)

I'd like to first thank Joshuardavis for so persitently giving me credit for this idea, although he's the one who takes all the responsibility for promoting it. Anyway, I was thinking about the most natural way to present this "induction on a binary operation", and here's what I think:

At the lowest level, this technique covers proof by induction of formulas which are "true by definition"; here you should have in mind the $1 + \dots + n = {n + 1 \choose 2}$ example. One attempt at a general form of this is that you are given a binary operation $B (x, y)$ and define an n-ary operation $B_n(x_1, \dots, x_n) = B(B_{n - 1}(x_1, \dots, x_{n - 1}), x_n)$ . Then the theorem to prove is that given a function $f (n)$ and a sequence $a_1, a_2, \dots$ , we have $B_n(a_1, \dots, a_n) = f(n)$ . The entirety of the proof is to compute that $B (f (n - 1), a n) = f (n)$ for all n. This is true by definition in the sense that $B_n(a_1, \dots, a_n)$ represents an "unsimplified" operation on the a's, which if it were simplified "as it is computed", would at each stage give $f (n)$ . I think this could be even more absurdly generalized if you really tried, but it's not helpful.
What this argument is really getting at is that we define some (all, actually) functions on the natural numbers "by induction", saying something like, "Let $f (1) = 1$ , and for each n, assuming we have defined $f (n - 1)$ , let $f (n) = f (n - 1) + n$ ". The fact that this can be done is not entirely obvious, and for example, Munkres' Topology devotes a whole section, Chapter 1 Section 8, to discussing how it can be done. In particular, what I said above is his Lemma 8.2 (all numbers are from the Second Edition). Therefore this "induction on binary operations" properly belongs as a subset of a discussion on recursive definition, which itself belongs as a section of mathematical induction. This is something I indicated in my second response to Mr. Hardy at Wikipedia talk:Articles_for_deletion/Three_forms_of_mathematical_induction.
Mr. Hardy's original point was that 2 is a special number. In light of the general framework I have set out here I think this is incorrect, and that if B were replaced by a trinary function T and the definition of B_n suitably modified, you could say the same thing. I think that if we are going to give this subject its proper due we should excise the reliance on the number 2; a very good example would be to mention a proof by induction (rather than by the methods of difference equations, the point being that the Fibonacci sequence is defined by a recurrence relation using two, rather than just one, of the previous terms) of the well-known formula

$F_n = \frac{\phi^n - (-\phi)^{-n}}{\sqrt{5}}$ , where $F n$ is the nth Fibonacci number

In order to remove the stain of the appearance of Original Research, we should not dwell that much on the point, and not go to great lengths to present it as a deep mathematical principle. I think the proper place is as a sub-subject of a discussion of recursive definitions, which is a deep principle, but also a well-researched one. Ryan Reich 04:18, 13 March 2006 (UTC)

On your second bullet: recursion is important, but shouldn't recursive definitions be elaborated upon at Recursion? Melchoir 04:31, 13 March 2006 (UTC)

Sure looks like it. As they say, I'm not as familiar with the literature as I should be. Given that, let's include the examples here and make reference to the theory there. Ryan Reich 04:41, 13 March 2006 (UTC)

I agree that extensions of this idea to trinary, 4-ary, etc. functions are possible and could be mentioned, but they do not deserve a worked example in this article, because virtually all functions encountered by the common person are unary or binary. My vague opinion is that Mathematical induction (being a proof technique required of many students) should remain relatively practical and example-driven (except for mentioning the equivalence with well-ordering), while Recursion (being an underlying concept with many manifestations) should contain the more conceptual and philosophical material. See the logistics section below. Joshuardavis 16:21, 13 March 2006 (UTC)

[edit] Special significance of the n = 2 case

In mathematics, many standard functions, including operations such as + and relations such as =, are binary, meaning that they take two arguments. Often these functions possess properties that implicitly extend them to more than two arguments. For example, once addition a + b is defined and is known to satisfy the associativity property (a + b) + c = a + (b + c), then the trinary addition a + b + c makes sense, either as (a + b) + c or as a + (b + c). Similarly, many axioms and theorems in mathematics are stated only for the binary versions of mathematical operations and relations, and implicitly extend to higher arity versions.

Suppose that we wish to prove a statement about an n-arity operation implicitly defined from a binary operation, using mathematical induction on n. Then it should come as no surprise that the n = 2 case carries special weight. Here are some examples.

[edit] Product rule

In this example, the binary operation in question is multiplication (of functions). The usual product rule taught in calculus says

$(fg)' = f'g + g'f.\,$

For a product of n functions, one has

$(f_1 f_2 f_3 \cdots f_n)' \,$

$= (f_1' f_2 f_3 \cdots f_n) + (f_1 f_2' f_3 \cdots f_n) + (f_1 f_2 f_3'\cdots f_n)+\cdots +(f_1 f_2 \cdots f_{n-1} f_n').$

In each of the n terms, just one of the factors is a derivative; the others are not.

The n = 1 case is trivial ( $f' = f'$ ), and the n >= 3 cases are easy to prove from the preceding n − 1 cases. The real difficulty lies in the n = 2 case, which is why this is the one stated in the standard product rule.

[edit] Pólya's proof that there is no "horse of a different color"

In this example, the binary relation in question is equality, = (applied to color of horses). In the middle of the 20th century, a commonplace colloquial locution to express the idea that something is unexpectedly different from the usual was "That's a horse of a different color!". George Pólya posed the following exercise: Find the error in the following argument, which purports to prove by mathematical induction that all horses are of the same color:

If there's only one horse, there's only one color.

Suppose within any set of n horses, there is only one color. Now look at any set of n + 1 horses. Number them: 1, 2, 3, ..., n, n + 1. Consider the sets {1, 2, 3, ..., n} and {2, 3, 4, ..., n + 1}. Each is a set of only n horses, therefore with each there is only one color. But the two sets overlap, so there must be only one color among all n + 1 horses.

Again the n = 1 case is trivial (any horse is the same color as itself), and the inductive step is correct in all cases n >= 3 cases. However, the logic of the inductive step is incorrect when n = 2, because the statement that "the two sets overlap" is false. Indeed, the n = 2 case is clearly the crux of the matter; if one could prove the n = 2 case, then all higher cases would follow from the transitive property of equality.

[edit] Triangle inequality

This example is somewhat more complicated, because it involves a binary operation, +, and another binary function, the distance function d in a metric space. The usual triangle inequality in metric spaces says

$d(x_0, x_2) \le d(x_0, x_1) + d(x_1, x_2).$

For a sequence of n + 1 points, one has

$d(x_0, x_n) \le d(x_0, x_1) + \cdots + d(x_{n-1}, x_n).$

Again the n = 1 case is trivial:

$d(x_0, x_1) \leq d(x_0, x_1).$

The first nontrivial case occurs when n = 2; this case is the crux of the matter, which is why the triangle inequality deals with it. The cases n ≥ 3 then follow inductively from the corresponding n − 1 cases.

[edit] Logistics of proposed merger

One problem with merging this material into mathematical induction is that that article has so pitifully few worked examples. That should get taken care of first. Alternatively one could create a separate article about Polya's example, and emphasize that although Polya phrased it as an error to be located, it is a valid argument as applied to some problems. Michael Hardy 01:38, 13 March 2006 (UTC)

You raise a good point: How many worked examples should this article offer? How long and textbooky should the article be? In my opinion, it should do

a basic example such as 1 + ... + n = n(n+1)/2
either the product rule or triangle inequality example (but not both)
the Polya example (because it's famous and of the same form but wrong -- very instructive)
an example of strong induction (Fibonacci?)

The starting at b, multiple induction (on indices n and m), induction on n-ary funcs for n > 2, etc. should be mentioned but do not deserve their own examples. Perhaps I am being too minimalist, but I feel that too many examples will overwhelm the reader and distract him from the really important ones. Joshuardavis 16:32, 13 March 2006 (UTC)

By the way, Fibonacci number already has the strong induction proof of the closed formula. So I guess we pick a different example or cite that one? Joshuardavis 17:45, 13 March 2006 (UTC)

Fibonacci does not seem to me to be a good example for strong induction, because it's not using the full strength of the hypothesis that the proposition holds for all values less than n. Michael Hardy 03:29, 14 March 2006 (UTC)

I fully agree. Can anyone think of a standard, interesting example of induction using all previous n? Joshuardavis 16:10, 14 March 2006 (UTC)

If you're talking about worked examples in the early part of the article explaining how to write proofs by mathematical induction, I think you're right that we should not include both the triangle inequality and the and the product rule. But if you're talking about the necessarily later section that would include the ideas from three forms of mathematical induction, then Polya's argument is not a concrete example, but a statement of the general form. There should be more than one concrete example in that section. Michael Hardy 03:47, 14 March 2006 (UTC)

Per my proposed reorganization, I believe that the "early part of the article" should have exactly one example, 1 + ... + n = n (n + 1) / 2. The later section, currently called "Building on n = 2", should have the product rule (say) and Polya's example.

Actually, I feel that there should be only one example of any one concept (except for Polya). This is an encyclopedia, not a textbook. But if you and other editors strongly want more examples, then I will surrender that point.

I still don't understand your philosophical view that Polya's argument is not an example but somehow a description of the entire Second Form. It is an example, in that it deals with a particular binary function (=), while other examples deal with other particular binary functions (+, x, etc.). Of course you are right that it illustrates the general idea, but so does the product rule example. This is what it means to be an example — that it has particulars not true of all examples, but nonetheless illustrates the concept. (Perhaps I'm simply misunderstanding you?) Joshuardavis 16:10, 14 March 2006 (UTC)

Now that the article is clearly under construction, with new sections containing only merge tags, I'm going to go ahead and start putting material into the sections. Since I have not asked ahead of time, I won't be offended if others start reverting it. But, please, let's actually start implementing some of these ideas. Joshuardavis 16:10, 14 March 2006 (UTC)

[edit] "Start at b" is obviously the wrong section for merger

Why in the world would anyone choose the section titled "start at b" to merge three forms of mathematical induction into. That is absurd!! Anyone who thinks the essense of the matter is starting at somewhere unconventional is totally clueless. Michael Hardy 03:38, 14 March 2006 (UTC)

And your better idea is...? Melchoir 03:45, 14 March 2006 (UTC)

Firstly, my better idea is don't put it into a section to which it is not relevant. The "start at b" section is about a trivial point. It's also about a point that has no bearing, as far as I can see, on the material in three forms of mathematical induction.
Three forms of mathematical induction is a more advanced section that needs to presuppose that the reader knows very well how to write proofs using mathematical induction. "Start at b", on the other hand, is about a simple point and is addressed to people learning the subject for the first time. One of those who suggested a "merge into" pointed out that more advanced material typically comes later in the article.

The mergeable content of Three forms of mathematical induction consists of the case when the induction step relies on the n=2 result. It is not advanced, and it is closer to the original presentation of induction than complete/transfinite induction. I'll create a new section for it, if that's what you're suggesting. Melchoir 06:02, 14 March 2006 (UTC)

What is "advanced" is the reason why this form is treated separately: the "binary character" of the identity relation, i.e. if any two horses are of the same color, then all horses are of the same color. Trivial when stated that way, but as applied to classification of forms of mathematical induction into three classes, it should generally be addressed only to those who already know what mathematical induction is and how to use it. Michael Hardy 22:05, 14 March 2006 (UTC)

[edit] "motivation"

The newly added "motivation" section, which I've deleted and am pasting below, has problmes. Firstly, what are "traditional proof approaches", if those don't include mathematical induction? Secondly, what is an "absolute property"? This section is mainly devoted to an example. Perhaps it should be listed among examples. Michael Hardy 01:50, 10 April 2006 (UTC)

PS: I've changed the typesetting style to conform to conventional Wikipedia usages in mathematics articles. Michael Hardy 01:50, 10 April 2006 (UTC)

More traditional proof methods include syllogistic arguments and proofs by contradiction. If you had a problem with that phrasing, you could have just revised the phrasing to your whims. An absolute property is exactly what it sounds like: a non-relational property; a property which an object intrinsically, as opposed to extrinsically, has.

The motivation is indeed an example. It is a very simple one, suitable to work as a motivation. That's what a motivation is; it's a simple example given to motivate the development of some sort of technique or reasoning.

If that's all, you might put it back now? The page is clearly in need of some form of motivational example; someone who doesn't know what induction is will most likely not be able to figure it out easily from the page as it stands. Drostie 21:34, 20 April 2006 (UTC)

My two cents: Yes, the page is sorely in need of work. Thanks for taking a stab at it, Drostie. Your proposed Motivation section is at least as good as the current Formal Definition/Example section, although I would like it to be more concise and less conversational. That said, does it do anything that the example in Formal Definition does not? That too is pretty gentle (though your version is more motivational).

Another two cents: In my mind mathematical induction is certainly traditional. I don't understand "absolute property"; does it mean a statement that holds at the top level of the deduction, not under any hypotheses? Your explanation of this point above does nothing for me. Joshua Davis 22:11, 20 April 2006 (UTC)

Mathematical induction is in a sense traditional. But if you don't consider it so, consider that

The definition of the word "traditional" in this context is is incredibly vague if not made explicit; and
It does not make sense to say that the reason for the use of this method is simply that some other methods don't work (unless some explicit account of why that would make sense is given).

Michael Hardy 22:46, 20 April 2006 (UTC)

[edit] Motivation

This section needs cleanup, but to conform to notational conventions and in content.

Often, in mathematics, there are observations which seem to defy traditional proof approaches. Take, for example, the claim that "the sum of the first n odd numbers is n²." You can verify it by hand for the first few n: 1 = 1 = 1², and then 1 + 3 = 4 = 2², and then 1 + 3 + 5 = 9 = 3². But it's not exactly clear how to prove it for all positive whole numbers n.

A proof by induction seeks to show a certain absolute property of the claim itself. This property is that "If the sum of the first n odd numbers is n squared, then it is also the case that the sum of the first n + 1 odd numbers is (n + 1)²."

This property is devilishly easy to show. If, indeed, the sum of the first n odd numbers were n², and the (n + 1)th odd number is 2n + 1 (which it is), then the sum of the first n + 1 odd numbers is n² + 2n + 1. And it's simple algebra to see that this number, in turn, is (n + 1)².

The absolute property that we've shown -- which is "If the claim is true for n, then it's true for n + 1 as well," -- is something like a method to climb up a ladder. If you've got your feet at some n which is on the ladder, this property lets you go one step higher, to n + 1, on the ladder.

Now, we already verified the original claim for the first three cases. We could verify it for n = 4, by hand, as well (1 + 3 + 5 + 7 = 16), but why bother? Instead of doing that sum for n = 4, why not just use the property that we just proved? Our claim was true for n = 3, so it must be true for n = 3 + 1 = 4. And since it's true for n = 4, it must also be true for n = 5. And since it's true for n = 5, it must be true for n = 6. In fact, if you are given any finite counting number m, you can go through this sort of chain to "climb up the ladder" from 1 to m, and prove that this property is true for m as well.

Just by proving two claims: "It's true for n = 1", and "If it's true for n, then it's true for n + 1," we've managed to finangle a proof that works for every finite counting number. And we don't need to go through those laborious sums to prove it.

[edit] Proving induction

There has been a small flurry of recent edits to the proof section which has caused me to become concerned for the integrity of the article. It would seem that the prospect of editing a genuine proof has evoked in some people the idea that playing mathemtician with it is a good idea. I think the last three edits (as of 14:48, 6 September 2006 (UTC)) show that this is not the case.

Look at the section as it existed when I merged it. It was straightforward, though as the subsequent edits of JRSpriggs suggest, perhaps not optimally worded. There was a nice separation between the "weak" and "strong" inductive cases and I didn't try to use one to prove the other. I think that the presentation as I had it was better for a novice (many of which must come to this page) than it's turned out in subsequent versions, especially the present one.

I think the last three edits have been a step backwards. First of all, some enterprising soul (known only by IP address) decided that weak induction should be proved for the integers from strong induction. Okay, it's elegant. It's not beautiful, though (see Mathematical jargon for the quote) because it clouds the point of what weak induction is about. People who like to think of induction as a domino effect (i.e. novices who visit this page often) will not be enlightened by learning that it is in fact a special case of transfinite induction. Not only will they likely not have heard of the latter, but they will be confused by the logical nitpicking that we use to eliminate the "trivial step" for strong induction. Furthermore, as a result of this edit, yet another axiom was tacked onto the list. I would like to point out that this is unnecessary, since it essentially states the explicit definition of the order with respect to which the natural numbers are well-ordered (as in the first axiom). It also confuses the novice with more logicalisms; ey will wonder what hidden reason we might have for stating something so obvious as that n is less than n + 1!

As I was writing this I also began to wonder, as was already discussed in the AfD for the old proof article, why exactly we need this proof. I defended it then, but it seems to serve an ambiguous purpose: when in mathematics do people actually use it? We could write down lots of equivalences that are not useful. My opinion is that this proof is relevant in exactly one situation: when the natural numbers are defined "top-down" as a subset of the real numbers (as the intersection of all sets closed under addition and containing 1). In that case, we are given an ordering satisfying n < n + 1 for all n which is a well-ordering (provable without induction), but induction is not clear. Then it must be proved, using the technique in this article. The other construction, by Peano axioms, of course includes induction and therefore this proof is irrelevant.

Concerning the dependence between "weak" and "strong" induction...the names are misnomers. They are equivalent principles for the natural numbers. "Weak" should not be derived from "strong" because, as I said above, it is confusing. It is also philosophically and historically different: once weak induction is noted, strong induction may be derived, and then generalized to transfinite well-ordered sets, where it is the only induction.

However, everything I've said here about mathematical and historical reasons is just opinion, and if there is anything this proof suffers from it is a mess of different opinions. My vision for it is that it should emphasize the "top-down" relevance, excise the dependence of weak and strong induction, and remove the formal logical flavor that characterizes it now (what with the list of axioms). However, this really ought to be sourced from somewhere, so that it becomes more than just opinion.

My $6.65. Ryan Reich 14:48, 6 September 2006 (UTC)

This proof requires at least three assumptions:

   1. The set of natural numbers is well-ordered.
   2. Every natural number is either zero, or n+1 for some natural number n.
   3. For any natural number n, n+1 is greater than n.

My main concern is that the third assumption has been slighted by other writers. It is necessary to tie the ordering mentioned in the first assumption to the successor function mentioned in the second assumption. Without it, one can construct models which satisfy the first and second of these assumptions and also all of Peano's postulates other than induction, and yet does not satisfy mathematical induction. Specifically, one can use the polynomials in one variable with integer coefficients for which the leading non-zero coefficient (if any) is positive. Give zero, successor, addition, and multiplication the usual meanings on those polynomials. Assign Gödel numbers (actual natural numbers) to these polynomials; and let the ordering be the result of applying the usual ordering of the natural numbers to the Gödel numbers. Then this model is well-ordered with order-type ω and it satisfies all of Peano's postulates EXCEPT the axiom schema of induction. However, it does not satisfy the third assumption listed above. JRSpriggs 05:31, 7 September 2006 (UTC)

I suppose I'll be "playing mathematician" by actually having a conversation about this, but here's my feeling. What you have said is, of course, correct, but in a sense, it is unreasonable because of the way the first axiom is written. Technically, of course, saying that "The natural numbers are well-ordered" could mean that they have any old well-ordering, but the intent was clearly to refer to the natural ordering induced by succession. My point is simply that anyone not steeped in mathematical logic wouldn't notice the difference, and listing axiom 3 separately is awkward. Your goal could equally well be accomplished by rephrasing axiom 1 to specify the ordering, which makes it flow better.

This was probably the least of my complaints, though. My overall problem with this proof is that it's clearly become a personal project for a number of people who all see it slightly differently, and as a result it's lost any elegance of prose or mathematical beauty it might once have had. Every sentence must contain its precise assumptions and deductions, and all ideas must be dismembered into their atomic constituents, stated in separate sentences. Furthermore, this encyclopedia is not a collection of proofs, but I don't think we really understand yet why we've included this one. I argued in the AfD that it's an important point, but I don't think any of its importance is emphasized in the article. Ryan Reich 13:18, 7 September 2006 (UTC)

When I saw that 64.42.233.61 had completely rewritten my proof, I was almost unable to resist the urge to just revert him out-of-hand. But I realized that I was angry just because I thought of my version as my creation, which does not mean that it is necessarily better. So I waited until I had calmed down and carefully read his proof. While he did not cover as many details as I did, he did give a more direct proof and one which is probably easier for most people to read. So I limited myself to just adding back the assumption which he used, but did not acknowledge. Actually when I had rewritten the proof earlier, I had put in more assumptions than were necessary. So I trimmed it down to what was necessary.

Of course, I realize that you and most people would be thinking of the usual ordering on the natural numbers when you refer to the well-ordering. But it does not say that. And it CANNOT say that without using the axiom schema of induction, which would be begging the question. One cannot even show that the usual well-ordering of the natural numbers is well-defined without using induction. The only situation I can see where this proof would be used would be if you start with set theory and then try to define the natural numbers as a subset of the ordinals.

I do not understand your statement that "... when the natural numbers are defined "top-down" as a subset of the real numbers (as the intersection of all sets closed under addition and containing 1). In that case, we are given an ordering satisfying n < n + 1 for all n which is a well-ordering (provable without induction), but induction is not clear.". How can you show within the theory of the real numbers that the natural numbers are well-ordered? JRSpriggs 03:51, 8 September 2006 (UTC)

I apologize for the hasty and impolite rewrite. I had just seen a way of eliminating two assumptions (n+1 is the smallest number bigger than n, 0 is the smallest number) and charged ahead in my excitement put it into place. I would welcome any modifications to the proof in order to improve clarity - the ideal proof proves as well as teaches. Hopefully, we will still be able to get by without re-introducing the extra assumptions. I would also concur that the whole well-ordering of the naturals becomes problematic without defining them as a subset of ordinals - which then introduces extreme complexity. 64.42.233.61 15:50, 13 September 2006 (UTC)

One can define the real numbers as a field totally ordered in a manner which respects addition and multiplication by a number greater than zero and such that every non-empty set which has an upper bound has a least upper bound (not necessarily belonging to the set). One could then treat the naturals as a subset of the reals and show that the inherited order induces a well-order on the naturals. It's not too hard to show that this definition of real provides uniqueness - but constructing an example without using induction might be difficult. Standard constructions are often based off of the rationals (Cauchy sequences, Dedekind cuts) and rationals are often defined as a pair of naturals with an equivalence relation. I'd be mighty impressed with a construction of reals which does not rely on natural induction. 64.42.233.61 17:54, 26 September 2006 (UTC)

[edit] Frog example

The frog example is bad, since proving that jumping from one pod to the next is possibly does not necessarily imply that the next lily pod will carry the frog. 128.130.40.149 13:13, 10 October 2006 (UTC)

I suggest that YOU reword it to make it correct. Or replace it with a better analogy. JRSpriggs 09:49, 11 October 2006 (UTC)

I just read the article for the first time and I would like to thank everyone who has contributed. It is a very nice article. That said, the one thing that seemed strange and out of place was this frog jumping example. I was left with questions of reachability and left wondering what the example was trying to clarify. --Jake 19:56, 9 December 2006 (UTC)

[edit] Cut-the-knot reference?

At the bottom of the page, the link to cut-the-knot says "(Warning, this is not a reliable source.)". Why is this there? The c-t-k wikipedia page doesn't mention any reliability problems. -- BillWeiss | Talk 16:37, 17 October 2006 (UTC)

On the page referred to it says "... n here is an 'arbitrary' integer." in a context where n must be positive. JRSpriggs 07:12, 18 October 2006 (UTC)

[edit] Elevator proof

User:JIP contributed the following "proof":

With mathematical induction, it is possible to prove that the elevator in an apartment building is always going in the right direction when it arrives at your floor. The proof is quite simple:

Let n equal the number of floors. In the base case n=2, the proof is trivial: there is only one direction for the elevator to go to.
Consider the case for n+1 floors. If the elevator is on any of the n first floors, the claim is true by induction. If it's on the top floor, there is only one direction for it to go, and thus the claim is trivially true. Thus, the case for n+1 floors is proven.

I'm not sure if this proof is wrong (and facetious) or proper (and ambiguous), so I have removed it until he gives a coherent explanation of what "the right direction" means. See related discussion on his talk page.

In particular, if he means that "the elevator is always going in the direction that you wish it to go," then the proof is facetiously wrong because the statement "If the elevator is on any of the n first floors, the claim is true by induction" is false. Consider two people who enter an elevator on the ground floor going up; consider myself on the 3rd floor going down. If one of them presses "3" and another "5", then the elevator most certainly isn't going in the direction I want it to go when it arrives at my floor.

--Drostie 05:27, 24 November 2006 (UTC)

[edit] Who is JRSpriggs?

Yesterday I added a very simple paragraph about Fermat's method of infinite descent to this article, simply because I saw no such reference in the article yet, and that method is historically significant.

Today I found that "JRSpriggs" had changed a simple sentence into an obtuse piece of hyper-mathematical prose. I went looking for his user page, to discuss it with him directly, but there was no "User:JRSpriggs" page within Wikipedia. So I reverted his edit.

Now I see that "JRSpriggs" has already gotten involved in a few disputes on this page. Now I'm curious -- who is this guy? And why won't he leave his user page up so the rest of us can see it? DavidCBryant 15:45, 26 November 2006 (UTC)

I put back JRSpriggs's changes for two reasons. One of his changes corrected the spelling of one of the links; the name was "Pierre de Fermat", not "pierre de fermat", as your addition had it. The other change was that he added an explanantion of the relationship between infinite descent and induction. Since this is the article about induction, I felt that an explanantion of the connection was required.

There is no requirement that any user have a user page.

Thanks for your contributions. -- Dominus 18:38, 26 November 2006 (UTC)

OK. Fine by me. I do wonder about accessibility, though. For the general reader, as opposed to trained mathematicians. DavidCBryant 22:21, 26 November 2006 (UTC)

I always worry about that too. But without some sort of explanation, won't a general reader be mystified about what infinite descent is even doing here in the first place? So I thought it would be better to put in some explanation. If you think you can make the explanation more accessible to the general reader, please go for it. -- Dominus 22:45, 26 November 2006 (UTC)

To DavidCBryant: I have been editing articles (mostly in Math and Physics) since February 2006. I do not have a user page because I never created one -- I have no interest in talking about myself for the public. I do have a talk page, User talk:JRSpriggs, but I prefer to talk on the talk pages of the article in question.
The reason I took out your sentence, "Therefore if the statement is not true when n = 1, it cannot be true for any natural number.", is two-fold: (1) it is unnecessary, because "... if a statement is true for a natural number n it must also be true for some smaller natural number m (m < n)." is sufficient to reach a contradiction without any additional assumption about one or zero; (2) we are using zero-based induction in this article (over some opposition which wants one-based) and mentioning one would just throw fuel on the fire.
And the sentence "This is equivalent to using mathematical induction with the inductive hypothesis being that the statement is false for all natural numbers less than or equal to m." was added to fill the gap left by the sentence removed and for the reason mentioned by Dominus. JRSpriggs 07:38, 27 November 2006 (UTC)

Thank you for replying, JR. Do you mind if I call you JR?

I understand your reasoning. You're clearly well trained in mathematics. This may not be the right place to bring it up, but I liked the original paragraph better for two simple reasons – it was more intuitive, and not rigorous.

I understand the need for rigor in proofs. But an encyclopedia is not a textbook. My judgment is certainly fallible. But in my opinion, some statements in an encyclopedic article about a mathematical subject (especially an article about a relatively simple subject, like this one) should be phrased in layman's language calculated to elicit the Aha! response from a few readers who may not yet have contracted the math bug. So I was trying to steer away from big words like "equivalent" and "induction hypothesis" – not because I can't use them myself, but because I'm writing for a target audience.

I can also see that the question "is zero a natural number, or not?" will never be settled one way or the other. I didn't know that the other people working on this page had decided to answer that question in the affirmative. In the future I will read the talk pages more carefully.

Anyway, I have no desire to belabor the point about the target audience. Thanks again for writing back. DavidCBryant 23:07, 27 November 2006 (UTC)

I rewrote the last sentence to try to make it even clearer (merging our two versions). Now, it says "Using mathematical induction (implicitly) with the inductive hypothesis being that the statement is false for all natural numbers less than or equal to m, we can conclude that the statement cannot be true for any natural number n.". I hope that you like that better. JRSpriggs 06:37, 28 November 2006 (UTC)

[edit] I have added some links to a video Podcast and they were remove

Hi everyone I have added some links to a video podcast that I own. I think they are a nice addition to wikipedia please look at them and express you oppinion here , judge for yourself if the links are really useful or not to wikipedia.

[1] Video PodCast by http://www.isallaboutmath.com/

If any of you think they are valuable to wikipedia then feel free to add them back in the external links.

Regards SilentVoice 03:26, 22 January 2007 (UTC)

[edit] "Floating" link

At the start of the Generalization section of the article is the phrase and wikilink to "Transfinite induction". It seems syntactically out of place. Perhaps a math-savvy editor would like to review this. --zenohockey 02:15, 18 February 2007 (UTC)

Retrieved from "http://en.wikipedia.org../../../m/a/t/Talk%7EMathematical_induction_4239.html"