, 2016

Solution:
Define $g(x) = 2x^{2} - 1$, so that $q(x) = -\frac{1}{2} + g\left(x + \frac{1}{2}\right)$. Thus
$$q^{N}(x) = 0 \Longleftrightarrow \frac{1}{2} = g^{N}\left(x + \frac{1}{2}\right)$$
where $N = 2016$.
But, viewed as function $g : [-1, 1] \to [-1, 1]$ we have that $g(x) = \cos(2 \arccos(x))$. Thus, the equation $q^{N}(x) = 0$ is equivalent to
$$\cos\left(2^{2016} \arccos\left(x + \frac{1}{2}\right)\right) = \frac{1}{2}$$
Thus, the solutions for $x$ are
$$x = -\frac{1}{2} + \cos\left(\frac{\pi/3 + 2\pi n}{2^{2016}}\right) \quad 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}\left(2^{2016} - 1\right) < n < \frac{1}{6}\left(5 \cdot 2^{2016} - 1\right)$$
The number of values of $n$ that fall in this range is $\frac{1}{6}\left(5 \cdot 2^{2016} - 2\right) - \frac{1}{6}\left(2^{2016} + 2\right) + 1 = \frac{1}{6}\left(4 \cdot 2^{2016} + 2\right) = \frac{1}{3}\left(2^{2017} + 1\right)$.