Show all roots of $\sum_{k=0}^n 2^{k(n-k)} x^k$ are real (December 6, 2014 Putnam problem)

Show that for each positive integer n, all roots of the polynomial $\sum_{k=0}^n 2^{k(n-k)} x^k$ are real numbers.

I have no idea where to start.

From this year's Putnam, problem B4.

Let's define

$$ p_n(x) = \sum_{k=0}^n 2^{k(n-k)} x^k. $$

Since all its coefficients are positive, all roots of $p_n(x)$ must be negative. I'll start with some heuristics to try to explain the substitutions we'll make before actually proving the result.

We observe that $p_n(x/2^n)$ converges compactly to an entire function as $n \to \infty$, so presuming the limit function has at least one root we expect that the smallest root of $p_n(x/2^n)$ converges to a constant. That is to say, we expect the smallest root of $p_n(x)$ to behave like $c2^{-n}$.

We also calculate

$$ p_n(-2^{n+2}) = (-1)^n 2^{n^2} \sum_{k=0}^{n} (-1)^k 2^{-k^2} $$

and observe that $\DeclareMathOperator{sign}{\operatorname{sign}}\sign p_n(-2^{n+2}) = (-1)^n$, which is consistent with the largest root being greater than $-2^{n+2}$.

So we suppose that all of the roots of $p_n(x)$ satisfy

$$ -c_1 2^n < x < -c_2 2^{-n}, $$

and this motivates us to make the substitution $x = -2^y$. We are thus interested in the function

$$ q_n(y) = p_n(-2^y) = \sum_{k=0}^{n} (-1)^k 2^{k(y+n-k)}. $$

To show that all roots are real we will show that the quantity $q_n(2m-n)$, $m=0,1,\ldots,n$, changes sign for each $m$.

First we rearrange things a little to get

$$ q_n(2m-n) = (-1)^m 2^{m^2} \sum_{j=-m}^{n-m} (-1)^j 2^{-j^2}, $$

and we'll show that

$$ r_n(m) = \sum_{j=-m}^{n-m} (-1)^j 2^{-j^2} $$

is always positive. Note that $r_n(m) = r_n(n-m)$, so we only need to check all $m$ in the interval $0 \leq m \leq n/2$.

If $m=0$ then this is clear. If $m=1$ then we have

$$ r_n(1) = \sum_{j=2}^{n-1} (-1)^j 2^{-j^2} > 0 $$

as well. If $2 \leq m \leq n/2$ and $n \geq 4$ then

$$ r_n(m) = \frac{1}{8} + \sum_{\substack{-m\leq j\leq n-m \\ |j| > 2}} (-1)^j 2^{-j^2}, $$

and

$$ \begin{align} \left|\sum_{\substack{-m\leq j\leq n-m \\ |j| > 2}} (-1)^j 2^{-j^2}\right| &< 2\sum_{j=3}^{\infty} 2^{-k^2} \\ &< 2 \sum_{j=3}^{\infty} 2^{-3k} \\ &= \frac{1}{244}, \end{align} $$

so indeed $r_n(m) > 0$, as desired.

It just remains to check the cases $n=1,2,3$. Indeed, the polynomials are

$$ p_1(x) = 1+x, \\ p_2(x) = (1+x)^2, \\ p_3(x) = (1+x)(1+3x+x^2), $$

which all have only negative roots. This completes the proof.