Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
$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
add comment

1 Answer

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.

share|improve this answer
    
Seems a comment, more than an answer. –  enzotib Jun 20 '13 at 13:34
1  
OP presented a solution and was wondering about the difference between their solution (with absolute values) and the expected answer (without absolute values). I pointed out that in fact the answer without the absolute values is incorrect. –  user72694 Jun 20 '13 at 13:39
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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