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.
 A: 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.
