1. ## 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

2. Originally Posted by CaptainBlack
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

3. Originally Posted by topsquark
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

4. Originally Posted by CaptainBlack
But f(x) = x^2 + 0.0001*x + 1 does not have real roots.

RonL
Ahhhhhh! I get it now!

-Dan

5. 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)

6. Originally Posted by spanner
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

7. Originally Posted by CaptainBlack
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

8. 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.]

9. Originally Posted by slobone
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.]

RonL

10. 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.]

11. 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...

12. Originally Posted by CaptainBlack
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.

13. Originally Posted by ecMathGeek
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.
Originally Posted by slobone
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!

14. Originally Posted by CaptainBlack
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

15. Originally Posted by CaptainBlack
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?

Page 1 of 2 12 Last