HMMT February

Define $g(x)=2x^{2}-1$, so that $q(x)=-\frac{1}{2}+g(x+\frac{1}{2})$. Thus $q^{N}(x)=0 \Longleftrightarrow \frac{1}{2}=g^{N}(x+\frac{1}{2})$ where $N=2016$. But, viewed as function $g:[-1,1] \rightarrow[-1,1]$ we have that $g(x)=\cos(2 \arccos(x))$. Thus, the equation $q^{N}(x)=0$ is equivalent to $\cos(2^{2016} \arccos(x+\frac{1}{2}))=\frac{1}{2}$. Thus, the solutions for $x$ are $x=-\frac{1}{2}+\cos(\frac{\pi / 3+2 \pi n}{2^{2016}})$ for $n=0,1, \ldots, 2^{2016}-1$. So, the roots are negative for the values of $n$ such that $\frac{1}{3} \pi<\frac{\pi / 3+2 \pi n}{2^{2016}}<\frac{5}{3} \pi$ which is to say $\frac{1}{6}(2^{2016}-1)<n<\frac{1}{6}(5 \cdot 2^{2016}-1)$. The number of values of $n$ that fall in this range is $\frac{1}{6}(5 \cdot 2^{2016}-2)-\frac{1}{6}(2^{2016}+2)+1=\frac{1}{6}(4 \cdot 2^{2016}+2)=\frac{1}{3}(2^{2017}+1)$.