mm-3099 === Subject: Re: svd question Correct, matrix A should have m rows. Yes, that's the idea. And since W is the space of the linear combinations of the eigenvalues then every vi is a linear combination of the eigenvalues. I haven't found this in any reference and this is very interesting for me. === Subject: Re: Legendre Polynomials..ineq. You're right - my bad. I tried the line of argument I suggested, but couldn't get it to work. Can I ask how this came up? === Subject: Re: Legendre Polynomials..ineq. Content-Length: 847 Originator: rusin@vesuvius Let h(x):=(x^2-1)^n=(x-1)^n(x+1)^n . Further denote f(x):=(x-1)^n , g(x):=(x+1)^n C(n,k)=n(n-1)...(n-k+1)/k! , k,n in {0,1,...} . Observe that for j in {0,1,...,n} we have (#) ( (x+b)^n )^{(j)} = j!C(n,j)(x+b)^{n-j} . According to Leibniz formula [see also (#)] h^{(n)}(x)= =SUM_{k=0 to k=n}C(n,k)f^{(k)}(x)g^{(n-k)}(x)= =SUM k!(n-k)!C(n,k)C(n,k)C(n,n-k)(x-1)^{n-k}(x+1)^{k}. For x=1 we find [see the last term from the sum] h^{(n)}(1)=n!2^n . But P_n(x)=c_n*[h(x)]^{(n)} and P_n(1)=1 . === Subject: Are inclusions of open subspaces monomorphisms of ringed spaces? Originator: bergv@math.uiuc.edu (Maarten Bergvelt) It is true in the category of schemes that open immersions are monomorphisms, but I can only prove this fact from the fact that for any ring R and any element f in R the localization map Rto R_f is an epimorphism. Can this be proved in general for ringed spaces? More precisely, if I have a ringed space (X,O_X) and an open subspace (U,O_U), where O_U is just the restriction of O_X to U, will the natural inclusion Usubset X be a monomorphism of ringed spaces? Keerthi === Subject: Re: Are inclusions of open subspaces monomorphisms of ringed spaces? Originator: bergv@math.uiuc.edu (Maarten Bergvelt) Hallo, What do you mean by monomorphism? If it's just that open immersions immersion i), this is of course true. One can see this by writing down the definition of a composition of morphisms of ringed spaces and of the (to a topological open immersion) associated morphism of sheaves; but when doing so, one can just as well go on and prove the following uniquely through U. Lukas === Subject: Re: seek advice on optimization of Gram matrix Originator: bergv@math.uiuc.edu (Maarten Bergvelt) First thing, when two of the x_i are equal, your matrix is not positive definite, since it is singular. Second thing, do you have an expression for the charateristic polynomial of K? Or even better, the eigenvalues of K? su_jionglong@hotmail.com a .8ecrit : === Subject: Re: seek advice on optimization of Gram matrix Originator: bergv@math.uiuc.edu (Maarten Bergvelt) First thing, when two of the x_i are equal, your matrix is not positive definite, since it is singular. Second thing, do you have an expression for the charateristic polynomial of K? Or even better, the eigenvalues of K? su_jionglong@hotmail.com a .8ecrit : === Subject: Re: Cumulants and infinite divisibility Originator: bergv@math.uiuc.edu (Maarten Bergvelt) The following is a counterexample. Let X have the density !x|exp(-|x|)/2. Then the moment generating function is (1+t^2)/(1-t^2)^2. It is clear from expanding the logarithm of this that all coefficients of even powers are positive. As to the distribution not being infinitely divisible, a symmetric infinitely divisible distribution must have its mode at the point of symmetry, and it is clear that this distribution does not. -- This address is for information only. I do not claim that these views are those of the Statistics Department or of Purdue University. Herman Rubin, Department of Statistics, Purdue University hrubin@stat.purdue.edu Phone: (765)494-6054 FAX: (765)494-0558 === Subject: Laplacian of weighted graphs Content-Length: 315 Originator: rusin@vesuvius Got a possibly silly question. Given a graph, the Laplacian is the degree matrix minus the adjacency matrix. Does one talk about the Laplacian matrix of a graph where the vertices and edges are labeled, i.e. each vertex and each edge is assigned some number? Any reference === Subject: Re: Laplacian of weighted graphs Originator: tchow@lebesgue.mit.edu.mit.edu (Timothy Chow) Content-Length: 1228 Originator: rusin@vesuvius Weights on the edges are handled in the obvious way: the degree of a vertex is the sum of the weights of the incident edges, and the adjacency matrix is the weighted adjacency matrix. There isn't going to be a reference for this fact other than the usual references for Laplacians (Cvetkovic & Doob's Spectra of Graphs, Biggs's Algebraic Graph Theory, Godsil & Royle's Algebraic Graph Theory, Chung's Spectral Graph Theory, etc.). I'm not aware of any variant of the Laplacian that also takes into account vertex weights. -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences === Subject: Re: Laplacian of weighted graphs Content-Length: 197 Originator: rusin@vesuvius There is one by Fan Chung: www.math.ucsd.edu/~fan/wp/lang.pdf Martin === Subject: Why are there only finitely many Steiner points? Originator: tchow@lebesgue.mit.edu.mit.edu (Timothy Chow) Content-Length: 774 Originator: rusin@vesuvius A few years back, I posted here asking why the maximum number of Steiner points in a minimum (Euclidean) Steiner tree is n - 2, where n is the number of initial points. Gerry Myerson gave a helpful response, pointing me to the work of Melzak. However, I was just looking at this again, and one point that was never quite settled to my satisfaction was the question of why the maximum number of Steiner points is finite. (I buy that *if* the number of points is finite, then it's at most n - 2.) -- Tim Chow tchow-at-alum-dot-mit-dot-edu The range of our projectiles---even ... the artillery---however great, will never exceed four of those miles of which as many thousand separate us from the center of the earth. ---Galileo, Dialogues Concerning Two New Sciences === Subject: The Geddes Series Project: A Vision for the Future Content-Length: 1242 Originator: rusin@vesuvius To mark the end of eleven very fruitful years in residence at the University of Waterloo, I have written a goodbye essay. The title and abstract appear below, along with a link to the full text. The essay describes my long-term research goals and presents my personal vision for the future of the areas of mathematics in which I work. TITLE The Geddes Series Project: A Vision for the Future of Multivariate Real, Complex, and Hypercomplex Analysis ABSTRACT This essay describes my personal research vision, which has evolved and grown over the course of two decades of free inquiry in both mathematics and computing. I will begin by thanking two leading researchers who have played a vital role in nurturing that vision: Keith Geddes (Waterloo) and Bruno Buchberger (RISC-Linz). I will end by inviting researchers in pure, applied, and computational mathematics to join my closest colleagues and myself in a broad, ongoing, interdisciplinary collaboration -- to embark on a new adventure of unfettered exploration, full of promise and possibilities! FULL TEXT http://vision.fwchapman.info/ -- Frederick W. Chapman, Postdoctoral Fellow, University of Waterloo http://www.fwchapman.info/ http://www.geddes-series.info/ === Subject: Re: Series Question > Hey guys need some help on this. > You may have heard the fable about the touroise and > the hare. Suppose that the tortoise and the hare are > running a 5000m race. The tortoise proceeds very > slowly, never changing its speed. The hare runs very > quickly at the start. The tortoise travels 10 m > every minute. The hare travels 2500 m in the first > minute but, in each minute after that, travels only > half of the remaining distance (in the second minute, > the hare travels half of the ramaining 2500 m, and so > on). > a) Write the series for the distance the tortoise > travels for the first few minutes of the race, where > Sn represents the total distance travelled after n > minutes. Each term of the series will represent the > distance the tortoise travels in that minute. > b) Write the series for the distance the hare travels > for the first few minutes of the race, where Sn > represents the total distance travelled after n > minutes. Each term of the series will represent the > distance the hare travels in that minute. > c) Analyze and compare the two series. Include > information such as Sn for both the tortoise and the > hare, and your conclusion as to who will win the > race. Provide Support for your analysis. > Heres what I got so far. > A) says take the first few mins, So do I right it > like > S5 10, 10, 10, 10 ,10 This (the easy part!) is incorrect. Sn is supposed to be the TOTAL distance traveled. The sequence is 10, 20, 30, 40, 50, ..., an arithmetic sequence. > B) S5 2500, 1250, 625, 312. 50, 156.25 2500, 2500+ (1/2)2500, 2500+ (1/2)2500+ (1/4)2500, 2500+ (1/2)2500+ (1/4)2500+ (1/8)2500= 2500(1+ 1/2+ 1/4+ 1/8), ... a geometric series. > C) Tort takes 500 minutes to travel 5000 m which is > obvious. > As for the hare i'm having trouble answering I got > was 1250 minutes to travel the 5000 m A heckuva lot longer than that! === Subject: Re: Series Question >> b) Write the series for the distance the hare travels >> for the first few minutes of the race... >> ...Each term of the series will represent the >> distance the hare travels in that minute. I'll cheat with Mathematica... equ = {d[1] == 2500, d[t] == d[t - 1]/2}; RSolve[equ, d[t], t] {d[t] -> 625*2^(3 - t)} First few distances are: Table[625.*2^(3 - t), {t, 4}] {2500., 1250., 625., 312.5} And the limit at time 't' at infinity... Sum[625*2^(3 - t), {t, 1, Infinity}] 5000 The limit at time infinity is the length of the race...5,000. -- HTH. :>) Dana DeLouis >> Hey guys need some help on this. >> You may have heard the fable about the touroise and >> the hare. Suppose that the tortoise and the hare are >> running a 5000m race. The tortoise proceeds very >> slowly, never changing its speed. The hare runs very >> quickly at the start. The tortoise travels 10 m >> every minute. The hare travels 2500 m in the first >> minute but, in each minute after that, travels only >> half of the remaining distance (in the second minute, >> the hare travels half of the ramaining 2500 m, and so >> on). >> a) Write the series for the distance the tortoise >> travels for the first few minutes of the race, where >> Sn represents the total distance travelled after n >> minutes. Each term of the series will represent the >> distance the tortoise travels in that minute. >> b) Write the series for the distance the hare travels >> for the first few minutes of the race, where Sn >> represents the total distance travelled after n >> minutes. Each term of the series will represent the >> distance the hare travels in that minute. >> c) Analyze and compare the two series. Include >> information such as Sn for both the tortoise and the >> hare, and your conclusion as to who will win the >> race. Provide Support for your analysis. >> Heres what I got so far. >> A) says take the first few mins, So do I right it >> like >> S5 10, 10, 10, 10 ,10 > This (the easy part!) is incorrect. Sn is supposed to be the TOTAL > distance traveled. The sequence is > 10, 20, 30, 40, 50, ..., an arithmetic sequence. >> B) S5 2500, 1250, 625, 312. 50, 156.25 > 2500, 2500+ (1/2)2500, 2500+ (1/2)2500+ (1/4)2500, > 2500+ (1/2)2500+ (1/4)2500+ (1/8)2500= 2500(1+ 1/2+ 1/4+ 1/8), ... a > geometric series. >> C) Tort takes 500 minutes to travel 5000 m which is >> obvious. >> As for the hare i'm having trouble answering I got >> was 1250 minutes to travel the 5000 m > A heckuva lot longer than that! === Subject: Re: Series Question I've been looking at this question. I think one of the issues is calculation \ becomes very small. If I am correct in thinking the ratio (r) is 1/2 or 0.5 \ . If this is the case the number to a high power yeilds a very LOW number. Which makes the 2500 * x to the 0.0000000000000000000000000000000000000000000000000 etc... very very small. \ The calculator returns 0, this is not true but it goes beyond the regular floating point value for the calc I geuss. Knowing this is geometric we calculate this using the series 2500, 1250, 625 ... etc.. where \ t_n = (t_n-1)/2^n and S_n = A + AR + AR^2 + AR^3 +... + AR^n-1 where S_500 = AR^500-1 OR AR^499 sub A = 2500 sub R = 0.5 in AR^499 for value of S_500 S_500 = 2500(0.5^499) 0.5^499 returns error number (0) we know this is not true though. In Sci mode it returns 0E0 using a lower power numbernumber such as 0.5^250 the number is 5.527...^-76 which we know to be very small 0.0000000000000000000000000000000000000000000000000000000 0000000000000005 etc.. something like that. it is unworkable in the calc with current knowledge. suffice to say it is an extremely large number. What we do know is that the \ number is div 2 every time and we are always 1/2 of the last number short. The rabit can 'never' finish, as it becomes infintismally small. (However \ the hare hair 'will' grow. So whatever rate the hare hair is growing at will eventually allow the rabit to finish in a day or so. === Subject: Re: Primer of number theory There is a pdf file on hardy and Wrights book which you can get free. === Subject: Re: JSH: Politics > The faster thing might be if it doesn't work well, > and someone could > prove that quickly. This was proven by a poster in another one of your threads, who computationally compared your method versus random method and fermat's method. === Subject: math tutors handbook A great resource for math teachers, tutors, homeschoolers or studying for standardized test, or personal review! Check out : www.janzia.com you'll love it! === Subject: sequence sum Hi friends, can anyone plz help me out in solving this problem. The problem goes something like this. Derive a formula to find the sum of the following series. sqrt(1)+sqrt(2)+sqrt(3)+sqrt(4)+ - - - - - - - - - - - +sqrt(n) where n>=1 karthik. === Subject: Re: sequence sum > can anyone plz help me out in solving this problem. > The problem goes something like this. > Derive a formula to find the sum of the following series. > sqrt(1)+sqrt(2)+sqrt(3)+sqrt(4)+ - - - - - - - - - - - +sqrt(n) > where n>=1 I don't think there's a simple closed form expression for this sum, but you can use left-endpoint and right-endpoint Riemann sums for y = sqrt(x) with delta(x) = 1 on the interval [0,n] to see that a rough estimate for the sum is n^(3/2). For slightly more details on this, see my post at The Math Forum, AP-Calculus, 19 May 2006 http://mathforum.org/kb/thread.jspa?messageID=4725124 L. Renfro === Subject: Math Tutor's Hand Book This is a great book with simple one page lessons on many math topics. It breaks down what to teach/learn in each grade level. Great for home school, tutors, and/or personal study for standardized tests, \ etc. www.janzia.com === Subject: Nature of proofs by induction (Excuse my ignorance if this is a stupid question. I'm still going through old material in order to get back to the track after a few years pause.) I have noticed some uses of proof by induction which I don't feel comfortable with. Could someone clarify the situation for me? Proofs are done by first prooving property holds at step 0, next we prove that if it holds for n then it does hold for n+1 and we conclude that it holds for all n in N (to provide the skeleton of the technique). Now, take a proof, say: Let [n] = {1,2,...,n} and A a proper subset of [n]. Now for some k < n there exists bijection f:A->[k] Proof. step 0: Clearly this hold for n=0 because [0] does not have proper subsets step n-> n+: Assume claim holds for n and prove it for n+. Let A be a proper subset of [n+] (n+ is the successor of n). Let B be the intersection of A and [n]. If B=[n], then A=B and the claim holds for A and n+ if we choose k=n. Assume B is a proper subset of [n]. By the induction hypothesis there exists k < n and bijection f:b->[k]. If A=B then we have a proof for A. Assume B =/= A. Now A=B union {n+}. Now mapping g:A->[k+], where g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a bijection. Because k < n, then k+ < n+ and hence we have prooved the claim for n+. Now what I have done is i) proved step 0 by noticing [0] does not have proper subsets ii) assumed that if hypothesis holds for n then it holds for n+1 Doesn't the step hypothesis hold for n assume that [n] does not have proper subsets? At least this was the way to prove step 0. Can we use property is not defined at 0 on step n even if property is defined for n? Doesn't the situation change if the property is defined at, say, 1? === Subject: Re: Nature of proofs by induction > (Excuse my ignorance if this is a stupid question. > I'm still going > through old material in order to get back to the > track after a few > years pause.) > I have noticed some uses of proof by induction which > I don't feel > comfortable with. Could someone clarify the situation > for me? > Proofs are done by first prooving property holds at > step 0, next we > prove that if it holds for n then it does hold for > n+1 and we conclude > that it holds for all n in N (to provide the skeleton > of the > technique). > Now, take a proof, say: > Let [n] = {1,2,...,n} and A a proper subset of [n]. > Now for some k < n > there exists bijection f:A->[k] > Proof. > step 0: Clearly this hold for n=0 because [0] does > not have proper > subsets > step n-> n+: Assume claim holds for n and prove it > for n+. Let A be a > proper subset of [n+] (n+ is the successor of n). Let > B be the > intersection of A and [n]. If B=[n], then A=B and the > claim holds for A > and n+ if we choose k=n. > Assume B is a proper subset of [n]. By the induction > hypothesis there > exists k < n and bijection f:b->[k]. If A=B then we > have a proof for A. > Assume B =/= A. Now A=B union {n+}. Now mapping > g:A->[k+], where > g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a > bijection. Because k < > n, then k+ < n+ and hence we have prooved the claim > for n+. > Now what I have done is > i) proved step 0 by noticing [0] does not have > e proper subsets > ii) assumed that if hypothesis holds for n then it > t holds for n+1 > Doesn't the step hypothesis hold for n assume that > [n] does not have > proper subsets? At least this was the way to prove > step 0. > Can we use property is not defined at 0 on step n > even if property is > defined for n? Doesn't the situation change if the > property is defined > at, say, 1? Looks to me like a variation on the horse of a different color paradox: Theorem: In any set of n horses, they must all be of the same color (there is NO horse of a different color!). Proof by induction on n: Let A be a set containing exactly one horse. Clearly all horses in the set are of the same color! Now, assume the statement is true for some n. For a set of n+1 horses. Take one of the horses, call it a, and remove it from the set. The remaining set has n horses and so they are all of the same color. Now, from \ the original set of horses, choose a different horse, call it b, and remove it from the set. Again, since this is a set of n horses, they must \ be all of the same color. But this set now contains a, so a must be of the same color as all the others. Since b was in the orginal set of n when a was removed, it is of the same color as all the other horses. Therefore, all horses in the set of n+1 horses must be of the same color. \ By induction, any set of n horses must have all horses of the same color! Do you see the error? If n+1= 2, when we remove a, we have a set containing only 1 horse. Yes, that consists of a single color. When we remove b we again have just one horse, of one color. But there are no other horses. It does not follow that a and b are of the same color. The argument for going from n to n+1 only works if n is at least 2. \ We can't go from 1 to 2. Does your argument for going from n to n+1 work if n= 0? === Subject: Re: Nature of proofs by induction <3309654.1151771210136.JavaMail.jakarta@nitrogen.mathforum.org Looks to \ me like a variation on the horse of a different color paradox: A variation...maybe, but not exactly the same. > Theorem: In any set of n horses, they must all be of the same color > (there is NO horse of a different color!). <... Do you see the error? Yes. > Does your argument for going from n to n+1 work if n= 0? I tried to express that if we have a fact P on which we base our proof on step 0 then, in my opinion, that fact P has to hold for all n or the proof fails. If from the fact P we reduce that f(0) holds and P is false at other f(n), n > 0, is it safe to assume f(n) holds? Apparently it is but I don't see why... Anyway, I'm off for vacation now :) === Subject: Re: Nature of proofs by induction On 1 Jul 2006 10:19:24 -0700, un student in alt.math.undergrad: [...] > If from the fact P we [d]educe that f(0) holds and P is false at other > f(n), n > 0, is it safe to assume f(n) holds? Sure, because it's a conditional assumption. You're not in fact asserting that f(n) holds. You're temporarily assuming this to see what consequences it would have. In particular, you want to know that f(n+1) is one of those consequences. To put it a bit differently, you're proving f(n) --> f(n+1); the most straightforward way to do this is to assume for the sake of argument that f(n) is true, and try to deduce f(n+1). If you succeed, you've proved f(n) --> f(n+1), but you still have no idea whether f(n) is actually true or not. [...] Brian === Subject: Re: Nature of proofs by induction On 1 Jul 2006 00:59:54 -0700, un student through old material in order to get back to the track after a few >years pause.) >I have noticed some uses of proof by induction which I don't feel >comfortable with. Could someone clarify the situation for me? >Proofs are done by first prooving property holds at step 0, next we >prove that if it holds for n then it does hold for n+1 and we conclude >that it holds for all n in N (to provide the skeleton of the >technique). >Now, take a proof, say: >Let [n] = {1,2,...,n} and A a proper subset of [n]. Now for some k < n >there exists bijection f:A->[k] >Proof. >step 0: Clearly this hold for n=0 because [0] does not have proper >subsets >step n-> n+: Assume claim holds for n and prove it for n+. Let A be a >proper subset of [n+] (n+ is the successor of n). Let B be the >intersection of A and [n]. If B=[n], then A=B and the claim holds for A >and n+ if we choose k=n. >Assume B is a proper subset of [n]. By the induction hypothesis there >exists k < n and bijection f:b->[k]. If A=B then we have a proof for A. >Assume B =/= A. Now A=B union {n+}. Now mapping g:A->[k+], where >g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a bijection. Because k < >n, then k+ < n+ and hence we have prooved the claim for n+. >Now what I have done is > i) proved step 0 by noticing [0] does not have proper subsets > ii) assumed that if hypothesis holds for n then it holds for n+1 >Doesn't the step hypothesis hold for n assume that [n] does not have >proper subsets? At least this was the way to prove step 0. No. You proved that every proper subset of the empty set has the required property. The fact that the empty set has no proper subsets doesn't change that - the details of _how_ you proved it doesn't change that. >Can we use property is not defined at 0 on step n even if property is >defined for n? Doesn't the situation change if the property is defined >at, say, 1? Don't know what you mean. The property _is_ defined when n = 0. ************************ David C. Ullrich === Subject: Re: Nature of proofs by induction Now what I have done is > i) proved step 0 by noticing [0] does not have proper subsets > ii) assumed that if hypothesis holds for n then it holds for n+1 >Doesn't the step hypothesis hold for n assume that [n] does not have >proper subsets? At least this was the way to prove step 0. > No. You proved that every proper subset of the empty set has the > required property. The fact that the empty set has no proper > subsets doesn't change that - the details of _how_ you proved > it doesn't change that. Ah, yes, the techique still works. I didn't see that. >Can we use property is not defined at 0 on step n even if property is >defined for n? Doesn't the situation change if the property is defined >at, say, 1? > Don't know what you mean. The property _is_ defined when n = 0. I was not precise enough. Actually I ment that on proof by induction one first proves that property holds at some point i and then uses this information to prove that if the property holds at n >= i, then it holds in n+1. Now, if we prove that the property in question holds in i using a fact P which only holds in i but no for any m > i, don't we later, when assuming property holds in n, assume that P holds as well? Uhh. This is hard to explain (as misunderstandings, which I seem to have quite a bunch, usually are). Is my text understable? === Subject: Re: Nature of proofs by induction On 1 Jul 2006 04:03:50 -0700, un student Now what I \ have done is > i) proved step 0 by noticing [0] does not have proper subsets > ii) assumed that if hypothesis holds for n then it holds for n+1 >Doesn't the step hypothesis hold for n assume that [n] does not have >proper subsets? At least this was the way to prove step 0. >> No. You proved that every proper subset of the empty set has the >> required property. The fact that the empty set has no proper >> subsets doesn't change that - the details of _how_ you proved >> it doesn't change that. >Ah, yes, the techique still works. I didn't see that. >Can we use property is not defined at 0 on step n even if property is >defined for n? Doesn't the situation change if the property is defined >at, say, 1? >> Don't know what you mean. The property _is_ defined when n = 0. >I was not precise enough. Actually I ment that on proof by induction >one first proves that property holds at some point i and then uses this >information to prove that if the property holds at n >= i, then it >holds in n+1. Now, if we prove that the property in question holds in i >using a fact P which only holds in i but no for any m > i, don't we >later, when assuming property holds in n, assume that P holds as well? >Uhh. This is hard to explain (as misunderstandings, which I seem to >have quite a bunch, usually are). Is my text understable? Yes, your question is understandable. It's already been answered several times, including once by me! You should try understanding the replies instead of repeating the question: If you prove that the property holds when n = 0 and then show that it holds at n + 1 assuming it holds at n then you're done. Details about _how_ you proved it holds at n = 0 are irrelevant. ************************ David C. Ullrich === Subject: Re: Nature of proofs by induction On 1 Jul 2006 04:03:50 -0700, un student alt.math.undergrad: [...] > I was not precise enough. Actually I ment that on proof by induction > one first proves that property holds at some point i and then uses this > information to prove that if the property holds at n >= i, then it > holds in n+1. No: the two parts of a proof by induction are completely independent. It is entirely possible to prove *first* that if the property holds at some n >= i, then it also holds at n + 1. In fact, it's easy to find examples in which it's possible to prove this even though the property *doesn't* hold at i. As an example, consider the following property P(n). P(n): 0 + 1 + 2 + 3 + ... + n = (n^2 + n + 1)/2 Suppose that P(k) is true for some particular k >= 0. Then 0 + 1 + ... + k + (k+1) = [0 + 1 + ... + k] + (k+1) = (k^2 + k + 1)/2 + k + 1 (because P(k) is true), and by elementary algebra (k^2 + k + 1)/2 + k + 1 = (k^2 + 3k + 3)/2 = [(k+1)^2 + (k+1) + 1]/2, i.e., P(k+1) is true. In other words, P(k) implies P(k+1), which is exactly what one needs to show in the induction step. But P(0) is easily seen to be false, since 0 != 0^2 + 0 + 1. In fact, P(n) is easily seen to be false for *all* n. Note first that n^2 + n + 1 = n(n + 1) + 1. Now n and n + 1 are consecutive integers, so one of them is even, and therefore the product n(n + 1) is even, n(n + 1) + 1 is odd, and (n^2 + n + 1)/2 = [n(n + 1) + 1]/2 isn't an integer. But the sum 0 + 1 + ... + n obviously is an integer. > Now, if we prove that the property in question holds in i > using a fact P which only holds in i but no for any m i, don't we later, \ when assuming property holds in n, > assume that P holds as well? No. Once again, the two parts of the proof are completely independent of each other. [...] Brian === Subject: Re: Nature of proofs by induction On 1 Jul 2006 00:59:54 -0700, un student in alt.math.undergrad: [...] > I have noticed some uses of proof by induction which I don't feel > comfortable with. Could someone clarify the situation for me? > Proofs are done by first prooving property holds at step 0, next we > prove that if it holds for n then it does hold for n+1 and we conclude > that it holds for all n in N (to provide the skeleton of the > technique). This is one kind of proof by induction; there are others. > Now, take a proof, say: > Let [n] = {1,2,...,n} and A a proper subset of [n]. Now for some k < n > there exists bijection f:A->[k] > Proof. > step 0: Clearly this hold for n=0 because [0] does not have proper > subsets > step n-> n+: Assume claim holds for n and prove it for n+. Let A be a > proper subset of [n+] (n+ is the successor of n). Let B be the > intersection of A and [n]. If B=[n], then A=B and the claim holds for A > and n+ if we choose k=n. And the specific bijection from A to [n] is the identity map. > Assume B is a proper subset of [n]. By the induction hypothesis there > exists k < n and bijection f:b->[k]. If A=B then we have a proof for A. > Assume B =/= A. Now A=B union {n+}. Now mapping g:A->[k+], where > g(i)=f(i) for every i =/= n+ and g(n+) = k+ is a bijection. Because k < > n, then k+ < n+ and hence we have prooved the claim for n+. By showing how to construct the desired bijection for any given proper subset of [n+]. > Now what I have done is > i) proved step 0 by noticing [0] does not have proper subsets > ii) assumed that if hypothesis holds for n then it holds for n+1 No, absolutely not. You have *proved* that if it holds for n, then it holds for n+1, which is a completely different thing. > Doesn't the step hypothesis hold for n assume that [n] does not have > proper subsets? No, not in the least. The assumption that the hypothesis holds for [n] is this, if written out in full: If A is a proper subset of [n], then for some natural number k < n there is a bijection f : A -> [k]. There is nothing there about whether or not [n] has proper subsets. Of course when n > 0 it always does. > At least this was the way to prove step 0. But 0 is a very special case. > Can we use property is not defined at 0 ??? The property *is* defined at 0, and what's more, 0 has it: 'if A is a proper subset of [0], then for some natural number k < 0 there is a bijection f : A -> [k]' is a true statement. Admittedly, it's true for the trivial reason that [0] has no proper subsets, but it's still true. (It's a statement of the form 'if P then Q', and such a statement is automatically true when P is false.) > on step n even if property is defined for n? Doesn't the > situation change if the property is defined at, say, 1? I don't see where you're getting this: nothing in the proof of (ii) is based on an assumption that [n] has no proper subsets. Brian === Subject: Re: Nature of proofs by induction <1rp757bmwol70$.32wvg3ph33ly.dlg@40tude.net On 1 Jul 2006 00:59:54 -0700, \ un student > Now what I have done is > i) proved step 0 by noticing [0] does not have proper subsets > ii) assumed that if hypothesis holds for n then it holds for n+1 > No, absolutely not. You have *proved* that if it holds for > n, then it holds for n+1, which is a completely different > thing. Yes, this is what I ment. A massive typo. <... > At least this was the way to prove step 0. > But 0 is a very special case. Yes, I see that :) <.. The property *is* defined at 0, and what's more, 0 has it: > 'if A is a proper subset of [0], then for some natural > number k < 0 there is a bijection f : A -> [k]' is a true > statement. Admittedly, it's true for the trivial reason > that [0] has no proper subsets, but it's still true. (It's > a statement of the form 'if P then Q', and such a statement > is automatically true when P is false.) Ok, I think I'm getting it. What I saw in the proof was something like: Let f be function f(n) = n+1 for all n > 0, n in N, and f is not defined at 0. Lemma: f is not defined anywhere Proof. (which is incorrect) step 0: clearly f is not defined at 0 step n->n+1: by induction hypothesis f is not defined at n. But now f(n) = f(n-1)+1 -> f(n+)=f(n)+1 but since f is not defined at n it can't be defined on n+ neither and hence f is not defined anywhere. Here I explicitly used the not defined when in the previous proof it was used implicitly. I mean, that step 0 was proved by showing A is false (no proper subsets) and showing that now property B follows N=A->B because anything follows from false. Now if written out explicitly. A=[0] has a proper subset B=Bijection f exists Because A is false then A->B is true. Let N=A->B, which is true. Now step n->n+ uses (actually no, but this is how I thought) N to prove the case for n+. Here C=[n] has a proper subset D=Bijection exists M=C->D Now we have to proof N->M is true, ie L=(A->B) -> (C->D) is true, correct? Now if n=0, then A->B is same as C->D and hence L is true. If n>0, then A->B is (still) true and C is true. Now it remains to be shown that from C one gets D. If the above reasoning is correct I got it. Looks like I thought A=C, but actually that is true only when n=0. And if n=0 then C=D and L is naturally true. One could say that A and B are constants, but C and D are functions of n and C(0)=A, D(0)=B :) Ok, maybe now... === Subject: Nature of a certian Ideal consider the Ideal I={set of all continous functions form R to R vanishing at 'a' , a fixed point } in the ring of continous functions form R to R. with addition and multiplication being point wise. R= set of real numbers Is I principal? === Subject: Re: Nature of a certian Ideal On Sun, 02 Jul 2006 10:25:11 EDT, koltesagar I={set of all continous functions form R to R vanishing at 'a' , a fixed point } >in the ring of continous functions form R to R. with addition and multiplication being point wise. >R= set of real numbers >Is I principal? No. If g is in I (and g is non-zero except at a) then there exists f in I such that f/g -> infinity at a, hence f is not in the ideal generated by g. ************************ David C. Ullrich === Subject: Re: Nature of a certian Ideal <8974198.1151853700195.JavaMail.jakarta@nitrogen.mathforum.org>, > consider the Ideal > I={set of all continous functions form R to R vanishing at 'a' , a fixed > point } > in the ring of continous functions form R to R. with addition and > multiplication being point wise. > R= set of real numbers > Is I principal? One would have to have some fixed function f:R --> R with f in I so that for every g in I, g = h*f for some h in the ring. But for every such g, one would have to have that g/f must have a finite limit as x --> a. Consider g = real cube root of f,so g will be in I whenever f is in I. What is lim_{x --> a} g(x)/f(x) like? === Subject: Re: Nature of a certian Ideal > consider the Ideal > I={set of all continous functions form R to R vanishing at 'a' , a fixed > point } I = { f in C(R,R) | f(a) = 0 } > in the ring of continous functions form R to R. with addition and > multiplication being point wise. > R= set of real numbers > Is I principal? Some g with for all f, f(a) = 0 iff some h in C(R,R) with f = g*h ? No. Notice g(a) = 0, sqr g in I. some h with sqr g = g * h h = (sqr g)/g is not continuous. === Subject: FTCE - Middle School Math Hi all, I am looking for some advice and guidance on how to better prepare and pass the Math SAe for the FTCE grades 5-9. I have purchased the study guide suggested on the back of the booklet of the FTCE information book and the FTCE book of secrets, but I feel that there is something that I am missing just not sure of what it might be; therefore if there is someone out there that has the answer or some good advice please hit me up. I take the test on July 22nd and really need to pass the test. === Subject: Where can i find problems in relations and equivalence relations? I am looking for problems with answers regarding relations and equivalence Relations. for example a good question can be: Is there a relation which is reflexive symetric and antisymmetric Btw my strategy to solve such problems is to write the definition and using operation on sets and de morgan law to simplify it..is this a good method? === Subject: Re: Where can i find problems in relations and equivalence relations? > I am looking for problems with answers regarding relations and > equivalence Relations. Relations or binary relations? For the later, read about order theory and they'll pop up all over the place. > for example a good question can be: > Is there a relation which is reflexive symmetric and antisymmetric Good question, got any others? Anyway yes, give an example. If a relation is symmetric and anti-symmetric, show it's reflexive. Anti-symmetric is a <= b, b <= a -> a = b tho some call that asymmetric, using the former for not(a <= b, b <= a). > Btw my strategy to solve such problems is to write the definition and > using operation on sets and de morgan law to simplify it..is this a good > method? DeMorgan laws are good to know and use. In addition, you'll likely develop other techniques. === Subject: Re: Where can i find problems in relations and equivalence relations? > I am looking for problems with answers regarding > relations and > equivalence Relations. > Relations or binary relations? For the later, read > about > order theory and they'll pop up all over the place. > for example a good question can be: > Is there a relation which is reflexive symmetric > and antisymmetric > Good question, got any others? Anyway yes, give an > example. > If a relation is symmetric and anti-symmetric, show > it's reflexive. > Anti-symmetric is a <= b, b <= a -> a = b > tho some call that asymmetric, using the former for > not(a <= b, b <= a). > Btw my strategy to solve such problems is to write > the definition and > using operation on sets and de morgan law to > simplify it..is this a good > method? > DeMorgan laws are good to know and use. In addition, > you'll likely > develop other techniques. And writing out PRECISE definitions is always a good idea! === Subject: Please explain the empty relation 1.What exactly is an empty relation? (no one in relation with other,or a relation on empty set?) 2.Why is it both symetric and anti symetric according to the definition of symetric and anti symetric === Subject: Re: Please explain the empty relation days. My association with the Department is that of an alumnus. >1.What exactly is an empty relation? > (no one in relation with other,or a relation on empty set?) A relation between two sets A and B is a subset of A x B. One such subset is the empty set. This is called the empty relation. In the empty relation, no element of the first set, A, is in the relation with any element of the second set, B. When A or B are themselves empty, the only possible relation from A to B is the empty relation. >2.Why is it both symetric and anti symetric according to the definition >of symetric and anti symetric For the relation to be symmetric and/or anti-symmetric, it must be a relation from a set to itself (the concept is only defined in that context). As such, we are assuming A = B. That said, the definition says: in order for the relation R to be symmtric, it is necessary that every time you have a pair (x,y) in R, the corresponding pair (y,x) musty also be in R. This is true for the empty relation, because the antecedent of the implication is never true. An implication is always true when the antecedent is false. Viewed another way: in order for the empty relation not to be symmetric, it is necessary that there be elements x and y in A for which the pair (x,y) is in R, but the pair (y,x) is not in R. This can never happen in the empty relation, because you can never find a pair of elements x and y in A for which (x,y) is in R, and you can forget the second clause. (This may be because A is empty, in which case R is necessarily empty; or it could be because R is empty, whether or not A is empty). The same argument works for anti-symmetry. Anti-symmetry requires that for all elements x and y in A, if both (x,y) and (y,x) are elements of R, then x must be equal to y. Since the antecedent of the implication is always false for the empty relation, the implication itself is always true and so R is anti-symmetric. -- It's not denial. I'm just very selective about what I accept as reality. --- Calvin (Calvin and Hobbes) Arturo Magidin magidin@math.berkeley.edu === Subject: Re: Please explain the empty relation > 1.What exactly is an empty relation? > (no one in relation with other,or a relation on > on empty set?) > 2.Why is it both symetric and anti symetric according > to the definition > of symetric and anti symetric I'm going to give a slightly different answer than William Elliot (using a \ variant definition of relation). A relation on a set, A, is a set of ordered pairs of elements of A. An empty relation then, would be the empty \ set. Using the definition of relation William Elliot is (a rule linking two things- something like x is related to y if and only if x- y= 6), my set of ordered pairs would contain (x,y) if and only if the rule is true. That's why he says the empty relation corresponds to always false. The definition of symmetric for a relation, using my definition of relation, is if (x,y) is in the set, then (y,x) is also. For the empty set, since (x,y) is in the set is never true, the statement is vacuously true. The definition of anti-symmetric for a relation is if (x,y) is in the set, then (y,x) is NOT in the set. Again, this is vacuously true. Vacuously true: The implication statement P implies Q or if P then Q is TRUE by definition if P is FALSE. === Subject: Re: Please explain the empty relation > 1.What exactly is an empty relation? > (no one in relation with other,or a relation on empty set?) One that is always false. > 2.Why is it both symetric and anti symetric according to the definition > of symetric and anti symetric Those definitions apply only to binary relations and as they are of the form for all a,b, if aRb, then ... Since aRb is false, the ... can be anything, even: Bush is intelligent.