Talk:Three forms of mathematical induction

This article was nominated for deletion on March 6 2006. The result of the discussion was no consensus.

What, no structural induction?

If the article needs changes, feel free to make them. Be bold! -- Cyan 04:17, 28 Jan 2004 (UTC)

Well, they're certainly not all like this!!! I agree that these are 3 fairly common situations in practice, however. -- Toby Bartels 22:08, 28 Jan 2004 (UTC)

I suspect that they are all like this if you allow an inclusive "or" between the three kinds. Can you cite counterexamples? (Notice that I said "suspect", since I can't prove this, as far as I can see.) Michael Hardy 23:53, 28 Jan 2004 (UTC)

The obvious (to me) missing type is where neither the base nor the inductive step is trivial.

No! That is not missing! I said if you allow an inclusive "or" between the three kinds. Michael Hardy 03:17, 29 Jan 2004 (UTC)

But all 3 kinds claim that the n = 1 case is trivial (or even vacuous). -- Toby Bartels 20:37, 29 Jan 2004 (UTC)

Of course this could be regarded as a special case of strong induction (3), where it just so happens that the only part of "true for all n<k" which you actually use is either vacuousness or n=k-1. But regarding it as such would be pedantry for the sake of defending this categorisation, not a useful description of the ways in which inductive proofs are performed in practice.

So, can I think of an example of a proof by induction where neither step is trivial? Not off hand, but I'm sure they exist. Onebyone 00:16, 29 Jan 2004 (UTC)

Anon posted a challenge which he/she claimed did not fall under the three listed cases, but then blanked it. [1] -- Cyan 00:25, 29 Jan 2004 (UTC)

If every node in a tree has either two children or none, then the number of nodes with two children is exactly one less than the number of nodes with none.

Proof by induction on n, the number of nodes in the tree having two children. We must show that there are n+1 nodes with no children.

Case n=0 is trivial - if all nodes have no children, then there is only one node total, hence 1 node with no children, and n+1 = 1.

Assume true for n=k (some k>=0). Then given such a tree having k+1 nodes with two children, choose one of the two-child nodes, each of the children of which has no children. This must be possible, since otherwise (by another induction I won't write out here) the tree has an infinite sequence of descendents, meaning that it is either infinite (which it isn't because it only has k+1 nodes with any children) or else cyclic (but then it wouldn't be a tree by definition of tree). Remove the children of the selected node from the tree. Then the resulting tree has only k nodes with two children, hence by the inductive hypothesis it has k+1 with no children. But comparing this tree with our original tree, we see that the original tree has exactly one more node with no children, hence it has k+2 nodes with no children which is the required number.

This precisely follows template (1) in the article, and the challenge was to prove the result using one of the forms listed. Onebyone 01:30, 29 Jan 2004 (UTC)

Oh yes, and the thing that I understand by "structural induction" can usually (my guess is always, but I don't want to have to prove it) be recast as strong induction on the size of the structure. In this case the fact that I could choose a nice terminal node made weak induction easy too. That's not necessarily to say that structural induction isn't sufficiently useful a concept to be added to the article (which would then have to be retitled), just that the challenge as stated can be met... Onebyone 01:43, 29 Jan 2004 (UTC)

Some structures require all ordinals, not just the natural numbers. This makes it type 3 so long its trivial for the smallest ordinal is trivial, which it usually is. But recasting is hardly the point here, since any proof can be recast in such a way as to avoid induction entirely! Yet for many proofs, that would be a foolish thing to do. -- Toby Bartels 20:37, 29 Jan 2004 (UTC)

I suspect proofs by structural induction also fit into one of these three forms if one tweaks them in obvious ways. But it's late and for now I'll defer that thought to another day. Michael Hardy 03:24, 29 Jan 2004 (UTC)

Here's why we can't say that they are all of (at least one of) these 3 forms: Each of the 3 forms specifies that the first case (n = 1 since Michael specified the set {1,2,3,...}) is trivial, or even vacuous. That is, IME, extremely common, and we can argue about language ("often" vs "usually" -- either is OK with me) to describe that commonality. This is not a mathematical claim, merely one about what is commonly found in mathematical practice. But to say that they are all like this is a mathematical claim that is false, because we cannot guarantee that the proposition is indeed trivial when n = 1.

I think that a good example can be found in a case of double induction, such as the proof that addition of natural numbers is commutative, given this recursive definition:

x + 1 = n' (where the prime indicates successor); and

x + y' = (x + y)'.

(I've started the natural numbers with 1 to fit Michael's specification of the set {1,2,3,...}, but it makes no real difference to the example.) The base case of the double induction, the proof that 1 + 1 = 1 + 1, is indeed trivial, so this is like type 1 (or rather its analogue when the set in question is {1,2,3,...} × {1,2,3,...} instead of just {1,2,3,...}). But if you break that into two parts -- an outer induction on n that n commutes with every m, and an inner induction on m to prove that fact for the specific n in question -- then the n = 1 case of the outer induction is not trivial. Indeed, it takes an entire proof by induction to do it!

This is not an ideal example, since for practical purposes, you want to approach the problem as a single case of double induction, not as several individual simple inductions. But technically, the latter is a valid analysis -- and in a proof that double induction is valid in the first place, it's a very necessary analysis. So the claim that the n = 1 case is always trivial cannot stand without qualification.

-- Toby Bartels 20:37, 29 Jan 2004 (UTC)

Would it be agreeable to merge this article with mathematical induction? AxelBoldt 22:50, 20 Feb 2004 (UTC)

Yes, and I think it's obvious enough that I'll do it immediately. Melchoir 21:39, 5 March 2006 (UTC)[reply]

I might have gone along with such a merger, although I am inclined to disagree with it and could give arguments, but Melchoir's recent edit was unbelievably irresponsible, and I have reverted. He took a small fragment of material from this article, paraphrased it in a way that made it clear that he had not the least understanding and just couldn't be bothered, put it in a completely random place in the mathematical induction article where it made no sense, and the result was a section that looked absurd and stupid. To say that it missed all of the point is a great understatement. Definitely the worst edit I've seen in a long time. Michael Hardy 01:41, 6 March 2006 (UTC)[reply]

P(0) is required to be proved!

As I have mentioned at transfinite induction, you do need to prove P(0). Mark Hurd 20:19, 3 Nov 2004 (UTC)

You completely misunderstand. Yes, you need to prove P(0), but you don't need to prove it separately when you get get both parts of the proof in one step. In the kind of examples used in secondary school, the two steps do need to be separate. In one particular form of mathematical induction, appearing third on this list, one step gets both the case n = 0 and the more general case, without need for a separate step to prove the case n = 0. Michael Hardy 23:23, 3 Nov 2004 (UTC)

Examples

When someone gets to examples, I think they should come after the list of three forms. Michael Hardy 23:18, 29 May 2005 (UTC)[reply]

Does renumbering render form 1 and 2 identical?

There been a disucssion on the AFD page and my talk page on this. I think its probably better discussed here:

Form 2 can be easily be rendered as form 1, by a simple renumbering. Define two sequences of cases: let $case_{A}$ $case_{A}$ the original cases and let $case_{B}(n)=case_{A}(n+1)$ $case_{B}(n)=case_{A}(n+1)$ , be a renumbered sequence. So the form 2 induction for $case_{A}$ $case_{A}$ just becomes a form 1 induction for $case_{B}$ $case_{B}$ , with an extra vacuously true case $case_{B}(0)$ $case_{B}(0)$ . In general induction arguments don't have to start at 1, if you can prove all cases up to m by other means and then prove >m using induction then its just as good an argument. --Salix alba (talk) 13:22, 7 March 2006 (UTC)[reply]
- "Form 2 can be easily be rendered as form 1, by a simple renumbering." That is utterly false. The fact that a certain set has two members would then be relied on in a absolutely crucial way in the step that would have been renumbered so as to be called "1". A property of the number 2 would still be relied on at that step in an essential way. Michael Hardy 21:23, 7 March 2006 (UTC)[reply]
This essentially brings up a question about the definition of induction. The way I've thought about it is take a infinite sequence of statements S₁, S₂, ..., the task of an induction argument is to prove that all these statements are true. (This is the definition in Spivac's calculus). How these statements relate to a set, is a specific of the particular induction. With this way of thinking about induction I can quite easily have statement S₁, concern a set of two elements, and S₂ concern a set of three elements.

For the product rule define

S_{1}:(f_{1}f_{2})'=f_{1}'f_{2}+f_{1}f_{2}'.\,

S_{2}:(f_{1}f_{2}f_{3})'=(f_{1}'f_{2}f_{3})+(f_{1}f_{2}'f_{3})+(f_{1}f_{2}f_{3}')\,

S_{n}:(f_{1}f_{2}f_{3}\cdots f_{n+1})=(f_{1}'f_{2}f_{3}\cdots f_{n+1})+(f_{1}f_{2}'f_{3}\cdots f_{n+1})+(f_{1}f_{2}f_{3}'\cdots f_{n+1})+\cdots +(f_{1}f_{2}\cdots f_{n}f_{n+1}').\,

this is then a case of form 1 induction.

The definition used in the article

Proofs that a subset of { 1, 2, 3, ... } is in fact the whole set { 1, 2, 3, ... } by mathematical induction usually have one of the following three forms.

I find a rather non-standard presentation of induction, and not particularly clear. So maybe this is not an article about induction in general, but an article about a specific type of induction where the index of the sequence is the same as the number of elements in a set.

This is not to say that the examples in the article are without merit, and it does highlight some interesting cases where careful indexing is needed. I seem to recal some inductive arguments in number theory, which only work for numbers n>m where m is some rather large number. Fermats last theorem aⁿ+bⁿ≠cⁿ, is an example where cases for all large n were proved first, (possibly by induction), the cases for small n proving particularly tricky to prove. --Salix alba (talk) 01:52, 8 March 2006 (UTC)[reply]