|
[quote=R.D. Silverman;219568]
No! No! No! The first statement just above is gibberish, but I will attribute it to English being a second language. You are again misusing variables. And you did not read what I wrote in my earlier post. x1 [B]DOES NOT HAVE A COEFFICIENT!!!! [/B] x1 is NOT a variable!! The only VARIABLE(s) here are x and its POWERS. The a_i and the x_i are given CONSTANTS. For f(x) = a_1 x + a_0 the coefficients are a_1 and a_0. The root is x1. Roots do not have coefficients! [/quote] Look, on the paragraph: "This is a sum between two factors, x and x1 The coefficent of x is 1 and of x1 is -1 which is equivallent to: a1=1 and a0=-x1." I didn't mean x1 has a coefficient, that's why I showed a0=-x1. For n=1, f(x)=a1x+a0=(x-x1)---> a1=1, a0=-x1. I myself don't know why I have written "and of x1 is -1" But I didn't mean it (x1 has a coefficient). |
[QUOTE=blob100;219614]Look, on the paragraph:
"This is a sum between two factors, x and x1 The coefficent of x is 1 and of x1 is -1 which is equivallent to: a1=1 and a0=-x1." I didn't mean x1 has a coefficient, that's why I showed a0=-x1. For n=1, f(x)=a1x+a0=(x-x1)---> a1=1, a0=-x1. I myself don't know why I have written "and of x1 is -1" But I didn't mean it (x1 has a coefficient).[/QUOTE] So start over. Give an exact statement of the formula to be proven. |
[quote=R.D. Silverman;219615]So start over. Give an exact statement of the formula to be proven.[/quote]
If I understand, you want me just to show the formula (on this post). ak=((-1)^P)(n_C_P). m_C_P is the sum of all product combinations of P roots taken from n roots of f(x) (which has n roots). ak is the coefficent of x^k in f(x). P=n-k. |
[QUOTE=blob100;219679]If I understand, you want me just to show the formula (on this post).
ak=((-1)^P)(n_C_P). m_C_P is the sum of all product combinations of P roots taken from n roots of f(x) (which has n roots). ak is the coefficent of x^k in f(x). P=n-k.[/QUOTE] Did you read my prior post? You formula must state HOW MANY terms are in the sum. It is a necessary part of any induction proof. It is not enough to say "all product combinations". How many combinations are there? |
[quote=R.D. Silverman;219682]Did you read my prior post? You formula must state HOW MANY terms
are in the sum. It is a necessary part of any induction proof. It is not enough to say "all product combinations". How many combinations are there?[/quote] OK, For a polynomial with n roots, The number of terms (in the sum.....) is (for P roots combinations); (n-P)+(n-(P+1))+...+1=((n-P)^2+(n-P))/2. |
[QUOTE=blob100;219684]OK,
For a polynomial with n roots, The number of terms (in the sum.....) is (for P roots combinations); (n-P)+(n-(P+1))+...+1=((n-P)^2+(n-P))/2.[/QUOTE] Tomer, did you check this for any reasonable small example? Does it work for the coefficient of the x^2 term? What about for the x^1 term? Does your answer to those two questions tell you anything? |
[quote=jyb;219691]Tomer, did you check this for any reasonable small example? Does it work for the coefficient of the x^2 term? What about for the x^1 term? Does your answer to those two questions tell you anything?[/quote]
Sorry, I gave the wrong answer. |
[QUOTE=blob100;219738]Sorry, I gave the wrong answer.[/QUOTE]
Check your results before posting. |
n-k=P. k>P.
The number of terms for x^k is: T=F(P)+F(P-1)+...+F(1). Where F(x) is the Fermat formula taken by x. f(x)=(x^2+x)/2. The number of terms for P is equivallent to x^k's. To open F(P)+F(P-1)+...+F(1)? |
[QUOTE=blob100;219744]n-k=P. k>P.
The number of terms for x^k is: T=F(P)+F(P-1)+...+F(1). Where F(x) is the Fermat formula taken by x. f(x)=(x^2+x)/2. The number of terms for P is equivallent to x^k's. To open F(P)+F(P-1)+...+F(1)?[/QUOTE] I have only one word: Huh???? This is total nonsnse. |
[quote=R.D. Silverman;219750]I have only one word: Huh????
This is total nonsnse.[/quote] What is unable to be understood? I'll try again: n-k=P. And we (arbitarically) assume k>P. F(x)=(x^2+x)/2 (known as the Fermat formula). We would say that the number of terms in the coefficnet of x^k is: F(P)+F(P-1)+...+F(1)=((P^2+P)+((P-1)^2+(P-1))+...+2)/2. I'll use a private case (private cases in our situation throw light on the general case): a,b,c,d,e are the roots. k=3, which means P=3. (a,b,c), (a,b,d), (a,b,e) (a,c,d), (a,c,e) (a,d,e) (b,c,d), (b,c,e) (b,d,e) (c,d,e) Now, we see that the number of terms is 6+3+1. 6=F(3) 3=F(2) 1=F(1) This private case does not come to prove anything, it comes to show from where did I take the formula F(P)+F(P-1)+...+F(1)=((P^2+P)+((P-1)^2+(P-1))+...+2)/2, Which you replayed by "Huh????". |
[QUOTE=blob100;219755]What is unable to be understood?
I'll try again: n-k=P. And we (arbitarically) assume k>P. [/QUOTE] Why this assumption? [QUOTE] F(x)=(x^2+x)/2 (known as the Fermat formula). [/QUOTE] (1) You are again being sloppy about notation. In your prior post you referred to F(x), but you did not define it. Instead you [b]redefined[/b] f(x) (which was already defined at the very beginning of the problem set!!!). f(x) is not the same as F(x). I am also curious. Where did you see that x(x+1)/2 is referred to as the 'Fermat formula'? I have never seen Fermat's name attached to it. (that I can recall) [QUOTE] We would say that the number of terms in the coefficnet of x^k is: F(P)+F(P-1)+...+F(1)=((P^2+P)+((P-1)^2+(P-1))+...+2)/2. [/QUOTE] We are not discussing the number of terms in the coefficient of x^k. We [b]are[/b] discussing the the number of terms in the summation formula that gives the coefficient as a function of the roots. The coefficient of x^k is a constant. It has one term: itself. You are being sloppy about definitions here. And your formula above is not correct. It can not be correct. It is nonsense. F(x) is a quadratic in x. When summed over an arithmetic progression of difference 1, i.e. (P, P-1, P-2, .....1) the result will be a cubic polynomial in P. But the number of terms in the summation formula is not a cubic function of P. Indeed. It is not even a polynomial in P. I will give a hint: The number of different products of roots taken r at a time from a set of size n is a well known COMBINATORIAL object. |
[QUOTE=R.D. Silverman;219757]
\ <snip> .[/QUOTE] I will also add: You wrote "The number of terms for P is equivallent to x^k's. To open F(P)+F(P-1)+...+F(1)?" The first sentence is total gibberish. What does "equivalent to x^k's" mean? It is nonsense. And what does the word "open" mean?? And "To open F(P)+F(P-1)+...+F(1)?" is not even a sentence. |
[quote=R.D. Silverman;219757]Why this assumption?
(1) You are again being sloppy about notation. In your prior post you referred to F(x), but you did not define it. Instead you [B]redefined[/B] f(x) (which was already defined at the very beginning of the problem set!!!). f(x) is not the same as F(x). I am also curious. Where did you see that x(x+1)/2 is referred to as the 'Fermat formula'? I have never seen Fermat's name attached to it. (that I can recall) We are not discussing the number of terms in the coefficient of x^k. We [B]are[/B] discussing the the number of terms in the summation formula that gives the coefficient as a function of the roots. The coefficient of x^k is a constant. It has one term: itself. You are being sloppy about definitions here. And your formula above is not correct. It can not be correct. It is nonsense. F(x) is a quadratic in x. When summed over an arithmetic progression of difference 1, i.e. (P, P-1, P-2, .....1) the result will be a cubic polynomial in P. But the number of terms in the summation formula is not a cubic function of P. Indeed. It is not even a polynomial in P. I will give a hint: The number of different products of roots taken r at a time from a set of size n is a well known COMBINATORIAL object.[/quote] I defined F(x) for every x (it does not concern f(x)). I know, it both concern x (this is my mistake). I'll define y(y+1)/2=F(y) for any natural y. |
[quote=R.D. Silverman;219758]I will also add:
You wrote "The number of terms for P is equivallent to x^k's. To open F(P)+F(P-1)+...+F(1)?" The first sentence is total gibberish. What does "equivalent to x^k's" mean? It is nonsense. And what does the word "open" mean?? And "To open F(P)+F(P-1)+...+F(1)?" is not even a sentence.[/quote] This is another horrible mistake. |
[QUOTE=blob100;219760]This is another horrible mistake.[/QUOTE]
Proofread before you post! |
[quote=R.D. Silverman;219763]Proofread before you post![/quote]
OK. |
I'll try again writing the formula:
The number of terms taken from x^k's coefficient is: F(P)+F(P-1)+...+1. Where P=n-k. F(N)=N(N+1)/2, for any given natural N. BTW: by "open" I meant, to show F(P)+F(P-1)+...+1 as a phrase concerning P's value (not a sum of functions). |
[QUOTE=blob100;219765]I'll try again writing the formula:
The number of terms taken from x^k's coefficient is: F(P)+F(P-1)+...+1. Where P=n-k. F(N)=N(N+1)/2, for any given natural N. [/QUOTE] To the other readers of this thread: What am I doing wrong? Am I not getting through? I [b]already[/b] said that this formula is wrong, explained [b]why[/b] it could not be correct, and gave a strong hint to the correct answer. Yet Tomer insists on repeating the same stuff. Just as he kept using the answer from THIS problem in problem 1 when I told him not to do so. |
[quote=R.D. Silverman;219766]To the other readers of this thread:
What am I doing wrong? Am I not getting through? I [B]already[/B] said that this formula is wrong, explained [B]why[/B] it could not be correct, and gave a strong hint to the correct answer. Yet Tomer insists on repeating the same stuff. Just as he kept using the answer from THIS problem in problem 1 when I told him not to do so.[/quote] I just touhgt you didn't understand what I formulated. |
"I will give a hint: The number of different products of roots taken r
at a time from a set of size n is a well known COMBINATORIAL object. " What you mean is that there is a well known formula for this question? |
The formula that gives the [B]number of combinations[/B] of n things taken k at a time, [SUB]n[/SUB][B]C[/B][SUB]k[/SUB], is well known.
It, also, is not difficult to derive. Perhaps it would be useful for you to back up and go through the exercise of providing a formal proof of that formula. While you are at it, you might learn to use simple formatting in your postings to display exponents and subscripts. Using them will make it easier to read your equations. |
[QUOTE=blob100;219769]"I will give a hint: The number of different products of roots taken r
at a time from a set of size n is a well known COMBINATORIAL object. " What you mean is that there is a well known formula for this question?[/QUOTE] It sounds like you are not familiar with the combination formula. Try this link: [url]http://mathworld.wolfram.com/Combination.html[/url]. While you're at it, look up some of the following terms: "binomial coefficient", "binomial theorem" and "Pascal's Triangle". After you've had a chance to think about this information, see if you can apply it to this problem. |
[QUOTE=R.D. Silverman;219766]To the other readers of this thread:
What am I doing wrong? Am I not getting through? I [b]already[/b] said that this formula is wrong, explained [b]why[/b] it could not be correct, and gave a strong hint to the correct answer. Yet Tomer insists on repeating the same stuff. Just as he kept using the answer from THIS problem in problem 1 when I told him not to do so.[/QUOTE] Yes, it's true that he's doing these things. But he is lacking some specific knowledge that he needs in order to understand your hints. Without that knowledge, which he doesn't know he lacks, he can't do what you're asking so he flails about. The solution isn't to yell at him; that hasn't been particularly successful so far. It's to direct him to the specific information that will help. This I have done. (And FWIW, I agree: there's a question of basic mathematical maturity here. Tomer should have been exposed to the combination formula long ago or, put another way, given that he [I]hasn't[/I] been so exposed it would seem that he is not ready for some of the more advanced topics to which he aspires. He needs time and instruction to gain that maturity.) |
[QUOTE=jyb;219775]Yes, it's true that he's doing these things. But he is lacking some specific knowledge that he needs in order to understand your hints. Without that knowledge, which he doesn't know he lacks, he can't do what you're asking so he flails about.
The solution isn't to yell at him; that hasn't been particularly successful so far. It's to direct him to the specific information that will help. This I have done. (And FWIW, I agree: there's a question of basic mathematical maturity here. Tomer should have been exposed to the combination formula long ago or, put another way, given that he [I]hasn't[/I] been so exposed it would seem that he is not ready for some of the more advanced topics to which he aspires. He needs time and instruction to gain that maturity.)[/QUOTE] He had stated earlier that he was familiar with the binomial theorem........ |
[QUOTE=R.D. Silverman;219777]He had stated earlier that he was familiar with the binomial theorem........[/QUOTE]
Apparently not familiar enough. :grin: |
[QUOTE=jyb;219778]Apparently not familiar enough. :grin:[/QUOTE]
I mean [b]no[/b] insult to Tomer in what I am going to say, but he really thinks that he knows a lot of things that he really doesn't know. It is surely not his fault; I'm sure that the training he received has been inadequate to really do proofs. He seems to have very poor training in the use of definitions, use of variables, substitution of variables, and his derivations just lack rigor. He would benefit greatly from a disciplined proof-based course in Eulclidean Geometry. |
[quote=R.D. Silverman;219781]I mean [B]no[/B] insult to Tomer in what I am going to say,
but he really thinks that he knows a lot of things that he really doesn't know. It is surely not his fault; I'm sure that the training he received has been inadequate to really do proofs. He seems to have very poor training in the use of definitions, use of variables, substitution of variables, and his derivations just lack rigor. He would benefit greatly from a disciplined proof-based course in Eulclidean Geometry.[/quote] "but he really thinks that he knows a lot of things that he really doesn't know." False. I didn't say I know something about the binom (I asked about it in one of the posts, becuase I know it's idea and theme, but I lack skills on the area). And now, after reading Wolfram's page on the binomial coefficients, I may say it is n_C_k=n!/(k!(n-k)!). |
[QUOTE=blob100;219787]n_C_k=n!/(k!(n-k)!).[/QUOTE]
Also meaning no offense, are you able to formulate a proof? At least to me, you have yet to demonstrate that you have the skills required. |
[QUOTE=blob100;219787]And now, after reading Wolfram's page on the binomial coefficients, I may say it is n_C_k=n!/(k!(n-k)!).[/QUOTE]
Okay, you may [I]say[/I] it, but do you [I]understand[/I] it? In what circumstances might it be useful? Can you see how it applies to the polynomial coefficient problem? This is what I meant when I said that you needed to "think about this information". |
[quote=Wacky;219788]Also meaning no offense, are you able to formulate a proof?
At least to me, you have yet to demonstrate that you have the skills required.[/quote] I'll try. Is induction the right approach to do so? |
[QUOTE=blob100;219790]I'll try.
Is induction the right approach to do so?[/QUOTE] "All roads lead to Rome" -- As with many such problems, there are multiple ways to formulate a proof. Any of them would be acceptable. A proof by induction is certainly a reasonable approach. |
[quote=Wacky;219791]"All roads lead to Rome" -- As with many such problems, there are multiple ways to formulate a proof. Any of them would be acceptable.
A proof by induction is certainly a reasonable approach.[/quote] OK. |
[QUOTE=R.D. Silverman;219781]He seems to have very poor training in the use of definitions, use
of variables, substitution of variables, and his derivations just lack rigor. He would benefit greatly from a disciplined proof-based course in Eulclidean Geometry.[/QUOTE] I would say that Tomer likes math and has discovered a number of interesting things about it which make him eager to learn more. Being bright and eager is a good start, but it will only get one so far. In order to really understand math, one also needs to learn rigor, and that requires discipline (as you've said many times). The key is to impart that sense of rigor and discipline without destroying the fun which makes one eager in the first place. He is untrained and lacks rigor. Well that's not a fatal flaw. I think he just hasn't been exposed to that way of thinking much. All of your complaints about his definitions, variables, derivations, etc. are really just symptoms of this lack of exposure. Learning to do proofs is a bit like learning a foreign language; to some degree there's just a style to which one must become accustomed, and being immersed in that is the best way to learn it. You're probably right about a course in geometry, partly because he just needs to spend some time learning to do rigorous proofs, and partly because geometry is a good vehicle for maintaining that sense of fun: who doesn't like drawing pictures? Of course there's really no way to give him geometry problems in this forum, but there are other kinds of problems we could give him that are very simple and would help him practice proofs. |
Proof by induction (binomial theorem):
We see define [sub]n[/sub]C[sub]k[/sub] as the number of combinations of k units taken from a set of n units. Proposition: [sub]n[/sub]C[sub]k[/sub]=(n!)/(P!k!) P=n-k. We will do so by induction on n. Step 1: Showing [sub]0[/sub]C[sub]k[/sub] agree the terms (for n=0, the proposition is true). [sub]0[/sub]C[sub]k[/sub]=1. (0!)/(P!k!)=1/(1*1)=1. Step 2: Assuming that the formula is true for a given n and all 0≤ k≤n. Step 3: Showing that for n+1 the proposition is true if it is for n. We assumed: [sub]n[/sub]C[sub]k[/sub]=(n!)/(P!k!), And we try to prove: [sub]n+1[/sub]C[sub]k[/sub]=((n+1)!)/(P!k!). We see: k=0, ((n+1)!)/((n+1)!0!)=1. And: k=n+1, ((n+1)!)/(0!(n+1)!)=1 And for 0≤ k≤n, [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub]. So, we try porving [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] is equivallent to (n+1)!/((n+1-k)!k!). n!/(n-k)!k!+n!/(n-k+1)!(k-1)!=n!(n-k+1)/(n-k+1)!k!+n!k/(n-k+1)!k!= n!(n+1)/(n-k+1)!k!. Now, we would easily propose the next equation: n!(n+1)/(n-k+1)!k!=(n+1)!/((n+1-k)!k!), Which is what we tried to prove. |
[quote=jyb;219793]I would say that Tomer likes math and has discovered a number of interesting things about it which make him eager to learn more. Being bright and eager is a good start, but it will only get one so far. In order to really understand math, one also needs to learn rigor, and that requires discipline (as you've said many times). The key is to impart that sense of rigor and discipline without destroying the fun which makes one eager in the first place.
He is untrained and lacks rigor. Well that's not a fatal flaw. I think he just hasn't been exposed to that way of thinking much. All of your complaints about his definitions, variables, derivations, etc. are really just symptoms of this lack of exposure. Learning to do proofs is a bit like learning a foreign language; to some degree there's just a style to which one must become accustomed, and being immersed in that is the best way to learn it. You're probably right about a course in geometry, partly because he just needs to spend some time learning to do rigorous proofs, and partly because geometry is a good vehicle for maintaining that sense of fun: who doesn't like drawing pictures? Of course there's really no way to give him geometry problems in this forum, but there are other kinds of problems we could give him that are very simple and would help him practice proofs.[/quote] I think Discrete mathematics is as Euclidean Geometry a good course to learn proofs. Do you agree with me? |
Tomer, there are a number of problems with this. The surest sign of that is that you give a definition for [sub]n[/sub]C[sub]k[/sub], but then you never appear to actually use it anywhere. If you're trying to prove that [sub]n[/sub]C[sub]k[/sub] is equal to something, don't you think you would have to actually use the definition of [sub]n[/sub]C[sub]k[/sub]?
[QUOTE=blob100;219795]Proof by induction (binomial theorem): We see define [SUB]n[/SUB]C[SUB]k[/SUB] as the number of combinations of k units taken from a set of n units.[/QUOTE] This is *not* the Binomial Theorem. Remember I told you to look that up? This is merely a proof that the formula for binomial coefficients matches our notion of "combinations of n things taken k at a time". Also, I've no idea what you mean by "units" in this context. [QUOTE=blob100;219795]Proposition: [SUB]n[/SUB]C[SUB]k[/SUB]=(n!)/(P!k!) P=n-k. We will do so by induction on n. Step 1: Showing [SUB]0[/SUB]C[SUB]k[/SUB] agree the terms (for n=0, the proposition is true). [SUB]0[/SUB]C[SUB]k[/SUB]=1. (0!)/(P!k!)=1. [/QUOTE] Given your definition for [sub]n[/sub]C[sub]k[/sub], what does [sub]0[/sub]C[sub]k[/sub] mean? How do we take k "units" from a set of 0 "units"? And when n = 0, then what is P? Shouldn't it be 0-k = -k? What is (-k)! ? [QUOTE=blob100;219795] Step 2: Assuming that the formula is true for a given n and all 0≤ k≤n. Step 3: Showing that for n+1 the proposition is true if it is for n. We assumed: [SUB]n[/SUB]C[SUB]k[/SUB]=(n!)/(P!k!), And we try to prove: [SUB]n+1[/SUB]C[SUB]k[/SUB]=((n+1)!)/(P!k!). [/QUOTE] No, that last line isn't correct. You need (n+1-k)! in the denominator, but you have P!, which by your definition is (n-k)! This is a good example of adding an extra variable that doesn't do much for you except confuse you. You did define it, but you'd be better off if you simply hadn't introduced it at all. [QUOTE=blob100;219795] We see: k=0, ((n+1)!)/((n+1)!0!)=1. And: k=n+1, ((n+1)!)/(0!(n+1)!)=1 [/QUOTE] Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub]. [QUOTE=blob100;219795] And for 0≤ k≤n, [SUB]n[/SUB]C[SUB]k[/SUB]+[SUB]n[/SUB]C[SUB]k-1[/SUB]. [/QUOTE] What [I]about[/I] [SUB]n[/SUB]C[SUB]k[/SUB]+[SUB]n[/SUB]C[SUB]k-1[/SUB]? Are you trying to say it's equal to something? What? This is like a sentence without a verb. [QUOTE=blob100;219795] So, we try porving [SUB]n[/SUB]C[SUB]k[/SUB]+[SUB]n[/SUB]C[SUB]k-1[/SUB] is equivallent to (n+1)!/((n+1-k)!k!). [/QUOTE] Why? You haven't shown that proving this is in any way related to the problem here. [QUOTE=blob100;219795] n!/(n-k)!k!+n!/(n-k+1)!(k-1)!=n!(n-k+1)/(n-k+1)!k!+n!k/(n-k+1)!k!= n!(n+1)/(n-k+1)!k!. Now, we would easily propose the next equation: n!(n+1)/(n-k+1)!k!=(n+1)!/((n+1-k)!k!), [/QUOTE] Okay, you managed to add the two fractions correctly. But again, how is that related to the problem? [QUOTE=blob100;219795]Which is what we tried to prove.[/QUOTE] Why? |
[QUOTE=blob100;219798]I think Discrete mathematics is as Euclidean Geometry a good course to learn proofs.
Do you agree with me?[/QUOTE] Probably not. Most courses in discrete mathematics would probably assume that you already know how to do rigorous proofs. Though I would need to know more about what you mean when you say discrete mathematics to know for sure. I.e. what specific material do you mean when you say discrete mathematics? |
[quote=jyb;219800]Probably not. Most courses in discrete mathematics would probably assume that you already know how to do rigorous proofs. Though I would need to know more about what you mean when you say discrete mathematics to know for sure. I.e. what specific material do you mean when you say discrete mathematics?[/quote]
Induction, Recurtion, Graph theory, Set theory, Combinatorics, etc. |
OK, you are on the right track.
However, I'll be pedantically "picky" because rigor and completeness are fundamental properties of a [B]formal proof[/B]. If you are just trying to convey "the concept of the proof", you can be a bit more lax, but, eventually, the formalism is expected when you claim to present a proof. But, even for "conceptual proofs", the permitted laxness is related to making assertions without providing their proof. You must still make sure that the statements are accurate and that they are not open to unintended interpretation. [QUOTE=blob100;219795]Proof by induction (binomial theorem): We see define [sub]n[/sub]C[sub]k[/sub] as the number of combinations of k units taken from a set of n units. Proposition: [sub]n[/sub]C[sub]k[/sub]=(n!)/(P!k!) where P=n-k. And we try to prove: [sub]n+1[/sub]C[sub]k[/sub]=((n+1)!)/(P!k!).[/QUOTE] No, [sub]n+1[/sub]C[sub]k[/sub]=((n+1)!)/((n-k+1)!k!). You have written ... =((n+1)!)/((n-k)!k!) [QUOTE]And for 0 ≤ k ≤ n, [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub].[/QUOTE] What does this mean? It is a clause, not an equation. Further, you give not justification for choosing these terms. [QUOTE]Which is what we tried to prove.[/QUOTE] (The customary nomenclature is "QED".) |
[quote=jyb;219799]Tomer, there are a number of problems with this. The surest sign of that is that you give a definition for [sub]n[/sub]C[sub]k[/sub], but then you never appear to actually use it anywhere. If you're trying to prove that [sub]n[/sub]C[sub]k[/sub] is equal to something, don't you think you would have to actually use the definition of [sub]n[/sub]C[sub]k[/sub]?
Also, I've no idea what you mean by "units" in this context. Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub] What [I]about[/I] [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub]? Are you trying to say it's equal to something? What? This is like a sentence without a verb. Why? You haven't shown that proving this is in any way related to the problem here. Okay, you managed to add the two fractions correctly. But again, how is that related to the problem? [/quote] [sub]n[/sub]C[sub]k[/sub] is a symbol discussed before, it means: The number combinations of sub-sets of k objects taken from n objects (a set of n objects). Moreover, by unit I meant object (my English isn't pretty good, as you assumed). "Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub]." "What [I]about[/I] nCk+nCk-1? Are you trying to say it's equal to something? What? This is like a sentence without a verb." This was corresponding the values of k which are 0,n+1 and the naturals in the interval [0,n+1]. I wanted to show what the value of [sub]n[/sub]C[sub]k[/sub] is for every value of k. Starting with showing that for k=0,n+1 the formula is true, and then putting the proof for the formula for every 0<k<n+1. We would say this if 0<k<n+1 the number of combinations is [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub]. By pascal's rule we would say that [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] equls (n+1)!/k!(n-k+1)!. The result (the equation) shows that for 0<k<n+1, the number of combinations is (n+1)!/k!(n-k+1)!. |
[QUOTE=blob100;219805]By pascal's rule we would say that [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] equals (n+1)!/k!(n-k+1)![/QUOTE]
Some problems here: First, Pascal's rule is: [sub]n+1[/sub]C[sub]k[/sub] = [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] Note that this is an equation, not just some terms dangling in space. And the rule does not express the value in direct terms of n and k. Now, if you wish to use this in your proof, first you should state an argument for its applicability. Then the validity is established in an algebraic step by substituting the formula definitions for each of the terms and showing that both sides of the equation reduce to the same thing. |
[QUOTE=Wacky;219811]Some problems here:
First, Pascal's rule is: [sub]n+1[/sub]C[sub]k[/sub] = [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] Note that this is an equation, not just some terms dangling in space. And the rule does not express the value in direct terms of n and k. Now, if you wish to use this in your proof, first you should state an argument for its applicability. Then the validity is established in an algebraic step by substituting the formula definitions for each of the terms and showing that both sides of the equation reduce to the same thing.[/QUOTE] Allow me to suggest that for proving n_C_k is the number of sets of k items taken from n items that a direct proof by counting is usually easier. One starts by proving that the number of rearrangements of a set of size k equals k!. This can be done directly by counting them. |
[QUOTE=R.D. Silverman;219815]Allow me to suggest that for proving n_C_k is the number of sets of
k items taken from n items that a direct proof by counting is usually easier. [/QUOTE] Tomer isn't trying to prove that [sub]n[/sub]C[sub]k[/sub] is the number of sets of k items taken from n items. He [I]defined[/I] [sub]n[/sub]C[sub]k[/sub] that way. He's trying to prove that [sub]n[/sub]C[sub]k[/sub] = n!/((n-k)!k!). Of course it doesn't much matter which way he does it. The important thing is to prove the number of combinations is equal to the fraction, regardless of which way he chooses to define [sub]n[/sub]C[sub]k[/sub]. But for purposes of reading his proof, it's very important to know which way he defined it, so we know what he thinks he's trying to prove. And in his case, he never makes any reference whatsoever to his definition after he makes it, so the proof can't possibly be valid. |
[QUOTE=blob100;219805][sub]n[/sub]C[sub]k[/sub] is a symbol discussed before, it means:
The number combinations of sub-sets of k objects taken from n objects (a set of n objects). Moreover, by unit I meant object (my English isn't pretty good, as you assumed). "Um, okay, yes we see that. But so what? You don't actually show that these correspond in any way to the definition of [sub]n+1[/sub]C[sub]0[/sub] or [sub]n+1[/sub]C[sub]n+1[/sub]." "What [I]about[/I] nCk+nCk-1? Are you trying to say it's equal to something? What? This is like a sentence without a verb." This was corresponding the values of k which are 0,n+1 and the naturals in the interval [0,n+1]. I wanted to show what the value of [sub]n[/sub]C[sub]k[/sub] is for every value of k. Starting with showing that for k=0,n+1 the formula is true, and then putting the proof for the formula for every 0<k<n+1.[/QUOTE] But you [I]don't[/I] show that it's true. You simply assert that it's true. You say that ((n+1)!)/((n+1)!0!)=1, but you don't show that this is equal to [sub]n[/sub]C[sub]0[/sub], given your definition of [sub]n[/sub]C[sub]k[/sub]. [QUOTE=blob100;219805]We would say this if 0<k<n+1 the number of combinations is [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub]. By pascal's rule we would say that [sub]n[/sub]C[sub]k[/sub]+[sub]n[/sub]C[sub]k-1[/sub] equls (n+1)!/k!(n-k+1)!. The result (the equation) shows that for 0<k<n+1, the number of combinations is (n+1)!/k!(n-k+1)!.[/QUOTE] Again, you make no reference to the definition of [sub]n[/sub]C[sub]k[/sub], so how does this show anything about [sub]n+1[/sub]C[sub]k[/sub]? |
[QUOTE=R.D. Silverman;219815]One starts by proving that the number of rearrangements of a set of size k equals k![/QUOTE]
Bob, I, too, would have approached this from the [SUB]n[/SUB]P[SUB]n[/SUB] -> [SUB]n[/SUB]P[SUB]k[/SUB] -> [SUB]n[/SUB]C[SUB]k[/SUB] path. However, Tomer chose another path and the proof can be accomplished that way also, and without too much difficulty. To me, the important thing is that he display all of the elements of the proof. I didn't discourage him because he may be more comfortable with his chosen path. Using his approach, he needs to show that Pascal's rule applies and that, by algebra, n!/((k!(n-k)!) is consistent with this rule and the boundary conditions. Richard |
[QUOTE=Wacky;219819]Bob,
I, too, would have approached this from the [SUB]n[/SUB]P[SUB]n[/SUB] -> [SUB]n[/SUB]P[SUB]k[/SUB] -> [SUB]n[/SUB]C[SUB]k[/SUB] path. However, Tomer chose another path and the proof can be accomplished that way also, and without too much difficulty. To me, the important thing is that he display all of the elements of the proof. I didn't discourage him because he may be more comfortable with his chosen path. Using his approach, he needs to show that Pascal's rule applies and that, by algebra, n!/((k!(n-k)!) is consistent with this rule and the boundary conditions. Richard[/QUOTE] The purely inductive proof is a bit more complicated, because for n_C_k, there are TWO variables involved and you have to do more than one induction. |
[QUOTE=R.D. Silverman;219850]The purely inductive proof is a bit more complicated, because for n_C_k,
there are TWO variables involved and you have to do more than one induction.[/QUOTE] Agreed. But it is not difficult to do that. Further, while formulating such a proof, Tomer may recognize some other path that he will find even less difficult. Remember that the goal is "to produce a rigorous proof", not "to produce a proof exclusively by induction". I believe that Tomer is honestly trying to learn how to present a proper proof. We should encourage him to make progress and help by pointing out any weaknesses in his presentation. Just as there are two "dimensions" to the inductive proof, there are two dimensions to Tomer's training. One of them is the establishment of logical steps in a proof and preparing a formal proof of each step. The other is to prove a particular formula. In my opinion, as long as he isn't going in a totally wrong direction with respect to the latter, we should welcome progress on the former even if that means that the journey meanders a bit. |
[LEFT][FONT=Times New Roman][SIZE=3]We define n_C_k as the number of combinations of k objects taken from a set of n objects.[/SIZE][/FONT][/LEFT]
[LEFT][FONT=Times New Roman][SIZE=3]Proposition:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n_C_k=n!/(n-k)!k!.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]To formulate this proof, we will use induction on n.[/SIZE][/FONT][/LEFT] [LEFT][FONT=Times New Roman][SIZE=3]Step 1:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We will start our proof by the first step, showing that for n=0 the equation is true.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]So, by locating 0 where n is written we have:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]0_C_k and 0!/(0-k)!k!.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]k must equal 0 because the maximal value of k out of n objects is 0,[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]This gives the next 0_C_0.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]And we assume easily 0_C_0=1.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]On the same time, by k=0, n!/(n-k)!k!=1/0!0!=1.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]This shows that for n=0 the proposition is true.[/SIZE][/FONT][/LEFT] [LEFT][FONT=Times New Roman][SIZE=3]Step 2:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]To continue with the inductive proof, we will assume the proposition for every natural </=n and 0=/<k</=n.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]By proving that if we assume that last statement the proposition (the proposition the assumption corresponding to) is true for n+1, we complete the inductive proof.[/SIZE][/FONT][/LEFT] [LEFT][FONT=Times New Roman][SIZE=3]Step 3:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We prove that for n+1 the proposition is true if it is true for n.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]The next phrase is what we try to prove:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n+1_C_k=(n+1)!/(n-k+1)!k! for any 0=/<k</=n+1,[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n+1_C_k is of course concerning n+1 and (n+1)!/(n-k+1)!k! is what we see as the same phrase as n!/(n-k)!k! just for n+1.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]This means, proving the statement:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]The number of combinations between k objects out of n+ 1 object is similar to what we assumed equals it (by the proposition).[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We will show that n+1_C_k is true for three kinds of values of k, [/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We will show that for these three values, the proposition is true.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]The values of k are: k=0, k=n+1, 0<k<n+1,[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]And we easily assume that for proving that these all values of k show that the next n+1_C_k=(n+1)!/(n-k+1)!k! as a valid equation,[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We proved the proposition.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n+1_C_0 is of course 1, there is only one combination of 0 objects (0 itself),[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]And on the same time, (n+1)!/(n+1)!0! equals 1.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]Corresponding to our goal, we see n+1_C_k=(n+1)!/(n-k)!k! for k=0.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We see that both n+1_C_n+1 (k=n+1) and (n+1)!(n+1-n-1)!(n+1)! equal 1 (equivalent).[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]Now, we will continue to proving the statement for every 0<k<n+1.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We try to prove that for these values of k (0<k<n+1) the value of n+1_C_k equals (n+1)!/(n-k+1)!k!.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]By pascal's rule we see the equation: n+1_C_k=n_C_k+n_C_k-1.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]This identify directs us to the next value of the right side of the equation:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n_C_k (as we assumed on Step 2) equals n!/(n-k)!k!, and same with n_C_k-1 which equals (by the same assumption) n!/(n-k+1)!(k-1)!.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]This gives n+1_C_k equals to the sum of the two n!/(n-k+1)!(k-1)! and [/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n!/(n-k)!k!.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n!/(n-k)!k!+ n!/(n-k+1)!(k-1)!=(n+1)!/(n-k+1)!k! (by trivial conclusions of algebra).[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]This last statement directs us to n+1_C_k=(n+1)!/(n-k+1)!k! which is what we tried to prove till now.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3][/SIZE][/FONT] [/LEFT] |
[QUOTE=blob100;219890][LEFT][FONT=Times New Roman][SIZE=3]We define n_C_k as the number of combinations of k objects taken from a set of n objects.[/SIZE][/FONT][/LEFT]
[LEFT][FONT=Times New Roman][SIZE=3]Proposition:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]n_C_k=n!/(n-k)!k!.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]To formulate this proof, we will use induction on n.[/SIZE][/FONT][/LEFT] [LEFT][FONT=Times New Roman][SIZE=3]Step 1:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]We will start our proof by the first step, showing that for n=0 the equation is true.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]So, by locating 0 where n is written we have:[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]0_C_k and 0!/(0-k)!k!.[/SIZE][/FONT] [FONT=Times New Roman][SIZE=3]k must equal 0 because the maximal value of k out of n objects is 0,[/SIZE][/FONT] [/QUOTE] No. For induction on n, you start by fixing a value of k. So you can take k = 1 and then k = 1 throughout the proof. The induction is on n. You start with n=1. Then you will need to fix n, and do an induction on k. Then you will need to do a induction on both together. And your last sentence is nonsense. You must start your proof by counting the number of ways one can select 1 object from a set of size 1 and showing that this number is given by your formula. Then you assume that the formula is true for arbitrary n (with k=1) and must show that it is then true for n+1. This means showing that if n_C_1 has the value given by the formula, then {n+1}_C_1 gives the correct number of subsets of size 1 when n increases to n+1. This means that you must independently COUNT the number of such subsets and show that it satisfies the formula. So: if n_C_1 has some value, say R, how do you count the number of subsets for {n+1} based only upon n_C_1 = R? The number of such subsets will depend on R. You must then show that this number satisfies your formula. Then, you fix n to have some arbitrary large value and do induction on k. Then, you do an induction on n and k simultaneously. |
[QUOTE=R.D. Silverman;219893]No.
For induction on n, you start by fixing a value of k. So you can take k = 1 and then k = 1 throughout the proof. The induction is on n. You start with n=1. Then you will need to fix n, and do an induction on k. Then you will need to do a induction on both together. And your last sentence is nonsense. You must start your proof by counting the number of ways one can select 1 object from a set of size 1 and showing that this number is given by your formula. Then you assume that the formula is true for arbitrary n (with k=1) and must show that it is then true for n+1. This means showing that if n_C_1 has the value given by the formula, then {n+1}_C_1 gives the correct number of subsets of size 1 when n increases to n+1. This means that you must independently COUNT the number of such subsets and show that it satisfies the formula. So: if n_C_1 has some value, say R, how do you count the number of subsets for {n+1} based only upon n_C_1 = R? The number of such subsets will depend on R. You must then show that this number satisfies your formula. Then, you fix n to have some arbitrary large value and do induction on k. Then, you do an induction on n and k simultaneously.[/QUOTE] Let me also add that at no time in the previous effort did you ever actually COUNT the number of subsets and show that the formula is correct. Furthermore, you are not allowed to use anything, such as "pascal's rule' that has not already been proved. I will present an example. Suppose you know that for n = 50, that there are R subsets of size 17. The induction *assumes* that the formula gives the correct answer. You then let n = 51. You now need to determine 51_C_17 WITHOUT USING THE FORMULA. (but you do use the value of R) You then need to show that the value you get for n = 51 satifies the formula. |
[quote=R.D. Silverman;219895]Let me also add that at no time in the previous effort did you ever
actually COUNT the number of subsets and show that the formula is correct. Furthermore, you are not allowed to use anything, such as "pascal's rule' that has not already been proved. I will present an example. Suppose you know that for n = 50, that there are R subsets of size 17. The induction *assumes* that the formula gives the correct answer. You then let n = 51. You now need to determine 51_C_17 WITHOUT USING THE FORMULA. (but you do use the value of R) You then need to show that the value you get for n = 51 satifies the formula.[/quote] I can prove pascal's rule, furthermore, it is trivially true. |
[QUOTE=blob100;219890]By Pascal's rule we see the equation: n+1_C_k=n_C_k+n_C_k-1.[[/QUOTE]
I have a problem with the way that you have used Pascal's rule. You have done so [B]without providing any justification[/B]. If you are going to use Pascal's rule, then you [B]must prove[/B] that it is applicable. Otherwise your argument is just a proof that x!/(x-y)!y! is a solution to the recursive definition f(x,y) = f(x-1,y)+f(x-1,y-1). You have not proven anything about the "number of combinations". Don't get too caught up in Bob's "double induction" argument. It appears to me that your proof is headed toward a slightly different approach that does not rely upon induction on k. |
[QUOTE=Wacky;219899]I have a problem with the way that you have used Pascal's rule. You have done so [B]without providing any justification[/B]. If you are going to use Pascal's rule, then you [B]must prove[/B] that it is applicable. Otherwise your argument is just a proof that x!/(x-y)!y! is a solution to the recursive definition f(x,y) = f(x-1,y)+f(x-1,y-1). You have not proven anything about the "number of combinations".
Don't get too caught up in Bob's "double induction" argument. It appears to me that your proof is headed toward a slightly different approach that does not rely upon induction on k.[/QUOTE] I said earlier that the induction proof was cumbersome. I much prefer a direct counting argument. It only takes a small number of steps. |
First of all, I can use pascal's rule,
Here is the proof: We try to prove: n_C_k=n-1_C_k-1+n-1_C_k. The left side: the number of combinations we can make with k objects out of n objects. Since 1</=[I]k</=[/I][I]n[/I] − 1, We can pick an arbitary J object of the set of the n objects ( the remaining sub-set is not empty). For each k-set if J is chosen, there are n-1_C_k-1 ways to choose the remaining k-1 objects out of the remaining n-1 choices; And there are n-1_C_k combinations with the remaining k objects out of the remaining n-1 objects (choices). Finally we have n-1_C_k+n-1_C_k combinations of k objects with J included in each combination which is how n_C_k defined. |
Is this a valid approach for the proof of the combinatorical theorem?:
[SUB]n[/SUB]C[SUB]k[/SUB]=[SUB]n[/SUB]C[SUB]k-1[/SUB](n-k/k). This is of course a recursive phrase which can be written as: [SUB]n[/SUB]C[SUB]k[/SUB]=(PI)[sup]J=k-1[/sup][sub]J=0[/sub](n-k+J)/(k-J), We see these two statements: (PI)[sup]J=k-1[/sup][sub]J=0[/sub](k-J)=k! (PI)[sup]J=k-1[/sup][sub]J=0[/sub](n-k+J)=n!/(n-k)! And by producting these two (the first proposition's right side) we get: [SUB]n[/SUB]C[SUB]k[/SUB]=n!/(n-k)!k!. *(PI)[sup]J=k-1[/sup][sub]J=0[/sub] is a product of the series with the index J=0 to J=k-1 (I didn't find how to write the index under and above the (PI)). This approach is the proposition needed to be proved in the induction on k in the doubled-induction proof. |
[QUOTE=blob100;219948]First of all, I can use pascal's rule[/QUOTE]
In presenting a proof, it is quite permissible to prove one theorem and thereafter use it in the proof of another theorem. I'm sure that it is just a language issue, but "use" carries the connotation that the result of a theorem will be applied without proving the theorem itself at that point because it has already been established. It is your intent to present and prove a theorem (Pascal's rule) so that you may use it in the subsequent proof. Therefore, a term such as "prove", "establish", or "verify", rather than the term "use", would describe better your intent. [QUOTE]Here is the proof: We try to prove: n_C_k=n-1_C_k-1+n-1_C_k. The left side: the number of combinations we can make with k objects out of n objects. [/QUOTE] Proving that a recursive formula describes some measure is essentially a proof by induction. Therefore, for completeness, you must also include the boundary conditions and show that the formulation applies in all instances. So your method of proof is now: Part 1: Prove that the "number of combinations" conforms to Pascal's rule (and each of the boundary conditions). Part 2: Prove that [SUB]n[/SUB]C[SUB]k[/SUB] = n!/(k!(n-k)!) meets all of the conditions expressed in part 1. |
For B a given non-empty set |B| will denote the large of the set (the number of objects in the set).
I have another approach to this proposition's proof (much easier): We will first prove the next lemma: For a given set A, |A|=n, and we define k as a natural number 0=/<k</=n. The number of sequences which contain k objects out of A's objects is: n(n-1)(n-2)....(n-k+1)=n!/(n-k)!. Proof: We see that for the first objects in the sequence we have n options to choose (there are n objects not contained in the sequence). The next object is able to be n-1 options, The next is n-2... When we will choose the object number k (the last object in the sequence) will have n-k+1 options to choose. This gives n(n-1)...(n-k+1)=n!/(n-k)!. This last theorem gives the approach to prove our problem: For the defined A,k,n we have: n_C_k=n!/(n-k)!k!. Where n_C_k is the number of combinations of k objects out of n objects. We firstly see that the number of promotations of every sequence is k! [SIZE=1]*I can prove this easily, but it does not seem to be nessecary.[/SIZE] We would say that a combination is similar to a sub-set of A. By this, we easily see that if there are k! promotations of every sequence, for every sub-set of A of k objects there are k! sequences of k objects. (I mean, for every k! sequences of k objects there is [U]only one[/U] such sub-set of k objects). So, if the theorem of the sequence counting was n!/(n-k)! the result of the sub-set counting will be n!(n-k)!k!. |
[QUOTE=blob100;220011]For B a given non-empty set |B| will denote the large of the set (the number of objects in the set).
I have another approach to this proposition's proof (much easier): We will first prove the next lemma: For a given set A, |A|=n, and we define k as a natural number 0=/<k</=n. The number of sequences which contain k objects out of A's objects is: n(n-1)(n-2)....(n-k+1)=n!/(n-k)!. Proof: We see that for the first objects in the sequence we have n options to choose (there are n objects not contained in the sequence). The next object is able to be n-1 options, The next is n-2... When we will choose the object number k (the last object in the sequence) will have n-k+1 options to choose. This gives n(n-1)...(n-k+1)=n!/(n-k)!. [/QUOTE] Correct, so far [QUOTE] This last theorem gives the approach to prove our problem: We firstly see that the number of promotations of every sequence is k! [/QUOTE] What is a "promotion"? Stop inventing terminolgy. I deleted the rest. It was so poorly worded as to make no sense. Proving that you must now divide by k! is simple, but you first need to prove that the number of different arrangements of k items is k! |
[QUOTE=R.D. Silverman;220014]
What is a "promotion"? Stop inventing terminology.[/QUOTE] Bob, I'm sure that he meant "Permutation". I don't know if the error occurred because of a language barrier or careless typing? [QUOTE=blob100;220011]We firstly see that the number of promotations of every sequence is k! *I can prove this easily, but it does not seem to be nessecary.[/QUOTE] necessary [QUOTE=R.D. Silverman;220014]but you first need to prove that the number of different arrangements of k items is k![/QUOTE] I will agree with Bob that you really do need to supply this portion of the proof. |
[quote=Wacky;220016]Bob,
I'm sure that he meant "Permutation". I don't know if the error occurred because of a language barrier or careless typing? necessary I will agree with Bob that you really do need to supply this portion of the proof.[/quote] Yes, for the proof of our proposition I had problem expressing myself. Ok, to write the Hebrew taken from English word permutation and what I have written (promotation which does not exist, this made me to think it is an individual mathematical word) are written in Hrebew the same. For two different words with different pronouncements, same word writing. |
[quote=R.D. Silverman;220014]Correct, so far
What is a "promotion"? Stop inventing terminolgy. I deleted the rest. It was so poorly worded as to make no sense. Proving that you must now divide by k! is simple, but you first need to prove that the number of different arrangements of k items is k![/quote] I'll try again expressing myself. If the number of permutations of a sequence of k out of n objects is k!, For the same k objects we can build just one set (these objects are the same as in the sequences). This set can be found as a combination of k objects out of n objects. This gives that for every k! sequences there is just one such a combination. This is equivallent to say (the number of sequences)/k!. The number of sequences was discussed before as n!/(n-k)!, These two results (the formula and the ratio between the sequneces and combinations) direct us to the next n!/(n-k)!k!=(the number of combinations of k objects out of n objects). |
[quote=Wacky;220016]
necessary .[/quote] I'll show that the number of permutations of a sequence is k!, Where the sequence includes k objects. The number of objects in a given permutation is as we defined k. The first objects in a permutation can be chosen as k different objects, The next one can be k-1 options,..., and the number k will be able to be just one object. This gives that the number of permutations is k!. |
[quote=blob100;220039]I'll show that the number of permutations of a sequence is k!,
Where the sequence includes k objects. The number of objects in a given permutation is as we defined k. The first objects in a permutation can be chosen as k different objects, The next one can be k-1 options,..., and the number k will be able to be just one object. This gives that the number of permutations is k!.[/quote] I think, it is not finished: I was needed to write: "this gives that the number of permutations is: k(k-1)(k-2)...1=k!." |
From now, what to do?
|
[QUOTE=blob100;220137]From now, what to do?[/QUOTE]
You still haven't applied what you have now learned about combinations ([sub]n[/sub]C[sub]k[/sub]) to the polynomial coefficient problem (#2 of Silverman's polynomial problems). Can you state and prove a simple formula for the coefficient of x^k? |
[quote=jyb;220185]You still haven't applied what you have now learned about combinations ([sub]n[/sub]C[sub]k[/sub]) to the polynomial coefficient problem (#2 of Silverman's polynomial problems). Can you state and prove a simple formula for the coefficient of x^k?[/quote]
Of course I will do so, but first I want Silverman to agree with what I have done till now. This is what tutoring means. |
[COLOR=black][FONT=Verdana]Now, for the primary problem:[/FONT][/COLOR]
[COLOR=black][FONT=Verdana]We try to prove that the coefficient a_k of x^k in [/FONT][/COLOR] [COLOR=black][FONT=Verdana]f(x)=x^n+a_(n-1)x^(n-1)+...+a_0 (a polynomial of degree n) is [/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k=((-1)^(n-k))(c1+c2+...+c(n_C_n-k)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]A={a_0,a_1,...,a_n} the set of the coefficients of the polynomial f(x).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]B={c1,c2,...,c(n_C_k)} is defined as the set of all product combinations of k roots out of n roots.[/FONT][/COLOR] We of course define n_C_k as the number of combinations of k objects out of n objects (number of sub-sets of a set of n objects). We will use the result of the value of n_C_k, so we must assume it first: n_C_k=n!/(n-k)!k!. [COLOR=black][FONT=Verdana]We will prove this by induction on n:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]I'll repeat the proposition: [/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k=((-1)^(n-k))(c1+c2+...+c(n_C_(n-k))).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*We define R as R=(c1+c2+...+c(n_C_(n-k)) and we say:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]If n-k=0 then R=1.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*a_k=((-1)^(n-k))(R) is our proposition.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Step 1:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We show that for a polynomial of n=1 the proposition is true:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]f(x)=(x-x1)[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Where D={x1,x2,...,xn} the set of all roots of a polynomial of degree n.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We see that the coefficient of x^0 by the formula is -x1=((-1)^(1-0))(x1) which fits the reality.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]For the coefficient of x^1 by the formula we get ((-1)^(1-1))(1)[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We see that R=1 just becuase n-k=0 (again, it fits the reality).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Step 2:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We assume the proposition is true for n.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]From here we will try proving the proposition is true for n+1.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Step 3:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]If we had a polynomial f(x)=a_nx^n+...+a_0,[/FONT][/COLOR] [COLOR=black][FONT=Verdana]From here, the approach will be: proving the coefficients of [/FONT][/COLOR] [COLOR=black][FONT=Verdana]f(x)(x-x(n+1)) fit the proposition.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*x(n+1) is a root of the polynomial f(x)(x-x(n+1)) not a product between two factors.[/FONT][/COLOR] [COLOR=black][FONT=Verdana](a_nx^n+...+a_0)(x-x(n+1))=f(x)(x-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We see that f(x)(x-x(n+1))=[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_(n+1)x^(n+1)+...+a_(k-1)x^(k-1)*x+((a_k)x^k)(-x(n+1))+...+a_0.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We, from now, concern to the phrase a_(k-1)x^(k-1)*x+((a_k)x^k)(-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]This last phrase means the coefficient of x^k in f(x)(x-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]And by this last result it is: a_(k-1)+a_k(-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We will show every part of this coefficient in it's most helpful form:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_(k-1)=((-1)^(n-k+1))(C1+C2+...+C(n_C_(n-k+1)))=[/FONT][/COLOR] [COLOR=black][FONT=Verdana]((-1)^(n-k+1))(G).[/FONT][/COLOR] Where E={C1,C2,...,C(n_C_(n-k+1))} the set of all product combinations of n-k+1 roots out of n roots. [COLOR=black][FONT=Verdana]*We define G as C1+C2+...+C(n_C_(n-k+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k=((-1)^(n-k))(c1+c2+...+c(n_C_(n-k)))=((-1)^(n-k))(R).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*We will again discuss the value of R: R=(c1+c2+...+c(n_C_(n-k)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We must see the difference between G and R, by the number of such product combinations and their number of root factors.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k(-x(n+1))=((-1)^(n-k))(R)(-x(n+1))=((-1)^(n-k+1))(R(x(n+1)))).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]R(-x(n+1)) is of course a sum of product combinations, each n-k+1 roots (similar to G's product combinations).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_(k-1)+a_k(-x(n+1))=((-1)^(n-k+1))(G+R(x(n+1))).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Now, we will try to verify ((-1)^(n-k+1))(G+R(x(n+1))) fits the proposition.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]By the proposition:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]The coefficient of x^k in the new polynomial is:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]((-1)^(n+1-k))(M)[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Where M is the sum of the n_C_(n+1-k) product combinations of n+1-k roots.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We now try to prove M=G+R(x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]G and R(x(n+1)) are two sums of different product combinations of n-k+1 [/FONT][/COLOR] [COLOR=black][FONT=Verdana]roots.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]From here, things seem pretty trivial (by the definitions of R,M,G).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]R(x(n+1))+G is the sum of the n!/(k-1)!(n-k+1)!+n!/(n-k)!k! product combinations of the n+1 roots. [/FONT][/COLOR] [COLOR=black][FONT=Verdana]M is the sum of the [U]same[/U] n!/(n-k+1)!k! product combinations of the n+1 roots.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]By Pascal's rule (or simple algebra) [/FONT][/COLOR] [COLOR=black][FONT=Verdana]n!/(n-k+1)!k!=n!/(k-1)!(n-k+1)!+n!/(n-k)!k! is true,[/FONT][/COLOR] [COLOR=black][FONT=Verdana]And this completes the proof of M=G+R(x(n+1)).[/FONT][/COLOR] |
[quote=blob100;220216][COLOR=black][FONT=Verdana]Now, for the primary problem:[/FONT][/COLOR]
[COLOR=black][FONT=Verdana]We try to prove that the coefficient a_k of x^k in [/FONT][/COLOR] [COLOR=black][FONT=Verdana]f(x)=x^n+a_(n-1)x^(n-1)+...+a_0 (a polynomial of degree n) is [/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k=((-1)^(n-k))(c1+c2+...+c(n_C_n-k)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]A={a_0,a_1,...,a_n} the set of the coefficients of the polynomial f(x).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]B={c1,c2,...,c(n_C_k)} is defined as the set of all product combinations of k roots out of n roots.[/FONT][/COLOR] We of course define n_C_k as the number of combinations of k objects out of n objects (number of sub-sets of a set of n objects). We will use the result of the value of n_C_k, so we must assume it first: n_C_k=n!/(n-k)!k!. [COLOR=black][FONT=Verdana]We will prove this by induction on n:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]I'll repeat the proposition: [/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k=((-1)^(n-k))(c1+c2+...+c(n_C_(n-k))).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*We define R as R=(c1+c2+...+c(n_C_(n-k)) and we say:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]If n-k=0 then R=1.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*a_k=((-1)^(n-k))(R) is our proposition.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Step 1:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We show that for a polynomial of n=1 the proposition is true:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]f(x)=(x-x1)[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Where D={x1,x2,...,xn} the set of all roots of a polynomial of degree n.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We see that the coefficient of x^0 by the formula is -x1=((-1)^(1-0))(x1) which fits the reality.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]For the coefficient of x^1 by the formula we get ((-1)^(1-1))(1)[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We see that R=1 just becuase n-k=0 (again, it fits the reality).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Step 2:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We assume the proposition is true for n.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]From here we will try proving the proposition is true for n+1.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Step 3:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]If we had a polynomial f(x)=a_nx^n+...+a_0,[/FONT][/COLOR] [COLOR=black][FONT=Verdana]From here, the approach will be: proving the coefficients of [/FONT][/COLOR] [COLOR=black][FONT=Verdana]f(x)(x-x(n+1)) fit the proposition.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*x(n+1) is a root of the polynomial f(x)(x-x(n+1)) not a product between two factors.[/FONT][/COLOR] [COLOR=black][FONT=Verdana](a_nx^n+...+a_0)(x-x(n+1))=f(x)(x-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We see that f(x)(x-x(n+1))=[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_(n+1)x^(n+1)+...+a_(k-1)x^(k-1)*x+((a_k)x^k)(-x(n+1))+...+a_0.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We, from now, concern to the phrase a_(k-1)x^(k-1)*x+((a_k)x^k)(-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]This last phrase means the coefficient of x^k in f(x)(x-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]And by this last result it is: a_(k-1)+a_k(-x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We will show every part of this coefficient in it's most helpful form:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_(k-1)=((-1)^(n-k+1))(C1+C2+...+C(n_C_(n-k+1)))=[/FONT][/COLOR] [COLOR=black][FONT=Verdana]((-1)^(n-k+1))(G).[/FONT][/COLOR] Where E={C1,C2,...,C(n_C_(n-k+1))} the set of all product combinations of n-k+1 roots out of n roots. [COLOR=black][FONT=Verdana]*We define G as C1+C2+...+C(n_C_(n-k+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k=((-1)^(n-k))(c1+c2+...+c(n_C_(n-k)))=((-1)^(n-k))(R).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]*We will again discuss the value of R: R=(c1+c2+...+c(n_C_(n-k)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We must see the difference between G and R, by the number of such product combinations and their number of root factors.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_k(-x(n+1))=((-1)^(n-k))(R)(-x(n+1))=((-1)^(n-k+1))(R(x(n+1)))).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]R(-x(n+1)) is of course a sum of product combinations, each n-k+1 roots (similar to G's product combinations).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]a_(k-1)+a_k(-x(n+1))=((-1)^(n-k+1))(G+R(x(n+1))).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Now, we will try to verify ((-1)^(n-k+1))(G+R(x(n+1))) fits the proposition.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]By the proposition:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]The coefficient of x^k in the new polynomial is:[/FONT][/COLOR] [COLOR=black][FONT=Verdana]((-1)^(n+1-k))(M)[/FONT][/COLOR] [COLOR=black][FONT=Verdana]Where M is the sum of the n_C_(n+1-k) product combinations of n+1-k roots.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]We now try to prove M=G+R(x(n+1)).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]G and R(x(n+1)) are two sums of different product combinations of n-k+1 [/FONT][/COLOR] [COLOR=black][FONT=Verdana]roots.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]From here, things seem pretty trivial (by the definitions of R,M,G).[/FONT][/COLOR] [COLOR=black][FONT=Verdana]R(x(n+1))+G is the sum of the n!/(k-1)!(n-k+1)!+n!/(n-k)!k! product combinations of the n+1 roots. [/FONT][/COLOR] [COLOR=black][FONT=Verdana]M is the sum of the [U]same[/U] n!/(n-k+1)!k! product combinations of the n+1 roots.[/FONT][/COLOR] [COLOR=black][FONT=Verdana]By Pascal's rule (or simple algebra) [/FONT][/COLOR] [COLOR=black][FONT=Verdana]n!/(n-k+1)!k!=n!/(k-1)!(n-k+1)!+n!/(n-k)!k! is true,[/FONT][/COLOR] [COLOR=black][FONT=Verdana]And this completes the proof of M=G+R(x(n+1)).[/FONT][/COLOR][/quote] Anyone would like to help here? |
[quote=R.D. Silverman;218562](3) Prove the remainder theorem:
The remainder left when f(x) is divided by (x-r) equals f(r). .[/quote] I guess I need to solve this problem. I can't understand this theorem.... |
[quote=blob100;220729]I guess I need to solve this problem.
I can't understand this theorem....[/quote]Let's see if this helps you understand. First an explanation of the notation: f(x) is a polynomial in x. That is f(x) is shorthand for a_0 +a_1 * x + a_2 * x^2 + ... where the a_i are all constants and there are finitely many non-zero a_i. (x-r) is a polynomial in x where a_0 equals -r, a_1 equals 1 and all other a_i are zero. It's a linear and monic polynomial, though that's jargon you don't strictly need to solve the problem. f(r) is the value of f(x) when x has the value r and r is a constant. Now, just to ensure all this is nailed down, let's take a particular example where f(x) is 1+4x+3x^2 and r=2. It's fairly easy to see that (1+4x+3x^2) = (x-2)*(3x+10) + 21, so the remainder when (1+4x+3x^2) is divided by (x-2) is 21. Substituting the value 2 into the example polynomial gives 1 + 4*2 + 3*(2^2) = 1+8+3*4 = 21. Your task is to prove that the stated result holds for all possible polynomials and all values of r. Paul |
[quote=xilman;220734]Let's see if this helps you understand. First an explanation of the notation:
f(x) is a polynomial in x. That is f(x) is shorthand for a_0 +a_1 * x + a_2 * x^2 + ... where the a_i are all constants and there are finitely many non-zero a_i. (x-r) is a polynomial in x where a_0 equals -r, a_1 equals 1 and all other a_i are zero. It's a linear and monic polynomial, though that's jargon you don't strictly need to solve the problem. f(r) is the value of f(x) when x has the value r and r is a constant. Now, just to ensure all this is nailed down, let's take a particular example where f(x) is 1+4x+3x^2 and r=2. It's fairly easy to see that (1+4x+3x^2) = (x-2)*(3x+10) + 21, so the remainder when (1+4x+3x^2) is divided by (x-2) is 21. Substituting the value 2 into the example polynomial gives 1 + 4*2 + 3*(2^2) = 1+8+3*4 = 21. Your task is to prove that the stated result holds for all possible polynomials and all values of r. Paul[/quote] So I'm needed to prove: f(x)=f(r)(mod x-r) Where f(x) is a given polynomial in x, f(r) is the result when x=r and x-r is a monic polynomial with a_0=-r and a_1=1. Example: f(x)=(1+4x+3x^2) = (x-2)*(3x+10) + 21 is equivallent to: f(x)=21(mod x-2) Where we know f(2)=21. |
Here is the proof:
We try to show the next congruence as valid: f(x)=f(r)(mod x-r). Where we state f(x)=anx^n+...+a0. A={a0,a1,...,an} the set of the coefficients of f(x) a polynomial in x of degree n. f(r) is the result given by x=r, where r is a constant. x-r is a monic polynomial a0=-r, a1=1. We try to prove: anx^n+...+a0=r^n+...+a0(mod x-r). an(x^n-r^n)+a(n-1)(x^(n-1)+r^(n-1))+....+a1(x-r)=0(mod x-r). This last phrase is trivially true by the next useful theorem: Theorem: If x=/=y and n>0 (natural number), then: x-y/x^n-y^n. We have shown that every such ai(x^i-r^i) in the sum is devided by x-r, which gives the whole sum is devided by x-r. |
[QUOTE=blob100;220893]So I'm needed to prove:
f(x)=f(r)(mod x-r) Where f(x) is a given polynomial in x, f(r) is the result when x=r and x-r is a monic polynomial with a_0=-r and a_1=1. Example: f(x)=(1+4x+3x^2) = (x-2)*(3x+10) + 21 is equivallent to: f(x)=21(mod x-2) Where we know f(2)=21.[/QUOTE] This is totally wrong. You keep failinbg to check your work. if e.g. x=7, then f(x) = 176, x-2 = 5, so f(x) = 1 mod x-2, yet you claim f(x) = 21 mod x-2. This is a totally incorrect statement of the problem. You need to prove that f(r) = the remainder when f(x) is divided by (x-r). |
[QUOTE=blob100;220894]Here is the proof:
We try to show the next congruence as valid: f(x)=f(r)(mod x-r). Where we state f(x)=anx^n+...+a0. A={a0,a1,...,an} the set of the coefficients of f(x) a polynomial in x of degree n. f(r) is the result given by x=r, where r is a constant. x-r is a monic polynomial a0=-r, a1=1. We try to prove: anx^n+...+a0=r^n+...+a0(mod x-r). an(x^n-r^n)+a(n-1)(x^(n-1)+r^(n-1))+....+a1(x-r)=0(mod x-r). This last phrase is trivially true by the next useful theorem: Theorem: If x=/=y and n>0 (natural number), then: x-y/x^n-y^n. We have shown that every such ai(x^i-r^i) in the sum is devided by x-r, which gives the whole sum is devided by x-r.[/QUOTE] No! You are mis-stating the problem. The proof of the correct proposition only takes 2 lines. |
[quote=R.D. Silverman;220900]This is totally wrong. You keep failinbg to check your work.
if e.g. x=7, then f(x) = 176, x-2 = 5, so f(x) = 1 mod x-2, yet you claim f(x) = 21 mod x-2. This is a totally incorrect statement of the problem. You need to prove that f(r) = the remainder when f(x) is divided by (x-r).[/quote] Do you mean: f(x)/(x-r)=f(r)? Or: f(x)-f(r) is always devided by x-r? |
[quote=blob100;220911]Do you say:
f(x)/(x-r)=f(r)?[/quote]No. The statement is that f(r) is the remainder ([B]not[/B] the quotient) when f(x) is divided by (x-r). [quote=blob100;220911] Or: f(x)-f(r) is always devided by x-r?[/quote]Yes, except that a native English writer would use "f(x)-f(r) is a multiple of (x-r)" or, perhaps, "f(x)-f(r) is divisible by (x-r)". In the second of these, the proviso "without remainder" is generally understood but would be used if complete clarity were required Paul |
[quote=xilman;220913]No. The statement is that f(r) is the remainder ([B]not[/B] the quotient) when f(x) is divided by (x-r).
Yes, except that a native English writer would use "f(x)-f(r) is a multiple of (x-r)" or, perhaps, "f(x)-f(r) is divisible by (x-r)". In the second of these, the proviso "without remainder" is generally understood but would be used if complete clarity were required Paul[/quote] This is what I tought. So, f(x)=f(r)(mod x-r). Proof: We would like to prove (x-r)|f(x)-f(r) where, f(x)=a_nx^n+a_(n-1)x^(n-1)+...+a_0. f(r)=a_nr^n+....+a_0. A={a_0,....,a_n} the set of the coefficients of f(x). Now, let's see the next equation: f(x)-f(r)=a_n(x^n-r^n)+a_(n-1)(x^(n-1)-r^(n-1))+....+a_1(x-r). To prove that f(x)-f(r) is divisible by x-r we will show a_n(x^n-r^n)+a_(n-1)(x^(n-1)-r^(n-1))+....+a_1(x-r)=0(mod x-r). I would like to state the next theorem: The next: z-y|z^b-y^b Takes place for all z=/=y, b natural numbers. The next is true: a_n(x^n-r^n)+a_(n-1)(x^(n-1)-r^(n-1))+....+a_1(x-r)=0(mod x-r) Becuase the last theorem. And we have: f(x)-f(r)=0(mod x-r). |
[QUOTE=blob100;220914]This is what I tought.
So, f(x)=f(r)(mod x-r). Proof: We would like to prove (x-r)|f(x)-f(r) where, f(x)=a_nx^n+a_(n-1)x^(n-1)+...+a_0. f(r)=a_nr^n+....+a_0. A={a_0,....,a_n} the set of the coefficients of f(x). Now, let's see the next equation: f(x)-f(r)=a_n(x^n-r^n)+a_(n-1)(x^(n-1)-r^(n-1))+....+a_1(x-r). To prove that f(x)-f(r) is divisible by x-r we will show a_n(x^n-r^n)+a_(n-1)(x^(n-1)-r^(n-1))+....+a_1(x-r)=0(mod x-r). I would like to state the next theorem: The next: z-y|z^b-y^b Takes place for all z=/=y, b natural numbers. The next is true: a_n(x^n-r^n)+a_(n-1)(x^(n-1)-r^(n-1))+....+a_1(x-r)=0(mod x-r) Becuase the last theorem. And we have: f(x)-f(r)=0(mod x-r).[/QUOTE] This works, but you are "hitting a thumbtack with a sledgehammer". The "proof from the book", ala P. Erdos takes only two lines. |
[quote=R.D. Silverman;220938]This works, but you are "hitting a thumbtack with a sledgehammer".
The "proof from the book", ala P. Erdos takes only two lines.[/quote] Here is a shorter proof. Proof: We define f(x) as a polynomial of degree n with, A={a0,...,an} the set of its coefficients. r is a constant. 1) We try to prove: f(x)=f(r)(mod x-r). This next is equivallent to (1): anx^n+...+a0=anr^n+...+a0(mod x-r), And is proved easily by the next theorem: The next: z-y|z^b-y^b Takes place for all z=/=y, b natural numbers. |
[quote=R.D. Silverman;218562](4) Prove the rational roots theorem:
If alpha = a/b is a rational root of f(x) then b divides a_n and a divides a_0. .[/quote] The rational roots theorem: If A=a/b (where (a,b)=1) a rational root of f(x) then b divides a_n and a divides a_0. Proof: B={a0,...,an} the coefficients of f(x). f(a/b)=an(a/b)[SUP]n[/SUP]+...+a0=0. We will multiplying each side by b[SUP]n[/SUP]. an(a[SUP]n[/SUP])+...+a0(b[SUP]n[/SUP])=0. And by simple algebra: a(an(a[sup]n-1[/sup])+a(n-1)(b*a[sup]n-2[/sup])+...+a1(b[sup]n-1[/sup])=-a0(b[sup]n[/sup]). b(a(n-1)(a[sup]n-1[/sup])+a(n-2)(b*a[sup]n-2[/sup])+...+a0(b[sup]n-1[/sup])=-an(a[sup]n[/sup]). These two phrases, each gives: a|a0b[sup]n[/sup], b|an(a[sup]n[/sup]) respectively. Becuase (a,b)=1 we have: a|a0, b|an. |
[QUOTE=blob100;220965]Here is a shorter proof.
Proof: We define f(x) as a polynomial of degree n with, A={a0,...,an} the set of its coefficients. r is a constant. 1) We try to prove: f(x)=f(r)(mod x-r). This next is equivallent to (1): anx^n+...+a0=anr^n+...+a0(mod x-r), And is proved easily by the next theorem: The next: z-y|z^b-y^b Takes place for all z=/=y, b natural numbers.[/QUOTE] Forget about working with ideals. A direct proof is much simpler. |
[quote=R.D. Silverman;220938]This works, but you are "hitting a thumbtack with a sledgehammer".
The "proof from the book", ala P. Erdos takes only two lines.[/quote]Tomer: what Bob says is true, but don't get discouraged. A valid proof you find for yourself is praiseworthy, and much better than one you merely copy out of a book, even though other proofs may be shorter and/or more elegant. For some theorems, there appears to be a sort of unofficial competition to find the largest number of different proofs. The proof that there are an infinite number of primes is a famous example. Paul |
[quote=xilman;220991]Tomer: what Bob says is true, but don't get discouraged. A valid proof you find for yourself is praiseworthy, and much better than one you merely copy out of a book, even though other proofs may be shorter and/or more elegant.
For some theorems, there appears to be a sort of unofficial competition to find the largest number of different proofs. The proof that there are an infinite number of primes is a famous example. Paul[/quote] I'm not discouraged. But I know I must learn how to make the shortest proof and make valid proofs. |
[quote=R.D. Silverman;220989]Forget about working with ideals. A direct proof is much simpler.[/quote]
To try proving it with another direction or to continue to the next problem? |
Hint: show that there is a polynomial [I]g[/I]([I]x[/I]) such that [I]x[/I][SUP][I]n[/I][/SUP] = ([I]x[/I]-[I]r[/I]) [I]g[/I]([I]x[/I]) + [I]r[/I][SUP][I]n[/I][/SUP].
|
[QUOTE=akruppa;221054]Hint: show that there is a polynomial [I]g[/I]([I]x[/I]) such that [I]x[/I][SUP][I]n[/I][/SUP] = ([I]x[/I]-[I]r[/I]) [I]g[/I]([I]x[/I]) + [I]r[/I][SUP][I]n[/I][/SUP].[/QUOTE]
This is not correct. Instead, put: f(x) = (x-r)g(x) + h(x). It is also true that h(x) is constant, but this info is not needed. i.e. simply factor (x-r) from f(x). |
I think it works with [TEX]g(x) = \sum_{i=0}^{n-1} r^{n-1-i} x^i.[/TEX]
Then [TEX](x-r)g(x) + r^n=[/TEX] [TEX]x \left(\sum_{i=0}^{n-1} r^{n-1-i} x^i\right) - r \left(\sum_{i=0}^{n-1} r^{n-1-i} x^i\right) + r^n=[/TEX] [TEX]\left(\sum_{i=0}^{n-1} r^{n-1-i} x^{i+1}\right) - \left(\sum_{i=0}^{n-1} r^{n-i} x^i\right) + r^n=[/TEX] [TEX]\left(\sum_{i=1}^{n} r^{n-i} x^{i}\right) - \left(\sum_{i=0}^{n-1} r^{n-i} x^i\right) + r^n=[/TEX] [TEX]x^n + \left(\sum_{i=1}^{n-1} r^{n-i} x^{i}\right) - \left(\sum_{i=1}^{n-1} r^{n-i} x^i\right) - r^n + r^n=x^n.[/TEX] If not, where did I make the error? |
[QUOTE=akruppa;221065]I think it works with [TEX]g(x) = \sum_{i=0}^{n-1} r^{n-1-i} x^i.[/TEX]
Then [TEX](x-r)g(x) + r^n=[/TEX] [TEX]x \left(\sum_{i=0}^{n-1} r^{n-1-i} x^i\right) - r \left(\sum_{i=0}^{n-1} r^{n-1-i} x^i\right) + r^n=[/TEX] [TEX]\left(\sum_{i=0}^{n-1} r^{n-1-i} x^{i+1}\right) - \left(\sum_{i=0}^{n-1} r^{n-i} x^i\right) + r^n=[/TEX] [TEX]\left(\sum_{i=1}^{n} r^{n-i} x^{i}\right) - \left(\sum_{i=0}^{n-1} r^{n-i} x^i\right) + r^n=[/TEX] [TEX]x^n + \left(\sum_{i=1}^{n-1} r^{n-i} x^{i}\right) - \left(\sum_{i=1}^{n-1} r^{n-i} x^i\right) - r^n + r^n=x^n.[/TEX] If not, where did I make the error?[/QUOTE] Look at the degree of the LHS and the degree of the remainder term. |
[quote=akruppa;221065]I think it works with [tex]g(x) = \sum_{i=0}^{n-1} r^{n-1-i} x^i.[/tex]
Then [tex](x-r)g(x) + r^n=[/tex] [tex]x \left(\sum_{i=0}^{n-1} r^{n-1-i} x^i\right) - r \left(\sum_{i=0}^{n-1} r^{n-1-i} x^i\right) + r^n=[/tex] [tex]\left(\sum_{i=0}^{n-1} r^{n-1-i} x^{i+1}\right) - \left(\sum_{i=0}^{n-1} r^{n-i} x^i\right) + r^n=[/tex] [tex]\left(\sum_{i=1}^{n} r^{n-i} x^{i}\right) - \left(\sum_{i=0}^{n-1} r^{n-i} x^i\right) + r^n=[/tex] [tex]x^n + \left(\sum_{i=1}^{n-1} r^{n-i} x^{i}\right) - \left(\sum_{i=1}^{n-1} r^{n-i} x^i\right) - r^n + r^n=x^n.[/tex] If not, where did I make the error?[/quote] Is this the easier proof? I think I gave a much simpler way to prove this theorem. |
[QUOTE=blob100;221142]Is this the easier proof? I think I gave a much simpler way to prove this theorem.[/QUOTE]
The proof takes two steps. (1) Put f(x) = (x-r) g(x) + r(x) where r(x) is the remainder after dividing by (x-r). Since (x-r) is linear and the degree of the remainder is less than the divisor, we have r(x) = constant, but this is not needed. (2) Put x = r yielding f(r) = r(r) = constant. QED. |
[quote=R.D. Silverman;221150]The proof takes two steps.
(1) Put f(x) = (x-r) g(x) + r(x) where r(x) is the remainder after dividing by (x-r). Since (x-r) is linear and the degree of the remainder is less than the divisor, we have r(x) = constant, but this is not needed. (2) Put x = r yielding f(r) = r(r) = constant. QED.[/quote] So I'm needed to prove that there is such g(x)? |
We try proving the next:
f(x)=(x-r)g(x)+f(r). Let's see f(x)-f(r) as a polynomial with k roots, We try proving it (the polynomial) has one root r which is equivallet to say it (the polynomial) equals g(x)(x-r) another polynomial. f(x)-f(r)=an(x^n-r^n)+...+a1(x-r). A={a0,...,an} as the set of all ocefficients of f(x). So the polynomial f(x)-f(r) has the root r. So it is easy to say there is a polynomial with k roots g(x) such that g(x)(x-r) equals f(x). |
[QUOTE=blob100;221152]So I'm needed to prove that there is such g(x)?[/QUOTE]
I thought that we had already discussed polynomial division. The existence of such a g(x) is simple. |
[quote=R.D. Silverman;221159]I thought that we had already discussed polynomial division. The
existence of such a g(x) is simple.[/quote] Of course, this is why I left this question... |
[quote=R.D. Silverman;221150]The proof takes two steps.
(1) Put f(x) = (x-r) g(x) + r(x) where r(x) is the remainder after dividing by (x-r). Since (x-r) is linear and the degree of the remainder is less than the divisor, we have r(x) = constant, but this is not needed. (2) Put x = r yielding f(r) = r(r) = constant. QED.[/quote] I want to understand one thing: Isn't the solution of the problem trivially true? I gave it three times... |
[quote=R.D. Silverman;218562](5) Prove that any polynomial of odd degree must have a real root.
This is easy with Calculus. Prove it without the Intermediate Value Thm. .[/quote] This theorem follows by the statement: every polynomial with a complex root a+bi is divisible (has the root) a-bi too. (a,b are too constants). So every polynomial must have 2m (m={0,1,2,3,...}) complex roots. So, by the fundamental theorem of algebra, such polynomial with 2m roots is of degree 2m. So an odd degreed polynomial must have at least one real root. |
| All times are UTC. The time now is 08:19. |
Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.