induction vs recursion
in [Math]
|
Prev: JSH: Using Usenet
Next: A reformulation of ZF-Reg.
From: cwldoc on 21 Jun 2010 09:03 > On Jun 20, 2:06 am, cwldoc <cwl...(a)aol.com> wrote: > > > On Jun 19, 7:09 am, David C. Ullrich > > > <ullr...(a)math.okstate.edu> wrote: > > > > On Fri, 18 Jun 2010 18:21:26 -0700 (PDT), > > > "porky_pig...(a)my-deja.com" > > > > > > <porky_pig...(a)my-deja.com> wrote: > > > > >Going through my old notes from Probability > class > > > I took a while ago, > > > > >I came across at a proof which I marked as > "proof > > > by induction", but > > > > >now I'm not so sure. The proof does kind of > > > "recursive unwind". It > > > > >looks correct and certainly has something to > do > > > with induction. I hope > > > > >somebody can point out how to justify that > proof. > > > I'll try to be as > > > > >concise as possible. > > > > > > >The proof is about "finite additivity". At > this > > > point we have already > > > > >proved a "general additivity": if the events A > and > > > B are pwd (pairwise- > > > > >disjoint), then P(A union B) = P(A) + P(B). > Now we > > > want to prove a > > > > >finite additivity for pwd set of n events > {A_1, > > > A_2, ..., A_n: the > > > > >probability of union of such events is the sum > of > > > their respective > > > > >probabilities. The proof is clearly by > induction. > > > The base step is for > > > > >n = 2, and we have already proved that. > > > > > > >Now this is how I would reason for inductive > step: > > > assume our > > > > >hypothesis is true for n. Now write > > > > >A_1 union A_2 union ... union A_n as > > > > >(A_1 union A_2 union ... union A_{n-1}) union > A_n. > > > > >Then > > > > >P(A_1 union A_2 union ... union A_n) = P(A_1 > union > > > A_2 union ... union > > > > >A_{n-1}) + P(A_n) > > > > >(by "general additivity for n=2 which we have > > > already proved) > > > > >= sum of probabilities of events A_1 through > > > A_{n-1} plus P(A_n) > > > > >= sum of probabilities of events A_1 through > A_n. > > > Done. > > > > > > >However, this is not what instructor did. > Instead > > > he simply proved > > > > >that the formula is valid for any > > > > >n events by keep peeling off the last, nth > event, > > > writing probability > > > > >as a sum of probabilities of two resulting > sets, > > > then peeling off the > > > > >(n-1)th event from the first set, etc etc. > Like > > > this: > > > > > > >P(A_1 union A_2 union ... union A_n) = (peeled > off > > > the last event) > > > > >= P([( A_1 union A_2 union ... union A_{n-1}] > > > union A_n) > > > > >= (by general additivity) P(A_1 union A_2 > union > > > ... union A_{n-1}) + > > > > >P(A_n) > > > > >= (peeled off the (n-1)th event) > > > > >= P( [A_1 union A_2 union ... union A_{n-2}] > union > > > A_{n-1}) + P(A_n) > > > > >= P(A_1 union A_2 union ... union A_{n-2}) + > > > P(A_{n-1}) + P(A_n) > > > > >= ... > > > > > > >well, you got a picture. In n-1 steps we got > the > > > formula. For any n it > > > > >takes n-1 steps to derive the result. Hence > it's > > > valid for any n > 1. > > > > >Done. > > > > > > >Now, formally this proof is not what I got > used to > > > when I think of > > > > >induction. This is more like recursive unwind. > > > OTOH I know there is a > > > > >deep connection between induction and > recursion. > > > My question is: how > > > > >can we formula justify this result? By > "formally", > > > I mean on basis of > > > > >induction principle. > > > > > > You've already shown us the formal > justification! > > > That's exactly > > > > what the formally-by-induction proof that you > gave > > > at the start > > > > is. > > > > > > Let's call the two proofs above proof 1 and > proof > > > 2. Proof 2 is > > > > slightly informal, and proof 1 is a formally > > > inductive precise version > > > > of the same argument. (That seems so clear that > > > maybe it's > > > > not really what you're asking. It's impossible > to > > > give a formal > > > > proof of the following statement: > > > > > > (*) "Proof 1 is a formal version of proof 2". > > > > > > The reason is that proof 2 _is_ informal.) > > > > > > >TIA. > > > > > Alas, this is exactly what I'm asking for: how to > > > reason that proof 1 > > > is a formal version of proof 2? If this question > is > > > not admissible, > > > then why? The proof 1 is what I would have done. > The > > > proof 2 is > > > what's given, intuitively I believe it's correct. > > > Certainly they are > > > connected. It's like defining the object (say, > sum) > > > iteratively vs > > > recursively. So the proof 2 is a bit loose, less > > > formal than 1, but > > > not necessarily incorrect. That's clear. Yet I > want > > > to reason formally > > > that they are related. Again, is that possible at > all > > > to state > > > anything about such a connection? > > > > > (Apparently the whole question "was proof 2 a > valid > > > proof from the > > > mathematical standpoint" is not that trivial, > looking > > > at other > > > responses. And - yes, the guy who taught the > course > > > is not a computer > > > scientist. His major area of research is > probability > > > and statistics, > > > and Real Analysis. And - yes, recursion makes you > > > think of computer > > > science, of course. But recursive definitions is > not > > > the exclusive > > > domain of computer science. we do define > functions > > > recursively, right? > > > and we can prove by induction that such > definition, > > > given certain > > > constrains, is valid in a sense that it defines a > > > unique function. > > > > > But in any case, thanks to everyone who joined > the > > > thread.) > > > > You might find the following reference > illuminating: > > > > There is a section on the "Principle of Recursive > Definition," in the first chapter of the book > entitled, "Topology," by James Munkres, which is both > rigorous and accessible. > > > Yes, I know that book and I know the proof. It > introduces the > recursive definition of the function and then, later > on, proves by > induction that that creates a unique function. > Funny, I thought of > that book as well after I posted the question. (btw, > I took that > course, with Munkres. We covered the first five > chapters). > > But the book talks about recursive *definition*. Say, > we can define > factorial recursively: > > (i) 0! = 1 > (ii) n! = (n-1)! * n. > > We know (following the book) that this is a valid > definition in a > sense that it uniquely defines a function > "factorial". > > Now, suppose we want to prove that n! = Product from > 1 to n. What do you mean by the "product from 1 to n?" I believe that any attempt to define it would be something similar to what you wrote above as the definition of factorial: (i) 0! = 1 (ii) n! = (n-1)! * n. That is, the product from 1 to n is synonymous with n factorial. > The > rigorous proof would be by induction. We use (i) for > the base step and > we use (ii) for the inductive step. That's the > rigorous proof. In effect you are trying to prove that factorial equals factorial > Suppose, however, we simply follow the definition and > do the recursive > descent, using (ii). Eventually we reach (i). So, for > any n in N, > > n! = (n-1)! * n > = (n-2)! * (n-1) * n > = (n-3)! * (n-2) * (n-1) * n > ... > = 0! * 1 * 2 * ... * (n-2) * (n-1) * n > = 1 * 2 * ... * * (n-1) * n > = product from 1 to n. "n! = 1 * 2 * ... * * (n-1) * n" is just shorthand for: (i) 0! = 1 (ii) n! = (n-1)! * n, which was your definition for n! in the first place! > Since n is finite, we always have a finite number of > steps. So that's > a finite product and we can always compute it. > > That was essentially my question: how this > non-rigorous proof by > recursive descent relates to more rigorous proof by > induction. Seems > like they are directly related. So I think, being > somewhat informal, > we can use that recursive descent and even call it > induction. That's > what instructor did, proving the principle of finite > additivity. > > Thanks. > > PPJ. In my opinion, as long as a proof is clear and unambiguous, then it should be alright to use whatever shorthand is convenient!
From: porky_pig_jr on 21 Jun 2010 19:20 On Jun 21, 6:57 am, David C. Ullrich <ullr...(a)math.okstate.edu> wrote: > On the other hand, proofs as actually written down by actual > persons are almost never strictly formal. The reader _does_ > recognize what the writer meant in various places. > Well, the whole question arised because I looked at the proof, saw my note "proof by induction" and then said to myself: if I were writing that proof by induction then this is how I would have written that. Now, after some thinking, I see the connections between proof 1 and proof 2. The "..." in proof 1 make it appear less rigorous than proof 2, but connection is clear. So, in some respect, they are equivalent. > >(Apparently the whole question "was proof 2 a valid proof from the > >mathematical standpoint" is not that trivial, looking at other > >responses. > > I can't imagine why you bother to mention this. > > Worrying about the author's credentials is "officially" > silly in any case. When we're talking about such a > short simple proof it's _really_ silly. Suggesting that > an error has something to do with the fact that > the author might be a computer scientist is > arrogant and ignorant; many computer scientists > do math just fine. And suggesting that the author > being a computer scientist explains why he wrote > a flawed proof, _when_ in fact the proof is both > very simple and perfectly correct, is utterly stupid. > Dumb. Dumb like a brick. Awesomely gobsmackingly > stupid. > Well, as I said, someone may thought of instructor being a computer scientist because computer scientists like recursion. Personally I have nothing against computer scientists, in fact, being one of them, that is, have an advanced degree in Computer Science. I just sort of drifted into Analysis and related stuff. It just happened. Thanks for the feedback. PPJ.
From: Don Stockbauer on 21 Jun 2010 19:25 On Jun 21, 6:20 pm, "porky_pig...(a)my-deja.com" <porky_pig...(a)my- deja.com> wrote: > On Jun 21, 6:57 am, David C. Ullrich <ullr...(a)math.okstate.edu> wrote: > > > On the other hand, proofs as actually written down by actual > > persons are almost never strictly formal. The reader _does_ > > recognize what the writer meant in various places. > > Well, the whole question arised because I looked at the proof, saw my > note "proof by induction" and then said to myself: if I were writing > that proof by induction then this is how I would have written that. > Now, after some thinking, I see the connections between proof 1 and > proof 2. The "..." in proof 1 make it appear less rigorous than proof > 2, but connection is clear. So, in some respect, they are equivalent. > > > > > > > >(Apparently the whole question "was proof 2 a valid proof from the > > >mathematical standpoint" is not that trivial, looking at other > > >responses. > > > I can't imagine why you bother to mention this. > > > Worrying about the author's credentials is "officially" > > silly in any case. When we're talking about such a > > short simple proof it's _really_ silly. Suggesting that > > an error has something to do with the fact that > > the author might be a computer scientist is > > arrogant and ignorant; many computer scientists > > do math just fine. And suggesting that the author > > being a computer scientist explains why he wrote > > a flawed proof, _when_ in fact the proof is both > > very simple and perfectly correct, is utterly stupid. > > Dumb. Dumb like a brick. Awesomely gobsmackingly > > stupid. > > Well, as I said, someone may thought of instructor being a computer > scientist because computer scientists like recursion. Personally I > have nothing against computer scientists, in fact, being one of them, > that is, have an advanced degree in Computer Science. I just sort of > drifted into Analysis and related stuff. It just happened. > > Thanks for the feedback. > > PPJ Dictionary entry for recursion: recursion: see recursion.
From: porky_pig_jr on 21 Jun 2010 19:30 I chose the factorial because it's simple example. In general, deriving the closed formula from the recursive definition may be not that easy. What I meant: given the recursive definition, we can just follow the definition, "unwiding things", so to speak, till we reach the terminating condition. If we're lucky we get some closed formula. In my lecture notes that's how it was done. We stopped and said: well, that's the proof. And this is equivalent by doing the proof by induction, except we move "up" instead of "down". From the terminating condition (which we use as a "based step"), and up and up and up (using recursive definition to define the inductive step). I guess the second way is more formal. Yes, in that simple example I proved that factorial of n, defined recursively, is the product of all natural numbers from 1 to n. In general, when you look at the recursive definition, it is not immediately clear what's the closed form expression. Thanks for the feedback. PPJ.
From: David C. Ullrich on 22 Jun 2010 11:51
On Mon, 21 Jun 2010 16:20:07 -0700 (PDT), "porky_pig_jr(a)my-deja.com" <porky_pig_jr(a)my-deja.com> wrote: >[...] >Now, after some thinking, I see the connections between proof 1 and >proof 2. The "..." in proof 1 make it appear less rigorous than proof >2, but connection is clear. So, in some respect, they are equivalent. Save those thoughts! Many proofs that don't explicitly use induction are really proofs by induction in disguise. |