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

Question

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?

Answer 1

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.

Answer 2

The question asker is either using an older edition of Sipser's book or is misquoting it. In the third edition, the inequality is

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

where "$c_\rm{max}$ is the largest absolute value of a $c_i$". Hence, there is no error.