1
$\begingroup$

I'm currently a high school Pre-Calculus student and my textbook presents the following theorem without proof:

Let $f(x)$ be a polynomial with real coefficients and a positive leading coefficient.

Let $a \geq 0$. Then, if when $f(x)$ is divided by $x-a$, all of the coefficients of the quotient and the remainder are non-negative, $a$ is an upper bound on the real zeroes of $f(x)$.

Now, let $a \leq 0$. Then, if when $f(x)$ is divided by $x-a$, all of the coefficients of the quotient and the remainder alternate between non-positive and non-negative, $a$ is a lower bound on the real zeroes of $f(x)$.

I am trying to find a proof for this theorem and I think I found a proof for it pages 6 and 7 of this PDF file. However, the proof does not seem correct:

[...] since all of $q(x)$'s remaining coefficients are positive [...]

This is a quote from the proof of the first part of this theorem. Here, $q(x)$ is the resulting polynomial from dividing $f(x)$ by $x-b$ for some root $b$ for $f(x)$. However, there is a clear counter example to this: If $a=5$ and $f(x)=x^2-5x+6$, then $f(x)$ and $a$ meet the hypothesis since $\frac{f(x)}{x-a}=x+0+\frac{6}{x-a}$, so there are all non-negative coefficients in the quotient and the remainder. Then, $b=3$ is a root of $f(x)$, but, $q(x)=\frac{f(x)}{x-b}=x-2$ does not have all positive coefficients, contradicting the above.

The proof of the second part of the theorem is also wrong:

Because $a < 0$ and the leading term in $q(x)$ has a positive coefficient, the constant term in $q(x)$ has the same sign as $q(a)$.

However, if we let $a=-4$ and $f(x)=x^2+3x+2$, then $f(x)$ and $a$ meet the hypothesis since $\frac{f(x)}{x-a}=x-1+\frac{6}{x-a}$, which alternatives between non-negative and non-positive coefficients in the quotient and remainder. Then, $b=2$ is a root of $f(x)$, but $q(x)=\frac{f(x)}{x-b}=x+1$ and thus $q(a)=-3$ while the constant term of $q(x)$ is $1$, which also clearly contradicts the above.

Thus, while I have found proofs for these theorems, I do not think they are valid. Could someone show me valid proofs for these theorems in my Pre-Calc textbook? Thank you!

$\endgroup$
2
$\begingroup$

Proof of Upper Bound Theorem:

Let $f(x)=q(x)*(x-a)+r$. It is given that all of the coefficients of $q(x)$ and $r$ are non-negative. Factoring out a $x-a$ from the right side of the equation yields $f(x)=(x-a)(q(x)+\frac{r}{x-a})$ for all $x \neq a$. Now, let $c > a$. Note that $c$ is positive since $a$ is non-negative. We will prove that $f(c) \neq 0$, which will prove the theorem by showing that $f(c)=0$ implies $c \leq a$ and thus $a$ is an upper bound on all zeroes of $f(c)$.

We have already shown that $f(c)=(c-a)(q(c)+\frac{r}{c-a})$. Since $c \neq a$, $c-a \neq 0$ and thus $q(c)+\frac{r}{c-a} \neq 0$ implies $f(c) \neq 0$. Therefore, we will prove that $q(c)+\frac{r}{c-a} \neq 0$. $q(x)=\sum_{i=0}^{n-1}q_i*x^i$ where $q_i$ are the non-negative coefficients of $q(x)$ and $n$ is the degree of $f(x)$. Since $c$ is positive, $c^i$ is also positive for any $i \in \mathbb{N}$ and thus, since $q_i$ is non-negative, $q_i*c^i$ is non-negative. As the sum of non-negative numbers are non-negative and $q(c)$ is the sum of all $q_i*c^i$ for $i \in \mathbb{N}$, $q(c)$ is non-negative. Also, since $c > a$, $c-a$ is positive and thus, since $r$ is non-negative, $\frac{r}{c-a}$ is non-negative.

Therefore, since both $q(c)$ and $\frac{r}{c-a}$ are non-negative, the only way their sum could be $0$ is if both of them are $0$. However, if both $q(c)$ is $0$, then all of the coefficients of $q(x)$ are $0$, meaning $q(x)=0$. Also, if $\frac{r}{c-a}=0$, since $c-a$ is positive, $r=0$. If both $q(x)$ and $r$ are $0$, since $f(x)=q(x)*(x-a)+r$, $f(x)=0$. However, $f(x) \neq 0$ since it has a leading positive coefficient. Therefore, $q(c)+\frac{r}{c-a} \neq 0$ because otherwise, $f(x)$ would not have a leading positive coefficient. Thus, we have proven the theorem.

Proof of Lower Bound Theorem:

