induction vs recursion
in [Math]
|
Prev: JSH: Using Usenet
Next: A reformulation of ZF-Reg.
From: porky_pig_jr on 19 Jun 2010 14:03 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.)
From: porky_pig_jr on 19 Jun 2010 14:14 On Jun 19, 7:17 am, David C. Ullrich <ullr...(a)math.okstate.edu> wrote: > (*) A1 \/..\/ A_n \/ A_(n+1) = (A1 \/..\/ A_n) \/ A_(n+1) > > you're _also_ giving an informal presentation! Any use > of notation like "a_1+...+a_n", involving those three > dots, is informal. Why? Because it relies on pattern > recogntion on the part of the reader. _Any_ time > you see, say, "a_1+...+a_n", that's an informal > abbreviation for "x_n, where x_1 = a_1 and > x_{j+1} = x_j + a_{j+1}". OK, instead of a_1 + dots + a_n I should have written, say, in LaTeX, \sum_{i=1}^{n} a_i. I don't think it's such a big deal here. No one should object \sum_{i=1}^{n} a_i (?) But in that recursive descent ("proof 2"), those dots do look a bit suspicious. We make n-1 steps. And then, result contains n terms. Again, in (slightly informal) LaTeX, \[ \bigcup_{i=1}^{n} A_i = \bigcup_{i=1}^{n-1} A_i \cup A_n = \bigcup_{i=1}^{n-2} A_i \cup A_{n-1} \cup A_n \dots \* these dots? = A_1 \cup A_2 \cup \dots \cup A_n \* these dots \] (I just didn't want to use LaTeX in posting, but I didn't want to use \/ instead of \cup either.)
From: cwldoc on 19 Jun 2010 22:06 > 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.
From: porky_pig_jr on 20 Jun 2010 17:48 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. 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. 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. 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.
From: David C. Ullrich on 21 Jun 2010 06:57
On Sat, 19 Jun 2010 11:03:15 -0700 (PDT), "porky_pig_jr(a)my-deja.com" <porky_pig_jr(a)my-deja.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? You can't reason formally about things that have not been formally defined! From a formal point of view, an informal proof of something is just a hint rgarding how a formal proof might be constructed. Getting from one to the other requires recognizing patterns, etc, that are not explicit in the formal proof - it requires some sort of "I know what you mean" on the part of the reader. There are officiial rules defined exactly what a valid formal proof is; there is no such official definition of what a valid informal proof is, and without such a definition it's impossible to give a formal proof that P is a valid informal proof. 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. >(Apparently the whole question "was proof 2 a valid proof from the >mathematical standpoint" is not that trivial, looking at other >responses. I see sort of two main threads of responses. Many of the comments in the other one are simply silly. There's nothing wrong with proof 2. Seeing comments on usenet saying that there is something wrong with it proves very little. > 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. 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. >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.) |