# 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.

• Can you edit your question so that the numbers of open and close parens are equal? Also, perhaps change the title to "show all root are real". And can you please put lower and upper limits on your sum? Otherwise, we can't really give a confident answer, since we don't know what polynomial you're talking about. – John Hughes Dec 6 '14 at 21:46
• Sorry, made changes – user198136 Dec 6 '14 at 21:54
• This is a problem from today's Putnam exam, should this be indicated? (The exam is over, but it would be nice to know.) – Lukas Geyer Dec 7 '14 at 0:59
• Sorry, made the edit – user198136 Dec 7 '14 at 17:51

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.

• I know this is a little rough in some places so if you think anything can be clarified please let me know. – Antonio Vargas Dec 8 '14 at 0:22
• The following observations might be useful: $p_{n+1}(x)=p_{n}(2x)+x^{n+1}$. $p(2x)$ has the same number of roots as $p(n)$, and if it can be shown that $p(2x) +x^{n+1}$ has the same number of roots as $p(2x)$ except for an additional most negative root due to the change in direction as $x\to\infty$, it would answer the question. Also possibly helpful, The polynomials $p(x)$ have palindromic coefficient sequences, so their roots come in pairs $r>r'$ for which $r\cdot r'=1$, with an additional root $r=-1$ when $n$ is odd. Thus is suffices to count the roots for which $r<-1$. – Steve Kass Dec 15 '14 at 5:57