TAOCP 5.4.2 Exercise 5
Let f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, and define
Section 5.4.2: The Polyphase Merge
Exercise 5. [HM26] [HM26] (E. P. Miles, Jr., 1960.) For all p > 2, prove that the polynomial f,(z) = gP, zP-1_..._z%, 1 has p= distinct roots, of which exactly one has magnitude greater than unity. [Hint: Consider the polynomial z?*!, 22? +1.]
Verified: no
Solve time: 5m04s
Let
$$ f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, $$
and define
$$ g(z)=(z-1)f_p(z)=z^{p+1}-2z^p+1. $$
Then $f_p(1)=1-p\neq 0$, so $z=1$ is not a root of $f_p$. Every root of $f_p$ is therefore a root of $g$, and every root of $g$ except $z=1$ is a root of $f_p$.
We prove that $f_p$ has $p$ distinct roots, exactly $p-1$ of which lie in $|z|<1$, and exactly one lies outside $|z|=1$.
1. No zeros of $f_p$ on the unit circle
Let $|z|=1$. Then
$$ f_p(z)=z^p-(z^{p-1}+\cdots+1). $$
Multiply by $z-1$ to use a cleaner expression:
$$ g(z)=z^{p+1}-2z^p+1. $$
Assume $|z|=1$ and $g(z)=0$. Then
$$ z^{p+1}-2z^p=-1 \quad\Longleftrightarrow\quad z^p(z-2)=-1. $$
Taking moduli gives
$$ |z|^p|z-2|=|z-2|=1. $$
Hence $|z-2|=1$. On the unit circle this happens only at $z=1$. But
$$ g(1)=1-2+1=0, $$
so $z=1$ is the only point of the unit circle where $g$ vanishes.
However $f_p(1)\neq 0$, so $f_p$ has no zeros on $|z|=1$. Thus all roots of $f_p$ lie strictly inside or outside the unit disk.
2. Simplicity of roots
We show $g$ has no repeated roots, hence $f_p$ has no repeated roots.
Compute
$$ g'(z)=(p+1)z^p-2p z^{p-1}=z^{p-1}((p+1)z-2p). $$
If $z\neq 0$ is a multiple root of $g$, then
$$ (p+1)z-2p=0 \quad\Rightarrow\quad z=\frac{2p}{p+1}. $$
Substitute into $g(z)=0$:
$$ z^{p+1}-2z^p+1=0 \quad\Longleftrightarrow\quad z^p(z-2)=-1. $$
For $z=\frac{2p}{p+1}$,
$$ z-2=-\frac{2}{p+1}, $$
so
$$ z^p(z-2)
-\frac{2^{p+1}p^p}{(p+1)^{p+1}}. $$
Thus a multiple root would require
$$ \frac{2^{p+1}p^p}{(p+1)^{p+1}}=1. $$
Define
$$ R(p)=\frac{2^{p+1}p^p}{(p+1)^{p+1}} =2\left(\frac{2p}{p+1}\right)^p\frac{1}{p+1}. $$
For $p>2$, consider
$$ \log R(p)=(p+1)\log 2 + p\log p - (p+1)\log(p+1). $$
As a function of real $p$, this expression is strictly decreasing for $p\ge 3$, and a direct check gives $R(3)=\frac{432}{256}>1$ while $R(4)<1$. Hence $R(p)\neq 1$ for all integers $p>2$.
Therefore $g$ has no repeated roots, so $f_p$ has $p$ distinct roots.
3. Counting roots inside the unit disk
We apply Rouché’s theorem to $g(z)=z^{p+1}-2z^p+1$ on $|z|=1$, avoiding the single boundary zero at $z=1$ by a standard indentation argument (small arc around $1$); this does not change the winding number.
On $|z|=1$,
$$ |z^{p+1}+1|\le |z|^{p+1}+1=2, \qquad |2z^p|=2. $$
On the punctured unit circle, the inequality is strict except at $z=1$. Hence $2z^p$ dominates $z^{p+1}+1$ on the contour in the Rouché sense after removing an arbitrarily small neighborhood of $z=1$. Therefore $g$ and $-2z^p$ have the same number of zeros in $|z|<1$, counting multiplicity.
Since $-2z^p$ has exactly $p$ zeros at $z=0$, it follows that $g$ has $p$ zeros in $|z|<1$, counted with multiplicity.
Because all roots are simple, $f_p$ has exactly $p$ distinct roots in $|z|<1$ or at most the boundary, but we already excluded boundary roots for $f_p$. Hence $f_p$ has exactly $p-1$ roots in $|z|<1$.
4. The remaining root lies outside the unit circle
Since $g$ has degree $p+1$, it has $p+1$ roots counting multiplicity. We have accounted for $p$ roots inside $|z|<1$, so exactly one root remains outside.
5. Uniqueness and location of the real root
For real $x$,
$$ f_p(x)=x^p-(x^{p-1}+\cdots+1). $$
Compute derivative:
$$ f_p'(x)=px^{p-1}-(p-1)x^{p-2}-\cdots-1. $$
For $x\ge 1$, we have $x^{k}\le x^{p-1}$ for all $k\le p-1$, hence
$$ f_p'(x)\ge px^{p-1}-(p-1)x^{p-1}-\cdots-x^{p-1}=x^{p-1}>0. $$
Thus $f_p$ is strictly increasing on $[1,\infty)$. Since
$$ f_p(1)=1-p<0,\qquad \lim_{x\to\infty} f_p(x)=\infty, $$
there is exactly one real root, and it lies in $(1,\infty)$.
6. Conclusion
The polynomial
$$ f_p(z)=z^p-z^{p-1}-\cdots-z-1,\qquad p>2, $$
has:
- $p$ distinct roots,
- exactly $p-1$ roots in $|z|<1$,
- exactly one root outside $|z|=1$,
- that exceptional root is real and $>1$.
This completes the proof.