Intereting Posts

Why this space is homeomorphic to the plane?
Compute the trigonometric integrals
When an infinite union of countable sets is uncountable?
What is a method for determining the radius of a sphere from distances between points of right triangles on it?
Find max: $\frac{a}{b+2a}+\frac{b}{c+2b}+\frac{c}{a+2c}$
The series $\sum a_n$ is conditionally convergent. Prove that the series $\sum n^2 a_n$ is divergent.
Real Numbers to Irrational Powers
An example about finitely cogenerated modules
Triangle Quadrilateral and pentagon whose areas form a set of consecutive positive integers.
Can Hilbert (style) prove my tautology?
Let $G$ be a group, where $(ab)^3=a^3b^3$ and $(ab)^5=a^5b^5$. How to prove that $G$ is an abelian group?
continuous map on $\mathbb{R}$ which is the identity on $\mathbb{Q}$ is the identity map, hence Aut$(\mathbb{R}/\mathbb{Q})= 1.$
Twin primes of form $2^n+3$ and $2^n+5$
Prove that $\omega + \omega_1 = \omega \cdot \omega_1 = \omega^{\omega_1} = \omega_1$
Why spherical coordinates is not a covering?

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}.$$

- Properties of the greatest common divisor: $\gcd(a, b) = \gcd(a, b-a)$ and $\gcd(a, b) = \gcd(a, b \text{ mod } a)$
- Proving $ 1+\frac{1}{4}+\frac{1}{9}+\cdots+\frac{1}{n^2}\leq 2-\frac{1}{n}$ for all $n\geq 2$ by induction
- How many possibilities to arrange a rope of length $N$ between two points
- Prove $(n^5-n)$ is divisible by 5 by induction.
- Proving $(A\cup B)\cap(B\cup C)\cap(C\cup A)=(A\cap B)\cup (A\cap C)\cup (B\cap C)$?
- Solve recursion $a_{n}=ba_{n-1}+cd^{n-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?

- Show that $f_0 - f_1 + f_2 - \cdots - f_{2n-1} + f_{2n} = f_{2n-1} - 1$ when $n$ is a positive integer
- Cardinality of a set A is strictly less than the cardinality of the power set of A
- Make up a reasonable definition for the bipartite complement of a bipartite graph
- Visualizing Concepts in Mathematical Logic
- For polynomial $f$, does $f$(rational) = rational$^2$ always imply that $f(x) = g(x)^2$?
- Homogeneous polynomial in $k$ can factor into linear polynomials?
- Strong Mathematical Induction: Why More than One Base Case?
- Comparison trees
- How to “Re-write completing the square”: $x^2+x+1$
- How prove that polynomial has only real root.

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.

consider the polynomial -x^2 + 2*x – 1 . It has roots 1 and 1 .

Now here Xo = 1 , Cmax = 2 and C1= -1 ;

So the inequality doesn’t hold true here.

- Hatcher pg 187: Idea of Cohomology
- Evaluating a trigonometric integral by means of contour $\int_0^{\pi} \frac{\cos(4\theta)}{1+\cos^2(\theta)} d\theta$
- What do the cosets of $\mathbb{R} / \mathbb{Q}$ look like?
- dropping a particle into a vector field
- Can all real polynomials be factored into quadratic and linear factors?
- Is it wrong to use Binary Vector data in Cosine Similarity?
- Show that $ \{\lnot,\leftrightarrow\} $ is not functional complete
- Find all ring homomorphisms from $\Bbb Q$ to $\Bbb R$
- Proving $a^ab^b + a^bb^a \le 1$, given $a + b = 1$
- Prove that the set of positive rational values that are less than $ \sqrt{2}$ has no maximum value
- Why is $1 – \frac{1}{1 – \frac{1}{1 – \ldots}}$ not real?
- Show that $M = \{a + b\sqrt{2}\mid 5\mid a, 5 \mid b\}$ is a maximal ideal in $R = \mathbb{Z}$ and find $R/M$.
- Prove complements of independent events are independent.
- Proof of the Euler Generalisation of Fermat's Little Theorem using modular arithmetic
- Triple Integral $ \iiint\limits_S\frac1{\sqrt{\left(x-a\right)^{2}+\left(y-b\right)^{2}+\left(z-c\right)^{2}}}\;dx\;dy\;dz $