# Proving all roots of a sequence of polynomials are real

Let the sequence of polyominoes $R_n(z)$ be defined as follows for $n\geqslant1$: $$R_n(z)\;= \;\sum_{r=0}^{\lfloor\frac{n-1}{2}\rfloor} \tbinom{n}{2r+1}(4z)^r.$$ I would like to prove that all the roots of $R_n(z)$ are real (and thus negative since the coefficients are all positive). Perhaps there's some way of getting the result by using Sturm’s theorem, but that seems too computationally intensive to be practical. Also, Kurtz’s condition on the coefficients only holds for small $n$.

Any ideas?

In case it helps, $R_n(z)$ satisfies the following recurrence: \begin{align*} R_1(z)&\;=\;1 \\ R_2(z)&\;=\;2 \\ R_n(z)&\;=\;2R_{n-1}(z)+(4z-1)R_{n-2}(z)\qquad \text{for } n>2, \end{align*} and also has the following closed form: $$R_n(z)\;=\;\frac{(1+2\sqrt{z})^n-(1-2\sqrt{z})^n}{4\sqrt{z}}.$$ Thanks.

-
These look like close relatives of the Chebyshev polynomials. –  André Nicolas Jul 11 '12 at 15:58

Due to your closed form, every root of $R_n$ must satisfy $(1+2\sqrt z)^n=(1-2\sqrt z)^n$. But that requires that $|1+2\sqrt z|=|1-2\sqrt z|$ which can't be true if $\sqrt z$ has nonzero real part. So $\sqrt z$ is pure imaginary, which is only possible if $z$ itself is a negative real.

-
Thanks. I spent so much time focussing on the coefficients of the polynomials that I completely missed that the closed form gave me what I wanted very easily. –  David Bevan Jul 12 '12 at 8:48

A more direct approach would be to find the $\lfloor\frac{n-1}{2}\rfloor$ distinct real roots.

Indeed, the real roots can be enumerated as:

$$z=-\frac{\tan^2 \frac{\pi k}{n}}{4}$$

$k=1,2,...,\lfloor\frac{n-1}{2}\rfloor$.

That gives us the requisite number of distinct roots, so it gives us all the roots.

You can show these are roots by showing that $(1+2\sqrt{z})^n$ is real for each of these $z$, and thus must be equal to $(1-2\sqrt{z})^n$.

-

An idea: Assuming it is correct, your last formula gives us for a root $\,w\,$ of $\,R_n(z)\,$: $$0=R_n(w)=\frac{(1+2\sqrt w)^n-(1-2\sqrt w)^n}{4\sqrt w}\Longleftrightarrow \left(\frac{1+2\sqrt w}{1-2\sqrt w}\right)^n=1\Longleftrightarrow$$ $$\Longleftrightarrow \frac{1+2\sqrt w}{1-2\sqrt w}=e^{2k \pi i/n}\,\,,\,k=0,1,2,...,n-1 \Longrightarrow$$ $$\Longrightarrow\,\, \text{putting }\,\,\zeta:=e^{\frac{2k\pi i}{n}}\,\,,\,\text {we get}\,\,\frac{1+2\sqrt w}{1-2\sqrt w}=\zeta\Longrightarrow$$ $$\Longrightarrow \sqrt w=\frac{\zeta -1}{2(\zeta +1)}=\frac{2i\operatorname{Im}(\zeta)}{2|\zeta+1|^2}\Longrightarrow w=(\sqrt w)^2\in\Bbb R$$ as with any purely imaginary complex number.

-
I think the last line should actually read $$\sqrt w=\frac{\zeta -1}{2(\zeta +1)}=\frac{(\zeta -1)(\bar{\zeta} +1)}{2(\zeta +1)(\bar{\zeta} +1)}=\frac{i\operatorname{Im}(\zeta)}{2(\operatorname{Re}(\zeta)+1)}$$ –  David Bevan Jul 12 '12 at 13:06
As with any complex number $\,z\,\,,\,z\overline z=|z|^2\,$ , thus$$(\zeta+1)\overline{(\zeta+1)}=(\zeta +1)(\overline\zeta +1)=|\zeta +1|^2$$ –  DonAntonio Jul 12 '12 at 13:23

Let $z$ be a complex root of $R_n$ and let $\sqrt z$ denote a fixed square root of $z$. Then $$\frac{(1+2\sqrt{z})^n - (1-2\sqrt{z})^n}{4\sqrt{z}} = 0.$$ We can assume $z \neq 0$, hence $$(1+2\sqrt{z})^n = (1-2\sqrt{z})^n.$$ Now there is an $n$th root of unity $\zeta$ s.t. $$1+2\sqrt{z} = \zeta (1-2\sqrt{z}).$$ Solve for $\sqrt{z}$ to find $$\sqrt{z} = \frac{\zeta-1}{2(\zeta+1)},$$ thus $$z = \frac{(\zeta-1)^2}{4(\zeta+1)^2}.$$ Now consider the complex conjugation of $z$. Since $1 = |\zeta|^2 = \zeta \overline \zeta$, we have $\overline \zeta = \zeta^{-1}$ and $$\overline z = \frac{(\zeta^{-1}-1)^2}{4(\zeta^{-1}+1)^2} = \frac{(1-\zeta)^2}{4(1+\zeta)^2} = \frac{(\zeta-1)^2}{4(\zeta+1)^2} = z.$$ Since $z$ is fixed by complex conjugation it has to be an real number.

-