Talk:Mathematical induction

A simple example of inductive proof

We need a simple example of an inductive proof: something easy to understand, but preferably something that doesn't have an even easier proof without induction. The problem on this web page might be a good example: [1] --Catherine Woodgold 12:04, 6 May 2007 (CDT)

problems

I have some problems with the leading section. Maybe it's my language level and terminology problem, but... consider the following remarks:

• inductive proof is not a proof by cases. The latter describes a reasoning when the statement to be proved is split in a _finite_ number of cases (called also "proof by exhaustion" or brute force in computer science). See famous 4 colors problem.
• is is applicable _whenever_ the problem can be divided into enumerable propositions. IMHO, the image is too simplistic: "divide the problem and you can prove it by induction". Wouldn't it be better to say "it is _used_ to prove an infinite number of statements that have similar form and depend on an integer parameter n" -- or something along these lines.
• modus ponens does not apply... In fact the mathematical induction can be viewed as a far-reaching generalization of this concept, but it is not correct to say "modus ponens is used" (there is infinity in question!)... (BTW, do we need Latin at the beginning?)

Besides, I agree that the chosen example is not the simplest explanation of the idea. So shall we rework all of this? --Aleksander Stos 09:59, 15 May 2007 (CDT)

I agree, we need a simpler example. Always bear in mind: an example, or definition, is too "advanced" if people in need of the article, in the first place, can't be expected to understand it. --Larry Sanger 10:48, 15 May 2007 (CDT)

Yes, we should pretty much re-work everything on this page. The introduction is very inaccessible, as is the content of the example. There are thousands of analogies used to illustrate the idea of induction (dominoes, climbing a ladder, family traditions, etc.); let's choose the best one or few and write a narrative-style article.

Also I think Induction (possibly Induction (mathematics) if disambiguation is needed) would be a more fundamental article title than "Inductive proof". - Greg Martin 11:35, 16 May 2007 (CDT)

I've rewritten it. A number of things were objectionable about the first paragraph. In particular, the definition of "induction hypothesis" was grossly wrong. "Induction hypothesis" means the assumption that the proposition holds in a particular unspecified case, relied on in proving that it also works in the next case. I've also added an example of the sort that secondary-school pupils will understand readily. In fact, I suspect that that particular example is the very first one that they usually see. Michael Hardy 12:07, 13 July 2007 (CDT)

The current example is the standard, but if the aim was to include an example for which a non-inductive proof is hard to find, this is not a good example. Apocryphally, Gauss found the simplest or "book" proof as a wee lad.

Also, eventually, someone should link to pages about "strong" and "structural" induction, and perhaps an advanced page should be created that explains, for instance, the equivalence with the axiom of choice. Or at least, the equivalence should be mentioned somewhere, if the explanation is given on the "axiom of choice" page.Barry R. Smith 10:49, 6 April 2008 (CDT)