# Showing that a root $x_0$ of a polynomial is bounded by $|x_0|<(n+1)\cdot c_{\rm max}/c_1$

I have doubts about the following problem (Problem 3.21 from Sipser's "Introduction to the Theory of Computation"):

Let $c_1 x^n + c_2 x^{n-1} + \cdots + c_n x + c_{n+1}$ be a polynomial with a root at $x=x_0$. Let $c_{\rm max}$ be the largest absolute value of a $c_i$. Show that

$$|x_0|<(n+1)\dfrac{c_{\rm max}}{c_1}.$$

Here is how I was able to approach it (I'm unsure that it's correct):

Making the polynomial equal zero (in this case, $x=x_0$):

$$c_1 x_0^n + c_2 x_0^{n-1} + \cdots + c_n x_0 + c_{n+1} = 0$$

Rearranging the terms:

$$c_1 x_0^n = -(c_2 x_0^{n-1} + \cdots + c_n x_0 + c_{n+1})$$

Taking the absolute value of both sides:

$$|c_1 x_0^n| = |c_2 x_0^{n-1} + \cdots + c_n x_0 + c_{n+1}|$$

Applying triangle inequality:

$$|c_1 x_0^n| \leq |c_2 x_0^{n-1}| + \cdots + |c_n x_0| + |c_{n+1}|$$

The inequality above still holds if we substitute $c_{max}$ for all coefficients:

$$|c_1 x_0^n| \leq |c_{max}| ( 1 + |x_0| + \cdots + |x_0^{n-1}| )$$

The inequality also holds if we substitute $n x_0^{n-1}$ for $1 + |x_0| + \cdots + |x_0^{n-1}|$ (because this sum has $n$ terms and $x_0^{n-1}$ is the largest one if $x_0>1$):

$$|c_1 x_0^n| \leq |c_{\rm max}| n |x_0^{n-1}|$$

$$|x_0| \leq n \dfrac{|c_{\rm max}|}{|c_1|}$$

From the above result, it is true that:

$$|x_0| < (n+1) \dfrac{|c_{\rm max}|}{|c_1|}$$

The above result is very close to the desired result, except that it should be $|x_0|<(n+1)\dfrac{c_{\rm max}}{c_1}$ (without the absolute bars).

Is this approach correct?

Edit: As pointed out in the comments, I also have to consider the case where $x_0\leq 1$.

If $x_0\leq 1$ then $\max(1, |x_0|,\cdots,|x_0|^{n-1}) = 1$, so $|c_1x_0^n|\leq |c_{\rm max}|n$, and $|x_0|\leq \left(n\dfrac{c_{\rm max}}{|c_1|}\right)^{1/n}$.

Since $c_{\rm max}\geq c_1$:

$|x_0| \leq \left(n\dfrac{c_{\rm max}}{|c_1|}\right)^{1/n}\leq n\dfrac{c_{\rm max}}{|c_1|} \leq (n+1) \dfrac{c_{\rm max}}{|c_1|}$.

Is this correct?

-
$x^{n-1}$ is only the largest term if $x>1$ – Ethan Jun 20 '13 at 12:10
@Ethan: I added this observation to the post. – anonymous Jun 20 '13 at 12:21
...Good, but you are supposed to treat also the case $x\leqslant1$, not simply mention that you assume $x\gt1$ (and this case $x\leqslant1$ is not difficult but is not done at present). – Did Jun 20 '13 at 12:40
@Did: I added an attempt for the case where $x_0\leq 1$. – anonymous Jun 20 '13 at 13:06
@anonymous Please do not use \dfrac, or other commands giving vertically verbose expressions, in question titles -- this is a policy to ensure that the scarce space on the main page is distributed evenly over the questions. See here for more information. Please take this into consideration for future questions. Thanks in advance. – Lord_Farin Jun 20 '13 at 13:23

Sipser's $c_{max}$ is by definition the absolute value. He forgot to mention that $c_1$ should be positive. Otherwise the inequality does not make sense.