0
$\begingroup$

Currently I studying analytic combinatorics and am looking at the OGF of integer compositions with summands restricted to the set $\{1,...,r\}$ for $r\geq2$: $$C^{\{1,...,r\}}(z) = \frac{1-z}{1-2z+z^{r+1}}.$$

In particular, $ z^{r+1} -2z + 1 $ has a unique zero $\rho_r \in (\frac{1}{2},1)$ of minimal magnitude so that by a later theorem the coefficients of the series expansion of the OGF are of the order $\rho_r^{-n}$. However, I am struggling to understand why we know such a zero exists. From complex analysis, I know that Rouche's theorem can be used to discern the amount and locations of the zeros to establish this. I tried using cases of odd and even $r$ to find functions to apply the theorem but am getting nowhere. How might Rouche's theorem or some other approach help us reach this fact?

$\endgroup$
1
  • $\begingroup$ Are you trying to prove that $z^{r+1} -2z + 1$ has a unique zero for $z$ a real in $(0.5, 1)$, or for $z$ a complex with $|z| \in (0.5, 1)$? $\endgroup$ Nov 19, 2022 at 21:48

1 Answer 1

2
$\begingroup$

We have$$z^{r+1}-2z+1=z(z^r-1)-(z-1)\\ =[z^r+z^{r-1}+\ldots +z-1](z-1)$$ The expression in the square brackets takes the value $r-1$ at $z=1$ and negative value at $z={1\over 2}.$ Therefore it vanishes in the interval $({1\over 2},1)$ by the intermediate value theorem. On the other hand for $|z|=1-\delta$ we have $2|z|=2(1-\delta)$ and $$|z^{r+1}+1|\le (1-\delta)^{r+1}+1\le (1-\delta)^3+1\\ =2-3\delta +3\delta^2-\delta^3<2(1-\delta)$$ for $\delta>0$ small enough. Then by the Rouche theorem the function $z^{r+1}-2z+1$ vanishes exactly once in $|z|<1.$

In conclusion the function vanishes only once for $|z|<1$ and the root is located in the interval $({1\over 2},1).$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .