Page 1 of 2 12 LastLast
Results 1 to 15 of 18

Math Help - Problem 21

  1. #1
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4

    Problem 21

    Let the polynomial:

    f(x) = x^n + a_1 x^{n-1} + ... + a_{n-1} x +1

    with non-negative real coefficients a_1, .. , a_{n-1} have n real roots.

    Prove that f(2) >= 3^n

    RonL
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    332
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    Let the polynomial:

    f(x) = x^n + a_1 x^{n-1} + ... + a_{n-1} x +1

    with non-negative real coefficients a_1, .. , a_{n-1} have n real roots.

    Prove that f(2) >= 3^n

    RonL
    No, I still have a contradiction.

    Let
    f(x) = x^2 + 0.0001*x + 1

    Then
    f(2) = 4 + 0.0001*2 + 1 = 5.0002
    which is not greater than or equal to 3^2 = 9.

    -Dan
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by topsquark View Post
    No, I still have a contradiction.

    Let
    f(x) = x^2 + 0.0001*x + 1

    Then
    f(2) = 4 + 0.0001*2 + 1 = 5.0002
    which is not greater than or equal to 3^2 = 9.

    -Dan
    But f(x) = x^2 + 0.0001*x + 1 does not have real roots.

    RonL
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Forum Admin topsquark's Avatar
    Joined
    Jan 2006
    From
    Wellsville, NY
    Posts
    9,927
    Thanks
    332
    Awards
    1
    Quote Originally Posted by CaptainBlack View Post
    But f(x) = x^2 + 0.0001*x + 1 does not have real roots.

    RonL
    Ahhhhhh! I get it now!

    -Dan
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Mar 2007
    Posts
    7
    the simplest polinomial is
    x squared

    then the lowest by your definition would be:
    p(x) x squared + 1

    make x = 1

    P(1) = 1 squared + 1
    P(2) = 2 squared + 1
    = 5

    this maybe wrong.

    p.s how do u post a graph (i have a problem but i don't know how to post a graph to ask the question) (its polynomial numbers)
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by spanner View Post
    the simplest polinomial is
    x squared

    then the lowest by your definition would be:
    p(x) x squared + 1

    make x = 1

    P(1) = 1 squared + 1
    P(2) = 2 squared + 1
    = 5

    this maybe wrong.

    p.s how do u post a graph (i have a problem but i don't know how to post a graph to ask the question) (its polynomial numbers)
    This polynomial again like topsquarks has no real roots.

    RonL
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    Let the polynomial:

    f(x) = x^n + a_1 x^{n-1} + ... + a_{n-1} x +1

    with non-negative real coefficients a_1, .. , a_{n-1} have n real roots.

    Prove that f(2) >= 3^n

    RonL
    A simple example of a polynomial satisfying the conditions of this problem is:

    f(x) = (x+1)^2 = x^2 + 2x +1

    where n=2, and f(2) = 9 = 3^2 <= 3^2

    as expected.

    RonL
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Newbie slobone's Avatar
    Joined
    Mar 2007
    Posts
    9
    POSSIBLE OUTLINE OF PROOF

    We can also write

    f(x) = (x-r_1)(x-r_2)...(x-r_n)

    (because f is monic) where r_1, r_2, ..., r_n are the n real roots.

    Step 1: show that each of the r_i must be <= 0.

    Proof by contradiction: For convenience, arrange the subscripts so that r_1 >= r_2 >=...>= r_n. By assumption, r_1 > 0.

    If r_1 > r_2, let x be such that r_1 > x > r_2. Then exactly one of (x-r_1), (x-r_2),... (x-r_n) is < 0, so f(x) < 0, contradiction.

    If r_1 = r_2, we have a problem. We could keep going down the list of roots until we find a number that's less than an odd number of the roots, but what if there isn't any such number? That is, r_1 = r_2, r_3 = r_4, and so on, and n is even. In this case I don't know what to do -- perhaps you could make some kind of combinatorial argument using the binomial theorem to show that if all the coefficients are positive, all the roots must be negative.

    Step 2. Let's make a notational switch and define R_j = ABS (r_j) [absolute value]. Then f(2) = (2+R_1)(2+R_2)...(2+R_n), where all the R's are positive. Since the constant term of f is 1, it follows that

    R_1R_2...R_n = 1.

    I believe that for any set of R_j's with this property, it must be true that f(2) >= 3^n.

    For example, (2 + 1/3)(2 + 1/2)(2 + 6) = 280/6 > 3^3.

    Unfortunately this is the hard part of the proof.

    [I apologize if my notation is horrific, but I'm not used to doing math on the Internet.]
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by slobone View Post
    POSSIBLE OUTLINE OF PROOF

    We can also write

    f(x) = (x-r_1)(x-r_2)...(x-r_n)

    (because f is monic) where r_1, r_2, ..., r_n are the n real roots.

    Step 1: show that each of the r_i must be <= 0.

    Proof by contradiction: For convenience, arrange the subscripts so that r_1 >= r_2 >=...>= r_n. By assumption, r_1 > 0.

    If r_1 > r_2, let x be such that r_1 > x > r_2. Then exactly one of (x-r_1), (x-r_2),... (x-r_n) is < 0, so f(x) < 0, contradiction.

    If r_1 = r_2, we have a problem. We could keep going down the list of roots until we find a number that's less than an odd number of the roots, but what if there isn't any such number? That is, r_1 = r_2, r_3 = r_4, and so on, and n is even. In this case I don't know what to do -- perhaps you could make some kind of combinatorial argument using the binomial theorem to show that if all the coefficients are positive, all the roots must be negative.

    Step 2. Let's make a notational switch and define R_j = ABS (r_j) [absolute value]. Then f(2) = (2+R_1)(2+R_2)...(2+R_n), where all the R's are positive. Since the constant term of f is 1, it follows that

    R_1R_2...R_n = 1.

    I believe that for any set of R_j's with this property, it must be true that f(2) >= 3^n.

    For example, (2 + 1/3)(2 + 1/2)(2 + 6) = 280/6 > 3^3.

    Unfortunately this is the hard part of the proof.

    [I apologize if my notation is horrific, but I'm not used to doing math on the Internet.]
    Not bad

    RonL
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie slobone's Avatar
    Joined
    Mar 2007
    Posts
    9
    Just to illustrate with the case of n = 2. Then we have

    (2 + a)(2 + 1/a) = 5 + 2(a + 1/a)

    But a + 1/a >= 2 for all positive real a, so f(2) >= 9.

    [If a + 1/a < 2 and a>0, then a^2 -2a +1 < 0, (a - 1)^2 < 0, which isn't possible.]
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Newbie slobone's Avatar
    Joined
    Mar 2007
    Posts
    9
    CaptainBlack, could you post the solution? I seem to be the only one working on it, and I've more or less given up.

    I'm sure there's a 3-line solution that's going to have me slapping my forehead...
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by CaptainBlack View Post
    Let the polynomial:

    f(x) = x^n + a_1 x^{n-1} + ... + a_{n-1} x +1

    with non-negative real coefficients a_1, .. , a_{n-1} have n real roots.

    Prove that f(2) >= 3^n

    RonL
    Prove inductively:

    First, show it is true for the first term: n = 1
    f(2) = 2^(1) + 1 = 3 >= 3^(1) = 3

    Now, assume it is true for some value: n = k
    f(2) = 2^k + a_1*2^(k-1) + ... + a_{k-1}*2 + 1 >= 3^k

    Show that it is true for the next term: n = k + 1
    f(2) = 2^(k+1) + a_1*2^k + ... + a_{k}*2 + 1 >= 3^(k+1)

    We have:
    2^(k+1) + a_1*2^k + ... + a_{k}*2 + 1
    = 2*[2^k + a_1*2^(k-1) + ... + a_{k-1}*2 + a_{k}] + 1


    It just occurred to me that I can go no futher until I know how to use the fact that there are n real roots. I know that is important to the proof (because it limits the values of a_1 to a_n), so I need to figure out how that effects the problem before I can go on.
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by ecMathGeek View Post
    It just occurred to me that I can go no futher until I know how to use the fact that there are n real roots. I know that is important to the proof (because it limits the values of a_1 to a_n), so I need to figure out how that effects the problem before I can go on.
    Quote Originally Posted by slobone View Post
    POSSIBLE OUTLINE OF PROOF

    We can also write

    f(x) = (x-r_1)(x-r_2)...(x-r_n)
    I'll take an approach similar to slobone:

    Let f(x) = (x + r_1)(x + r_2)*...*(x + r_{n-1})(x + r_n)
    Where r_1*r_2*...*r_n = 1

    Now, I'll try proving it inductively:

    First, show it is true for the first term: n = 1, which means r_1 = 1
    f(2) = (2 + 1) = 3 >= 3^1 = 3

    Now, assume it is true for some term: n = k
    f(2) = (2 + r_1)(2 + r_2)*...*(2 + r_k) >= 3^k
    Where r_1*r_2*...*r_k = 1

    Show that it works for the next term: n = k + 1
    f(2) = (2 + r_1)(2 + r_2)*...*(2 + r_k)(2 + r_{k+1}) >= 3^(k+1)

    Recall that r_1*r_2*...*r_k = 1, but r_1*r_2*...*r_k*r_{k+1} MUST also equal 1, so r_{k+1} MUST equal 1.

    Therefore, we have:
    (2 + r_1)(2 + r_2)*...*(2 + r_k)(2 + 1) >= 3^k*(2 + 1) = 3*3^k = 3^(k+1)

    Q.E.D.

    --------------------------------------------------------------------------------------------------------------------------------

    Notes:

    The coefficient of all the "x" terms in f(x) MUST be 1 (or MUST multiply to equal one - but the way I set up this proof allowed for me to avoid this) because the original polynomial form of f(x) began with 1*x^n, so the expansion of the factored form of f(x) must have the same. Note also that r_1 through r_n take care of the coefficients of the constants, a_1 through a_{n-1}, of the remaining "x"s in the expanded form.

    In the factored form of f(x), the product of the roots, r_1*r_2*...*r_n, MUST equal 1 because the constant term of the polynomial form of f(x) was 1, and so expanding the factored form of f(x) MUST also result in a constant term of 1.

    I LOVE INDUCTIVE PROOFS!
    Last edited by ecMathGeek; May 10th 2007 at 11:56 AM.
    Follow Math Help Forum on Facebook and Google+

  14. #14
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    Quote Originally Posted by CaptainBlack View Post
    Let the polynomial:

    f(x) = x^n + a_1 x^{n-1} + ... + a_{n-1} x +1

    with non-negative real coefficients a_1, .. , a_{n-1} have n real roots.

    Prove that f(2) >= 3^n

    RonL
    As f(x)>0 for all x>=0 all roots are negative. Let these be -b1, -b2, .. -bn,
    with all the b's >0.

    Then:

    f(x) =(x+b1)(x+b2) ..(x+bn)

    Also as the constant term is 1 we know that b1.b2. .. bn = 1.

    Now 2 + bk = 1 + 1 + bk >= 3 cuberoot(1.1.bk), by the Arithmetic-Geometric
    mean inequality. So (2+bk) >= 3cuberoot(bk)

    So for x=2:

    f(2) = (2+b1)(2+b2) ...(2+bn) >= 3^n cuberoot(b1.b2. .. bn) = 3^n

    RonL
    Follow Math Help Forum on Facebook and Google+

  15. #15
    Senior Member ecMathGeek's Avatar
    Joined
    Mar 2007
    Posts
    436
    Quote Originally Posted by CaptainBlack View Post
    As f(x)>0 for all x>=0 all roots are negative. Let these be -b1, -b2, .. -bn,
    with all the b's >0.

    Then:

    f(x) =(x+b1)(x+b2) ..(x+bn)

    Also as the constant term is 1 we know that b1.b2. .. bn = 1.

    Now 2 + bk = 1 + 1 + bk >= 3 cuberoot(1.1.bk), by the Arithmetic-Geometric
    mean inequality. So (2+bk) >= 3cuberoot(bk)

    So for x=2:

    f(2) = (2+b1)(2+b2) ...(2+bn) >= 3^n cuberoot(b1.b2. .. bn) = 3^n

    RonL
    Was my proof wrong?
    Follow Math Help Forum on Facebook and Google+

Page 1 of 2 12 LastLast

Search Tags


/mathhelpforum @mathhelpforum