Exercise 2.1.4

[lshagiev]

How to "prove it using elementary means" and show that "there must be some input on which they disagree"?

[j2kun]

The question is:

Prove that two polynomial formulas with different degrees cannot be equal as functions. That is, there must be some input on which they disagree.

The second sentence is saying that "non equal functions" is defined to mean there are two inputs for which the functions have different outputs.

If f(x) and g(x) are polynomials of different degrees, suppose the degree of f is larger than the degree of g, then look at the polynomial (f-g)(x). If f and g are equal, then this polynomial must be zero. So if they are not equal, then you should be able to find an x for which (f-g)(x) is nonzero.

Can you prove that there is always such an x, using the fact that f and g have different degree? What would (f-g) look like, according to the definition of a polynomial? Can you use that to reason about what x would need to look like?

[lshagiev]

The question is:

Prove that two polynomial formulas with different degrees cannot be equal as functions. That is, there must be some input on which they disagree.

The second sentence is saying that "non equal functions" is defined to mean there are two inputs for which the functions have different outputs.

If f(x) and g(x) are polynomials of different degrees, suppose the degree of f is larger than the degree of g, then look at the polynomial (f-g)(x). If f and g are equal, then this polynomial must be zero. So if they are not equal, then you should be able to find an x for which (f-g)(x) is nonzero.

Can you prove that there is always such an x, using the fact that f and g have different degree? What would (f-g) look like, according to the definition of a polynomial? Can you use that to reason about what x would need to look like?

if m≠n (f-g) would look like: (f-g) = (a0 - b0) + (a1-b1)x + ... + (an-bn)x^n + ... + (am-bm)*x^m

m and n are both integers, so one of them is bigger than other, let m > n then (f-g) would look like: (f-g) = (a0 - b0) + (a1-b1)x + ... + (an-bn)x^n + (a(n+1) - b(n+1))x^n+1 + ... + (am-bm)x^m and also we understand that "an" can't be 0 and "bm" can't be 0.

If x = 0, then (f-g) is zero only if (a0-b0) also zero.

Here I got stuck and don't know how to show that there is another input where they can't be equal.

[j2kun]

Some good observations!

I think if f has a larger degree than g, then your second formula can be simplified a little bit:

(f-g) = (a0 - b0) + (a1-b1)*x + ... + (an-bn)*x^n + (a(n+1))*x^n+1 + ... + am*x^m

If g has degree n, then all of the b_i terms (from g) are zero after b_n.

Can you think of a way to exploit this extra observation to prove there is an input x for which (f-g) != 0 ? What is special about am*x^m that might enable this? I can give more hints or jump right to the solution if you still don't make any progress

[lshagiev]

Some good observations!

I think if f has a larger degree than g, then your second formula can be simplified a little bit:

(f-g) = (a0 - b0) + (a1-b1)*x + ... + (an-bn)*x^n + (a(n+1))*x^n+1 + ... + am*x^m

If g has degree n, then all of the b_i terms (from g) are zero after b_n.

Can you think of a way to exploit this extra observation to prove there is an input x for which (f-g) != 0 ? What is special about am*x^m that might enable this? I can give more hints or jump right to the solution if you still don't make any progress

I only see that amx^m can be 0, only if x is 0 and sum of all terms before amx^m can have maximum degree m-1 -- x^m-1

[j2kun]

One idea here is that am*x^m will grow much faster than the rest of the polynomial, for sufficiently large x. This is true of any nonzero polynomial, so you can think about this question as follows:

How large does x need to be in order for am*x^m > a{m-1}x^(m-1) + ... + a_1x + a_0 ?

Try playing around with some very large x (defined in terms of the other a_i) so as to make it easy to prove the left hand side is bigger than the right hand side for that special x.

[lshagiev]

One idea here is that am*x^m will grow much faster than the rest of the polynomial, for sufficiently large x. This is true of any nonzero polynomial, so you can think about this question as follows:

How large does x need to be in order for am*x^m > a{m-1}_x^(m-1) + ... + a_1_x + a_0 ?

Try playing around with some very large x (defined in terms of the other a_i) so as to make it easy to prove the left hand side is bigger than the right hand side for that special x.

So if x->∞ then right part is always bigger then left part? Is this only "elementary" proof?

[j2kun]

You don't need limits for this. I think you can come up with an x in terms of the coefficients and reason about the inequality, or use the fact that the polynomial has a limited number of roots, and pick a number bigger than the largest root.

On Sat, Mar 13, 2021, 9:26 PM lshagiev @.***> wrote:

One idea here is that am*x^m will grow much faster than the rest of the polynomial, for sufficiently large x. This is true of any nonzero polynomial, so you can think about this question as follows:

How large does x need to be in order for am*x^m > a{m-1}_x^(m-1) + ... + a_1_x + a_0 ?

Try playing around with some very large x (defined in terms of the other a_i) so as to make it easy to prove the left hand side is bigger than the right hand side for that special x.

So if x->∞ then right part is always bigger then left part? Is this only "elementary" proof?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/pim-book/exercises/issues/14#issuecomment-798835897, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS2PKXSAKFTBDIPBMCW3ZTTDRCJVANCNFSM4Y5RKEEQ .

[lshagiev]

Yes, but exercise says we should find that they are unequal as functions, but root is something related only to polynomials.

[j2kun]

I don't think that precludes the use of polynomial-specific facts. All the root is doing is helping you find an input and proving the two polynomials have different outputs when given that input.

If I ask you to prove two drinks, say tea and coffee, are different as liquids, the fact that they taste different is sufficient proof, even though you cannot drink all liquids (such as liquid nitrogen).

On Sun, Mar 14, 2021 at 11:54 AM lshagiev @.***> wrote:

You don't need limits for this. I think you can come up with an x in terms of the coefficients and reason about the inequality, or use the fact that the polynomial has a limited number of roots, and pick a number bigger than the largest root.

On Sat, Mar 13, 2021, 9:26 PM lshagiev @.***> wrote:

One idea here is that am*x^m will grow much faster than the rest of the polynomial, for sufficiently large x. This is true of any nonzero polynomial, so you can think about this question as follows:

How large does x need to be in order for am*x^m > a{m-1}_x^(m-1) + ... + a_1_x + a_0 ?

Try playing around with some very large x (defined in terms of the other a_i) so as to make it easy to prove the left hand side is bigger than the right hand side for that special x.

So if x->∞ then right part is always bigger then left part? Is this only "elementary" proof?

— You are receiving this because you commented. Reply to this email directly, view it on GitHub

14 (comment)

https://github.com/pim-book/exercises/issues/14#issuecomment-798835897, or unsubscribe

https://github.com/notifications/unsubscribe-auth/AAS2PKXSAKFTBDIPBMCW3ZTTDRCJVANCNFSM4Y5RKEEQ .

Yes, but exercise says we should find that they are unequal as functions, but root is something related only to polynomials.

— You are receiving this because you commented. Reply to this email directly, view it on GitHub https://github.com/pim-book/exercises/issues/14#issuecomment-798959455, or unsubscribe https://github.com/notifications/unsubscribe-auth/AAS2PKRD32G4UXGBHPQLL6TTDUA5PANCNFSM4Y5RKEEQ .

[lshagiev]

closed