dardik@yale.ARPA (The Lord ) (10/04/84)
I have just learned from my recent computer science classes (in Discrete Mathematics and Algorithms, CS 260 at Yale) that I cannot do induction. I can say "yes that is a nice inductive proof", but to come up with one on my own is another story. In other words, I have no talent for it and need some real quickly (and it just turns out that I need it for reasons outside my classwork too). So, could anyone steer me to a book or something similar to help me? Could anyone give me some advice? Or am I doomed? Thanks, -Alan Dardik
eps360@foxvax1.UUCP (E.P. Shaughnessy ) (10/05/84)
************************************************************************** When I was a kid, I also had problems with induction. I just couldn't understand where to start or even why the thing worked. I eventually became proficient in induction in the following manner: I found a book that contained one induction problem that I could solve. I then convinced myself that as long as I could continue to solve these types of problems, I would never have difficulty with them in the future. Although it wasn't absolutely necessary, I successfully attacked a few more examples just to convince myself that my reasoning was correct. I haven't had a problem since. Ed Shaughnessy
holland@uiucdcs.UUCP (10/07/84)
Induction is perhaps one of the hardest "tricks" to conceptualize. It is probably THE hardest trick to get down on paper. Try lots of simple inductive proofs. Most books on abstract algebra will have at least a couple. I think that McLaine/Birkhoff has several. You can always do induction mechanically, in two steps: 1. is the hypothesis true when the index variable is 1 (or another starting value)? 2. is the hypothesis true when adding 1 to the index variable?
west@uiucdcs.UUCP (10/08/84)
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.
allenm@ittvax.UUCP (Allen Matsumoto) (10/08/84)
I can't decide if this is a simple reply or a parody of meta-induction. > > > When I was a kid, I also had problems with induction. I just > couldn't understand where to start or even why the thing > worked. I eventually became proficient in induction in the > following manner: I found a book that contained one induction > problem that I could solve. I then convinced myself that as > long as I could continue to solve these types of problems, I > would never have difficulty with them in the future. Although > it wasn't absolutely necessary, I successfully attacked a few > more examples just to convince myself that my reasoning was > correct. I haven't had a problem since. > > > Ed Shaughnessy Namely, I could interpret this as the following "theorem": Theorem: I can solve induction problems. (I := author) Proof (by induction): Base case: "I found a book that contained one induction problem that I could solve" Inductive step: "I then convinced myself that as long as I could continue to solve these types of problems, I would never have difficulty with them in the future." Optional further convincing for those not confortable with inductive proofs: "Although it wasn't absolutely necessary, I successfully attacked a few more examples just to convince myself that my reasoning was correct. I haven't had a problem since." Clearly this is not a proof in that the inductive step is unexplained, but the spirit of the reasoning is the same. In either case, this seems a reasonable response to a request for help with inductive proofs. If simple encouragement, it reads like an "I've also been there and survived" comment. If it was intended as an example and parody, it appears to be an artful attempt to be helpful in all three ways (encouragement, example, and parody). Assuming the best, GOOD SHOW! Allen Matsumoto (decvax!ittvax!allenm)
thomas@utah-gr.UUCP (Spencer W. Thomas) (10/11/84)
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). =Spencer
ags@pucc-i (Seaman) (10/19/84)
> 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).