Let $f(x)=q(x)*(x-a)+r$ and $q(x)=\sum_{i=0}^{n-1}q_i*x^i$ where $q_i$ are the coefficients of $q(x)$ and $n$ is the degree of $f(x)$. Since $f(x)$ has a positive leading coefficient, $q(x)$ must have a non-negative leading coefficient and thus $q_{n-1} \geq 0$. Also, let $c < a$. Note that $c$ is negative since $a$ is non-positive. We can use the argument from the previous theorem to show that all we need to prove is that $q(c)+\frac{r}{c-a} \neq 0$ in order to prove the whole theorem. We will now split this proof up into two cases: $n$ is odd and $n$ is even.

Case 1: $n$ is Odd

If $n$ is odd, then $n-1$ is even and since all of the coefficients alternate between non-negative and non-positive, all of the coefficients of even powers of $x$ must be the same sign as $q_{n-1}$, or non-negative, and all of the coefficients of odd powers of $x$ must be the opposite sign as $q_{n-1}$, or non-positive. Let $i \in \mathbb{N}$. If $i$ is odd, then $q_i$ is non-positive, as we have just shown, and since $c$ is negative, $c^i$ is negative, so $q_i*c^i$ is non-negative. Otherwise, $i$ is even, so $q_i$ is non-negative and $c^i$ is positive, making $q_i*c^i$ still non-negative. Thus, since the sum of non-negative numbers is non-negative and $q(c)=\sum_{i=0}^{n-1}q_i*c^i$, $q(c)$ is non-negative.

Also, since $q_0$ is non-negative (as $0$ is even) and $r$ alternates in sign with $q_0$, $r$ is non-positive. Since $c < a$, $c-a$ is negative. Therefore, $\frac{r}{c-a}$ is non-negative.

Thus, we have shown that $q(c)$ and $\frac{r}{c-a}$ are both non-negative, meaning $q(c)+\frac{r}{c-a}=0$ only if $q(c)=0$ and $\frac{r}{c-a}=0$. However, we have already shown in the argument of the above theorem that this contradicts $f(x)$'s positive leading coefficient. Therefore, $q(c)+\frac{r}{c-a} \neq 0$, proving the theorem for this case.

Case 2: $n$ is Even

The proof of this case is very similar to the proof of Case 1. Simply switch "odd" with "even" and "positive" with "negative" from the proof of the previous case (except where it says "If $i$ is odd", "since $c$ is negative, $c^i$ is negative", "Otherwise, $i$ is even", "$c^i$ is positive", and "because $0$ is even") to prove this new case.

Thus, since we have proven both cases of this theorem, we have proven the whole theorem.

$\endgroup$
  • $\begingroup$ Re upper bound: Maybe there's something basic I'm missing, but if the degree of $f$ is more than one, and $f(x)=(x-a)q(x)$ plus terms of lower degree than $f(x)$, then how can the leading coefficient of $f(x)$ be positive and that of $q(x)$ be non-positive? $\endgroup$ – ForgotALot Jan 31 '16 at 1:52
  • $\begingroup$ @ForgotALot If the degree of $f(x)$ is at least $1$, then the leading coefficient of $q(x)$ must be positive since the leading coefficient of $f(x)$ is positive. However, it is not given that $f(x)$ is not a constant. This proof shows the theorem is true even if $f(x)$ is a non-zero constant (which is obvious, since constants have no zeroes and thus all numbers are upper and lower bounds) without making a separate case to prove the theorem is true for non-constants and constants. $\endgroup$ – Noble Mushtak Jan 31 '16 at 1:59
  • $\begingroup$ Sorry, I relied on the OP's version of the problem which said the coefficients of $q(x)$ are non-positive. What you have proved assumes them to be non-negative, which I guess was the correct statement of the problem. Thanks. $\endgroup$ – ForgotALot Jan 31 '16 at 2:06
0
$\begingroup$

Here's what I think is a more intuitive proof.

For the first part:

Suppose that $f(x)/(x-a)$ leaves only non-negative coefficients. So $f(x)=(x-a)q(x)+r(x)$. But by the definition of polynomial division, $\deg q>\deg r$. Since $q$ is linear but not the zero polynomial, $r(x)$ is a constant polynomial - let this constant be $r$. Then $f(x)=(x-a)q(x)+r$. Now suppose that $b>a$. Then $f(b)=(b-a)q(b)+r$. Here, $q(x)$ and $b-a$ are positive by definition and $r$ is non-negative. Hence $f(b)>0$, showing that $b$ is not a root of $f$.

A similar argument that invokes the upper bound theorem completes the lower bound proof.

$\endgroup$
  • $\begingroup$ Why is $q(x)$ linear? If $f(x)$ is a cubic, then $q(x)$ could be a quadratic. Also, this proof is suspect because it never uses the fact that $a \geq 0$, which is necessary in order for the theorem to be true. $\endgroup$ – Noble Mushtak Oct 20 '18 at 17:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.