I need some proof...
-
Vikram Punathambekar wrote: What in tarnation does the fourth line mean? The x < n^(1/2) <=> y > n^(1/2) is to sided - two separate proofs needed. => means we prove first direction - if x < n^(1/2) then y > n^(1/2). Vikram Punathambekar wrote: The fifth line in your post says "by contradiction". Contradiction of what? Assuming by contradiction is standard proof technique - you assume something wrong and contradict the assumption, thus the opposite of it is correct. The technique sometimes worded also: by way of contradiction assume that, or assuming the contrary. Vikram Punathambekar wrote: Could you give me a more coherent proof, please? The proof is formal and very mathy - minimal words:) I'll try to humanize it later.
Felix Gartsman wrote: Assuming by contradiction is standard proof technique - you assume something wrong and contradict the assumption, thus the opposite of it is correct. Well, I know that :-O , sorry if I sounded silly. But proof by contradiction goes like this. You're supposed to prove a statement S. You assume S is not true. Then you derive something from !S (or ~S to the more mathematical mind) that is clearly false. Now you say "this is 'cos we made a mistake in assuming !S to be true- so, S must be true". I repeat (maybe in ignorance): in the fifth line, you simply state
y<sqrt(n)which assumption does it contradict? The only assumption you've made so far is thatx<sqrt(n). I can't see how this assumption directly contradicts the statement in the fifth line. Please explain. BTW, do you think the proof I gave in my original post is accpetable? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design. -
Felix Gartsman wrote: Assuming by contradiction is standard proof technique - you assume something wrong and contradict the assumption, thus the opposite of it is correct. Well, I know that :-O , sorry if I sounded silly. But proof by contradiction goes like this. You're supposed to prove a statement S. You assume S is not true. Then you derive something from !S (or ~S to the more mathematical mind) that is clearly false. Now you say "this is 'cos we made a mistake in assuming !S to be true- so, S must be true". I repeat (maybe in ignorance): in the fifth line, you simply state
y<sqrt(n)which assumption does it contradict? The only assumption you've made so far is thatx<sqrt(n). I can't see how this assumption directly contradicts the statement in the fifth line. Please explain. BTW, do you think the proof I gave in my original post is accpetable? Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.Vikram Punathambekar wrote: repeat (maybe in ignorance): in the fifth line, you simply state y<sqrt(n) which assumption does it contradict? It is the false assumption. We assume as fact that x<sqrt(n) and contradictury assume that y<sqrt(n). Then we show that those assumptions (together with xy=n) contradict each other, and since only y<sqrt(n) is additional assumption not from question it must be false. Vikram Punathambekar wrote: BTW, do you think the proof I gave in my original post is accpetable? I'll answer separatelly so I could quote.
-
WARNING: Math post! Hi, fellas! Well, this isn't a programming question, but I wasn't sure where to post it. If it doesn't belong to the Lounge, simply tell me where to go ( Hell? ). I'm trying to prove this statement for my upcoming (and first) article at CP: If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) This is two-way implication- if x is less than sqrt(n), y must be greater than sqrt(n) and vice versa. Yes, I know it's true, but a fromal proof eludes me :-O . It's possible to show it on a graph- the curve xy=n is a rectangular hyperbola (whose general eqn is xy=c^2). The 45-degree line x=y intersects this curve at x=y=sqrt(n). Forget about negative values. Looking at the figure, it's clear that for every point (x1,y1) on the curve xy=n, either x1 or y1 will lie to the left/above of the straight line while the other value lies to the right/below it. NOTE: I can prove using DC that the sum of the two factors of n is minimum when they are identical, i.e., x=y=sqrt(n). But I don't know how that can help. Can this be accepted as a "formal" proof:
Let x and y be factors of n such that xy=n ----- (1) Assume that x<sqrt(n) and y<sqrt(n). Therefore, we have x+c=sqrt(n) ----------- (2) and y+d=sqrt(n) ----------- (3) where c,d>0 . We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=0 Since we have x,y>0, the only possibility is c=d=0, which is contradictory to our assumption that c,d>0. Hence we must be wrong in assuming that x<sqrt(n) and y>sqrt(n) if xy=n. A similar proof can be given where x,y>sqrt(n).Do you think this proof stands up? Are you convinced? Any holes in it? Can anybody give me a better proof (I'm sure there must be a more formal proof). Yep, I'll inlcude ya name in the credits section of my article :-D . Thanx and regards, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.Vikram Punathambekar wrote: Let x and y be factors of n such that xy=n ----- (1) Assume that x0 . Why you assume this? What if x=n,y=1? Although it's minor end cases, you wanted formality. Why y+d=sqrt(n), d>0? Did you mean x,y<sqrt(n)? If so you must contradictury assume y<=sqrt(n) and then d can be zero! Vikram Punathambekar wrote: We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=n From previous, d=0 and c=x and no contradiction. You didn't correctly made ~(y>sqrt(n)).
-
If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) Say: f(n) = x - n^(1/2) and g(n) = y - n^(1/2), now we need to prove f(n) < g(n) for all n > 0. But we know f(n) = x + y - n^(1/2) - y and then f(n) = x - y - g(n), so f(n) + g(n) = x - y, which is independant of n. Thus we can declare n constant, but i wont. This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1. Now with induction, rewrite f(n) as f(x) = x- n^(1/2), and g(n) as g(y) = y - n^(1/2). Now prove f(1) < g(n/1): 1 - n^(1/2) < n/1 - n^(1/2) ===> 1 < n/1 thus TRUE for n > 1 Now assume f(k) < g(n/k) TRUE, and prove f(k + 1) < g(n/(k + 1)): So from induction assumption (k + 1) - n^(1/2) < n/(k + 1) - n^(1/2) k + 1 < n/(k + 1) So for k + 1 < 0 ===> 1 > n and is not allowed. For k + 1 > 0 ===> 1 < n thus TRUE. So we can similarly show the reverse is true for values of 0 < n < 1 where f(x) > g(y). This shows that If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) PS: I hope this is the proper formal way. I'll ask my lecturer on Tuesday :) I rated this article 2 by mistake. It deserves more. I wanted to get to the second page... - vjedlicka 3:33 25 Nov '02
leppie wrote: PS: I hope this is the proper formal way. I'll ask my lecturer on Tuesday It is formal, but I don't see how it proves what you need (I'm before breakfast, so I might missed it). x,y,n are constants and you treat them as parameters, you don't use xy=n or x<sqrt(n).
-
If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) Say: f(n) = x - n^(1/2) and g(n) = y - n^(1/2), now we need to prove f(n) < g(n) for all n > 0. But we know f(n) = x + y - n^(1/2) - y and then f(n) = x - y - g(n), so f(n) + g(n) = x - y, which is independant of n. Thus we can declare n constant, but i wont. This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1. Now with induction, rewrite f(n) as f(x) = x- n^(1/2), and g(n) as g(y) = y - n^(1/2). Now prove f(1) < g(n/1): 1 - n^(1/2) < n/1 - n^(1/2) ===> 1 < n/1 thus TRUE for n > 1 Now assume f(k) < g(n/k) TRUE, and prove f(k + 1) < g(n/(k + 1)): So from induction assumption (k + 1) - n^(1/2) < n/(k + 1) - n^(1/2) k + 1 < n/(k + 1) So for k + 1 < 0 ===> 1 > n and is not allowed. For k + 1 > 0 ===> 1 < n thus TRUE. So we can similarly show the reverse is true for values of 0 < n < 1 where f(x) > g(y). This shows that If n is a positive integer & x and y are two positive numbers such that xy=n, then x < n^(1/2) <=> y > n^(1/2) PS: I hope this is the proper formal way. I'll ask my lecturer on Tuesday :) I rated this article 2 by mistake. It deserves more. I wanted to get to the second page... - vjedlicka 3:33 25 Nov '02
Hey, Leppie! Your "proof" seems brilliant and absurd at the same time (sorry, no offense meant). I've outlined a few issues with your proof, all of which have to be analyzed independantly: #1 You say f(n)=x-sqrt(n) and g(n)=y-sqrt(n). Err...why do you say we have to prove f(n)<g(n) ? Where does that lead us? For all you know, this statement might be right yet both of them could be less than sqrt(n). And what if they are both equal, as in the case of x=y=3,n=9? #2 Glaring error in the very next step. You say f(n)=x+y-sqrt(n)+y. Correct. The next step is wrong. You write f(n)=x-y-g(n), while it should actually be f(n)=x-y+g(n). Therefore, f(n)-g(n)=x-y and not f(n)+g(n)=x-y. #3 Whaddaya mean by saying "We can declare n constant" ? #4 From issue #2, it follows that the statement "This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1." is ^probably^ wrong too. The stuff coming after this is correct, as far as I can see. So you have successfully proved that f(n)<g(n), that is, x-sqrt(n) < y-sqrt(n) . From this, it's obvious that x<y. SO WHAT? You have tied up only x and y. There is absolutely no mention of sqrt(n) here. IMPORTANT: I really appreciate your help in this matter, helping somebody you've never seen or don't even know well. If in the above post I sound ungrateful anywhere, please note that I did not mean to do so. I still would like you to give me a more solid proof, if possible, with your lecturer's help. All the same, please check out the proof that I have given in the original post. The thread link is http://www.codeproject.com/lounge.asp?msg=483741&mode=all&userid=55714#xx483741xx . Don't check the one that was delivered to you by mail. It contains a few small errors that have been changed now. You see, it is simple and straightforward IMHO, but I don't know if it can be accepted by a bunch of nerdy mathematicians. Thanx for your help, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Hey, Leppie! Your "proof" seems brilliant and absurd at the same time (sorry, no offense meant). I've outlined a few issues with your proof, all of which have to be analyzed independantly: #1 You say f(n)=x-sqrt(n) and g(n)=y-sqrt(n). Err...why do you say we have to prove f(n)<g(n) ? Where does that lead us? For all you know, this statement might be right yet both of them could be less than sqrt(n). And what if they are both equal, as in the case of x=y=3,n=9? #2 Glaring error in the very next step. You say f(n)=x+y-sqrt(n)+y. Correct. The next step is wrong. You write f(n)=x-y-g(n), while it should actually be f(n)=x-y+g(n). Therefore, f(n)-g(n)=x-y and not f(n)+g(n)=x-y. #3 Whaddaya mean by saying "We can declare n constant" ? #4 From issue #2, it follows that the statement "This will tell us that when f(n) + g(n) = 0 , n has a root, from below you can see this is 1." is ^probably^ wrong too. The stuff coming after this is correct, as far as I can see. So you have successfully proved that f(n)<g(n), that is, x-sqrt(n) < y-sqrt(n) . From this, it's obvious that x<y. SO WHAT? You have tied up only x and y. There is absolutely no mention of sqrt(n) here. IMPORTANT: I really appreciate your help in this matter, helping somebody you've never seen or don't even know well. If in the above post I sound ungrateful anywhere, please note that I did not mean to do so. I still would like you to give me a more solid proof, if possible, with your lecturer's help. All the same, please check out the proof that I have given in the original post. The thread link is http://www.codeproject.com/lounge.asp?msg=483741&mode=all&userid=55714#xx483741xx . Don't check the one that was delivered to you by mail. It contains a few small errors that have been changed now. You see, it is simple and straightforward IMHO, but I don't know if it can be accepted by a bunch of nerdy mathematicians. Thanx for your help, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
Vikram Punathambekar wrote: Your "proof" seems brilliant and absurd at the same time I have found my new sig :) I thought about it again after I posted it, and realised there are some holes. This time i'll do it on paper instead on keyboard. :) But I'll ask him tomorrow morning and post the findings tomorrow night, or later tonite if I get a proper proof. Later then :) Hey leppie! Your "proof" seems brilliant and absurd at the same time - Vikram Punathambekar 28 Apr '03
-
Vikram Punathambekar wrote: repeat (maybe in ignorance): in the fifth line, you simply state y<sqrt(n) which assumption does it contradict? It is the false assumption. We assume as fact that x<sqrt(n) and contradictury assume that y<sqrt(n). Then we show that those assumptions (together with xy=n) contradict each other, and since only y<sqrt(n) is additional assumption not from question it must be false. Vikram Punathambekar wrote: BTW, do you think the proof I gave in my original post is accpetable? I'll answer separatelly so I could quote.
Your post is all mixed up, undoubtedly due to using < improperly. Please repost so I can understand. Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Vikram Punathambekar wrote: Let x and y be factors of n such that xy=n ----- (1) Assume that x0 . Why you assume this? What if x=n,y=1? Although it's minor end cases, you wanted formality. Why y+d=sqrt(n), d>0? Did you mean x,y<sqrt(n)? If so you must contradictury assume y<=sqrt(n) and then d can be zero! Vikram Punathambekar wrote: We have sqrt(n) * sqrt(n) = n (x+c)(y+d)=n [from (2) and (3)] xy+dx+cy+cd=n n+dx+cy+cd=n [from (1)] dx+cy+cd=n From previous, d=0 and c=x and no contradiction. You didn't correctly made ~(y>sqrt(n)).
Well, I had realized that my original proof had a few typos. I have corrected them now. You should be able to see them at http://www.codeproject.com/lounge.asp?msg=483741&mode=all&userid=55714#xx483741xx Sorry for the trouble... and thanks for your help :-D Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Vikram Punathambekar wrote: Your "proof" seems brilliant and absurd at the same time I have found my new sig :) I thought about it again after I posted it, and realised there are some holes. This time i'll do it on paper instead on keyboard. :) But I'll ask him tomorrow morning and post the findings tomorrow night, or later tonite if I get a proper proof. Later then :) Hey leppie! Your "proof" seems brilliant and absurd at the same time - Vikram Punathambekar 28 Apr '03
leppie wrote: I have found my new sig At last! I was thinking I'd never get quoted. Now my wish has come true. I can die in peace...but wait! Before that I want that proof! :-D leppie wrote: This time i'll do it on paper Just what I was about to suggest. Do it on paper, scan it and email it to me. You can reach me at binarybandit@operamail.com (talk about redundancy, it's there in the mail header, I'll bet). Thanks (for the help and quoting me ;) ), Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
leppie wrote: I have found my new sig At last! I was thinking I'd never get quoted. Now my wish has come true. I can die in peace...but wait! Before that I want that proof! :-D leppie wrote: This time i'll do it on paper Just what I was about to suggest. Do it on paper, scan it and email it to me. You can reach me at binarybandit@operamail.com (talk about redundancy, it's there in the mail header, I'll bet). Thanks (for the help and quoting me ;) ), Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
Vikram Punathambekar wrote: Do it on paper, scan it and email it to me. No scanner :( But here is what I would say sufficient proof. Show for 2 postive numbers x, y that when n = xy x < n^(1/2) <==> n^(1/2) < y Lets assume the assumption is correct, then x < n^(1/2) < y , and from that follows x < y Now work back to where we started. x < y <==> x < y ...(only a fool would not believe this) x^2 < xy <==> xy < y^2 ...(x > 0, y > 0) x^2 < n <==> n < y^2 ...(n = xy given) x < n^(1/2) <==> n^(1/2) < y ...(n > 0 as n = xy, x > 0, y > 0) Thus it proofs that Given 2 postive numbers x, y that when n = xy x < n^(1/2) <==> n^(1/2) < y PS: This appears to be proof enouhg from my PoV :) Hey leppie! Your "proof" seems brilliant and absurd at the same time. - Vikram Punathambekar 28 Apr '03
-
Your post is all mixed up, undoubtedly due to using < improperly. Please repost so I can understand. Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
I modified it to show properly.
-
Vikram Punathambekar wrote: Do it on paper, scan it and email it to me. No scanner :( But here is what I would say sufficient proof. Show for 2 postive numbers x, y that when n = xy x < n^(1/2) <==> n^(1/2) < y Lets assume the assumption is correct, then x < n^(1/2) < y , and from that follows x < y Now work back to where we started. x < y <==> x < y ...(only a fool would not believe this) x^2 < xy <==> xy < y^2 ...(x > 0, y > 0) x^2 < n <==> n < y^2 ...(n = xy given) x < n^(1/2) <==> n^(1/2) < y ...(n > 0 as n = xy, x > 0, y > 0) Thus it proofs that Given 2 postive numbers x, y that when n = xy x < n^(1/2) <==> n^(1/2) < y PS: This appears to be proof enouhg from my PoV :) Hey leppie! Your "proof" seems brilliant and absurd at the same time. - Vikram Punathambekar 28 Apr '03
Sorry, leppie! This time your proof is only absurd. Sorry. If you will see correctly, you will notice that you are assuming what is to be proved as true and using that, you get the result. This CANNOT be accepted as proof at all. There is even a term for this thing- assuming the statement to be proved to be true and using this to get the result. I forgot what it is. :-O I'll be going to college tomorrow (err...today, it's way past 12:00) and I'll ask my Math staff for a proof. It's doubtful, given that tomorrow's my last exam, but I'll hope for the best. leppie wrote: This appears to be proof enouhg from my PoV What/Who is PoV? BTW, what's your real name? And the link in your bio is phony. :suss: Thanx, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
-
Sorry, leppie! This time your proof is only absurd. Sorry. If you will see correctly, you will notice that you are assuming what is to be proved as true and using that, you get the result. This CANNOT be accepted as proof at all. There is even a term for this thing- assuming the statement to be proved to be true and using this to get the result. I forgot what it is. :-O I'll be going to college tomorrow (err...today, it's way past 12:00) and I'll ask my Math staff for a proof. It's doubtful, given that tomorrow's my last exam, but I'll hope for the best. leppie wrote: This appears to be proof enouhg from my PoV What/Who is PoV? BTW, what's your real name? And the link in your bio is phony. :suss: Thanx, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.
Vikram Punathambekar wrote: This time your proof is only absurd. Sorry. I was told that ;P :laugh: He said I must try it again, but I have been too tired and working on a CS project (95% done, I hate these polishing bits). Vikram Punathambekar wrote: What/Who is PoV? Point of View, dont you play games? Vikram Punathambekar wrote: BTW, what's your real name? That you can deduct from my email address :) Vikram Punathambekar wrote: And the link in your bio is phony. Nope, just no-one has offered to pay for it. Maybe I'll make that my Terms of Use statement in all my code, if you find the code really helpful, please pay for my website. :) Hey leppie! Your "proof" seems brilliant and absurd at the same time. - Vikram Punathambekar 28 Apr '03
-
Sorry, leppie! This time your proof is only absurd. Sorry. If you will see correctly, you will notice that you are assuming what is to be proved as true and using that, you get the result. This CANNOT be accepted as proof at all. There is even a term for this thing- assuming the statement to be proved to be true and using this to get the result. I forgot what it is. :-O I'll be going to college tomorrow (err...today, it's way past 12:00) and I'll ask my Math staff for a proof. It's doubtful, given that tomorrow's my last exam, but I'll hope for the best. leppie wrote: This appears to be proof enouhg from my PoV What/Who is PoV? BTW, what's your real name? And the link in your bio is phony. :suss: Thanx, Vikram. "There's probably a Nish-like alien answering VB questions on a CP forum as we speak." - adamUK in The Lounge, discussing aliens and parallel universes. "Do not give redundant error messages again and again." - A classmate of mine, while giving a class talk on error detection in compiler design.