Problem Of The Week # 286 - Oct 24, 2017

[Ackbach]

Here is this week's POTW:

-----

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

-----

Remember to read the http://www.mathhelpboards.com/showthread.php?772-Problem-of-the-Week-%28POTW%29-Procedure-and-Guidelines to find out how to http://www.mathhelpboards.com/forms.php?do=form&fid=2!

 

[Ackbach]

No one answered this week's POTW, which was Problem B-4 of the 2014 Putnam Archive. The solution, attributed to Kiran Kedlaya and associates, follows.

[sp]Define the polynomial $\displaystyle f_n(x) = \sum_{k=0}^n 2^{k(n-k)} x^k$. Since
\[
f_1(x) = 1+x, f_2(x) = 1 + 2x + x^2 = (1+x)^2,
\]
the claim holds for for $n=1,2$. For $n \geq 3$, we show that the quantities
\[
f_n(-2^{-n}), f_n(-2^{-n+2}), \dots, f_n(-2^n)
\]
alternate in sign; by the intermediate value theorem, this will imply that $f_n$ has a root in each of the $n$ intervals $(- 2^{-n}, - 2^{-n+2}), \dots, (- 2^{n-2}, -2^n)$, forcing $f_n$ to have as many distinct real roots as its degree.

For $j \in \{0,\dots,n\}$, group the terms of $f_n(x)$ as
\begin{align*}
&\cdots \\
&+ 2^{(j-5)(n-j+5)} x^{j-5} + 2^{(j-4)(n-j+4)} x^{j-4} \\
&+ 2^{(j-3)(n-j+3)} x^{j-3} + 2^{(j-2)(n-j+2)} x^{j-2} \\
&+ 2^{(j-1)(n-j+1)} x^{j-1} + 2^{j(n-j)} x^j + 2^{(j+1)(n-j-1)} x^{j+1} \\
&+ 2^{(j+2)(n-j-2)} x^{j+2} + 2^{(j+3)(n-j-3)} x^{j+3} \\
&+2^{(j+4)(n-j-4)} x^{j+4} + 2^{(j+5)(n-j-5)} x^{j+5} \\
& \cdots.
\end{align*}
Depending on the parity of $j$ and of $n-j$, there may be a single monomial left on each end. When evaluating at $x =- 2^{-n+2j}$, the trinomial evaluates to $0$. In the binomials preceding the trinomial, the right-hand term dominates, so each of these binomials contributes with the sign of $x^{j-2k}$, which is $(-1)^j$. In the binomials following the trinomial, the left-hand term dominates, so again the contribution has sign $(-1)^j$.

Any monomials which are left over on the ends also contribute with sign $(-1)^j$. Since $n \geq 3$, there exists at least one contribution other than the trinomial, so $f_n(- 2^{-n+2j})$ has overall sign $(-1)^j$, proving the claimed alternation.[/sp]