Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10.1 6/24/83; site pucc-i
Path: utzoo!watmath!clyde!burl!ulysses!mhuxj!ihnp4!inuxc!pur-ee!CS-Mordred!Pucc-H:Pucc-I:ags
From: ags@pucc-i (Seaman)
Newsgroups: net.math
Subject: Re: Induction help, please?
Message-ID: <690@pucc-i>
Date: Fri, 19-Oct-84 10:28:00 EDT
Article-I.D.: pucc-i.690
Posted: Fri Oct 19 10:28:00 1984
Date-Received: Tue, 23-Oct-84 01:21:21 EDT
References: <5264@yale.UUCP> <28200045@uiucdcs.UUCP> <1204@utah-gr.UUCP>
Organization: Purdue University Computing Center
Lines: 30

>  In article <28200045@uiucdcs.UUCP> west@uiucdcs.UUCP writes:
>  >Step 2 mentioned in the previous response is poorly expressed.
>  >The induction step of an induction proof proves that the hypothesis
>  >holds at a given value under the assumption that it holds for all
>  >values of the parameter between there and the values considered in the
>  >basis step.
>  
>  This is what is called "strong" or "complete" induction.  It is often
>  only necessary to know that P(n) -> P(n+1).  Sometimes, as you have
>  stated, one must know that P(1..n) -> P(n+1).

You have that backwards.  "P(n) -> P(n+1)" is a stronger assertion than
"P(1..n) -> P(n+1)".  "P(1..n) -> P(n+1)" is ALWAYS sufficient to establish
induction.  Therefore it logically follows that "P(n) -> P(n+1)" can
establish induction as well, and it is often just as easy to prove.

A better way to state it is "P(all predecessors of n) -> P(n)".  This
handles induction for cases that do not necessarily begin with 1, and
it also reduces the usual two-step induction proof to a one-step proof.
You don't have to prove P(0) (or whatever) as a separate step, since that
logically follows from:

	(1) P(all predecessors of n) -> P(n)  for all n, and

	(2) 0 has no predecessors (among the natural numbers).
-- 
[This is my bugkiller line.  It may appear to be misplaced, but it works.]

Dave Seaman			My hovercraft is no longer full of 
..!pur-ee!pucc-i:ags		eels (thanks to my confused cat).