induction vs recursion
in [Math]
|
Prev: JSH: Using Usenet
Next: A reformulation of ZF-Reg.
From: porky_pig_jr on 18 Jun 2010 21:21 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. TIA.
From: William Elliot on 19 Jun 2010 01:05 On Fri, 18 Jun 2010, porky_pig_jr(a)my-deja.com wrote: > 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. That's wrong. Use A1 \/..\/ A_n \/ A_(n+1) = (A1 \/..\/ A_n) \/ A_(n+1). > 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. Yea, it sucks as a proof. > 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. > That's not a proof. It's a recursive expression for calculating P(A1 \/..\/ A_n). Are you sure the instructor is a mathematician and not a computer scientist?
From: Frederick Williams on 19 Jun 2010 06:58 "porky_pig_jr(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) > = ... Dear Mr Pig, or may I call you Porky? Those three dots hide an induction! > 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. > > TIA. -- I can't go on, I'll go on.
From: David C. Ullrich on 19 Jun 2010 07:09 On Fri, 18 Jun 2010 18:21:26 -0700 (PDT), "porky_pig_jr(a)my-deja.com" <porky_pig_jr(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.
From: David C. Ullrich on 19 Jun 2010 07:17
On Fri, 18 Jun 2010 22:05:35 -0700, William Elliot <marsh(a)rdrop.remove.com> wrote: >On Fri, 18 Jun 2010, porky_pig_jr(a)my-deja.com wrote: > >> 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. > >That's wrong. Use >A1 \/..\/ A_n \/ A_(n+1) = (A1 \/..\/ A_n) \/ A_(n+1). No, there's nothing wrong about it. >> 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. > >Yea, it sucks as a proof. No, it's a perfectly acceptable proof. >> 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. >> >That's not a proof. >It's a recursive expression for calculating P(A1 \/..\/ A_n). > >Are you sure the instructor is a mathematician >and not a computer scientist? This sort of arrogance would be more appropriate if you had a better idea of what is and what is not a valid proof. A strictly formal presentation of something is not nexessarily considered better than a somewhat informal presentation of the same argument. In fact the informal version is ofter preferred, in cases where it's easier to understand. Hint: When you "correct" (A_1 union A_2 union ... union A_{n-1}) union A_n and say it should be (*) 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}". |