TAOCP 5.4.2 Exercise 7
Let f_p(z)=z^p - z^{p-1}-\cdots-1.
Section 5.4.2: The Polyphase Merge
Exercise 7. [HM22] [HM22] Let ap be the dominant root of the polynomial f,(z) in exercise 5. What is the asymptotic behavior of ap, as p, oo?
Verified: no
Solve time: 1m10s
Solution
Let
$$ f_p(z)=z^p - z^{p-1}-\cdots-1. $$
Multiplying by $z-1$ gives
$$ (z-1)f_p(z)=z^{p+1}-2z^p+1. $$
The dominant root $a_p>1$ of $f_p$ is also the unique root $>1$ of
$$ z^{p+1}-2z^p+1=0, $$
since $z=1$ is not a root of $f_p$.
Rewriting,
$$ z^p(z-2)=-1, \qquad\text{hence}\qquad z^p(2-z)=1. $$
Set $z=2-\varepsilon$ with $\varepsilon>0$. Then
$$ (2-\varepsilon)^p \varepsilon = 1. $$
Taking logarithms yields
$$ p\ln(2-\varepsilon)+\ln \varepsilon=0. $$
Using the expansion
$$ \ln(2-\varepsilon)=\ln 2+\ln!\left(1-\frac{\varepsilon}{2}\right) =\ln 2-\frac{\varepsilon}{2}+O(\varepsilon^2), $$
substitution gives
$$ p\ln 2 - \frac{p\varepsilon}{2} + \ln \varepsilon + O(p\varepsilon^2)=0. $$
Since the equation $(2-\varepsilon)^p\varepsilon=1$ forces $\varepsilon\to 0$ and in fact $\varepsilon=O(2^{-p})$, the term $p\varepsilon^2$ is negligible compared with $p\varepsilon$. Hence
$$ \ln \varepsilon = -p\ln 2 + \frac{p\varepsilon}{2} + o(1). $$
Exponentiating,
$$ \varepsilon = 2^{-p} e^{p\varepsilon/2+o(1)}. $$
Since $p\varepsilon = p\cdot O(2^{-p}) \to 0$, the exponential factor satisfies
$$ e^{p\varepsilon/2+o(1)} = 1 + o(1), $$
so
$$ \varepsilon = 2^{-p}(1+o(1)). $$
Thus
$$ a_p = 2-\varepsilon = 2 - 2^{-p} + o(2^{-p}). $$
A sharper expansion follows by inserting $\varepsilon=2^{-p}+O(p2^{-2p})$ into $(2-\varepsilon)^p\varepsilon=1$, yielding a consistent correction term of order $p2^{-2p}$.
Hence
$$ a_p = 2 - 2^{-p} + O(p2^{-2p}). $$
$$ \boxed{a_p = 2 - 2^{-p} + O(p2^{-2p})} $$