Problem 2088

Let $Q_k(x) = \sum_{i=0}^{k} a(i, 2k - 2i)x^i$. According to the recurrence relation for $a(m, n)$, we get
$$\begin{align*} P_k(x) &= xP_{k-1}(x) + Q_k(x) \\ Q_k(x) &= xQ_{k-1}(x) + P_{k-1}(x). \end{align*}$$
So $Q_k(x) = P_k(x) - xP_{k-1}(x)$ and therefore, $P_k(x) - xP_{k-1}(x) = x(P_{k-1}(x) - xP_{k-1}(x)) + P_{k-1}(x)$. Finally, we get
$$P_k(x) = (2x + 1)P_{k-1}(x) - x^2 P_{k-1}(x).$$
Hence we get a recurrence relation for $P_{k+1}(x)$ where $k \ge 2$, $P_1(x) = 3x + 1$ and $P_2(x) = 5x^2 + 5x + 1$.

Claim. For each positive integer $k \ge 2$ all of the roots of $P_k(x)$ and $P_{k-1}(x)$ are real and distinct. Furthermore, if $a_1 < a_2 < \cdots < a_{k-1}$ and $b_1 < b_2 < \cdots < b_k$ are roots of $P_{k-1}$ and $P_k$, respectively, we have
$$b_1 < a_1 < b_2 < a_2 < \cdots < a_{k-1} < b_k.$$
Proof. We proceed by induction. For the base case $k = 2$, $-\frac{1}{3}$ is the only root of $P_1$ and $P_2(-\frac{1}{3}) < 0$ so $-\frac{1}{3}$ lies between the two roots of $P_2(x)$.
Suppose that $P_{k-1}(x)$ and $P_k(x)$ satisfy the induction hypothesis. We know $P_{k+1}(x) = (2x+1)P_k(x) - x^2P_{k-1}(x)$. Now, we consider the signs of $P_k$ and $P_{k-1}$ on different real numbers. First suppose that $k$ is even.
$$\begin{array}{c|cccccccccc} x & -\infty & b_1 & a_1 & b_2 & a_2 & \cdots & b_{k-1} & a_{k-1} & b_k & +\infty \\ \hline P_k & + & 0 & - & 0 & + & \cdots & 0 & - & 0 & + \\ x^2 P_{k-1} & - & - & 0 & + & 0 & \cdots & - & 0 & + & + \end{array}$$
Since $P_{k+1}(x) = (2x+1)P_k(x) - x^2P_{k-1}(x)$, for the sign of $P_{k+1}$ in respective $b_i$'s we have
$$\begin{array}{c|cccccccccc} x & -\infty & b_1 & a_1 & b_2 & a_2 & \cdots & b_{k-1} & a_{k-1} & b_k & +\infty \\ \hline P_{k+1} & - & + & - & - & - & \cdots & + & - & - & + \end{array}$$
According to the change of signs of $P_{k+1}(x)$ and by the Mean Value Theorem, for each $1 \le i \le k-1$, $P_{k+1}$ has a root between $b_i$ and $b_{i+1}$. Also, it has one root less than $b_1$ and one root greater than $b_k$, which completes the proof for even values of $k$. The case where $k$ is an odd number is similar, the only difference being the signs of $b_1$ and $-\infty$.

Note that
(i) $0$ is not a root of any of the $P_k$'s. Because $P_k(0) = a(0, 2k+1) = 1$, $P_{k-1}(x)$ and $x^2P_{k-1}(x)$ have the same sign.
(ii) The coefficient of $x^k$ in $P_k(x)$ equals $a(2k, 1) > 0$, so $P_k(+\infty) > 0$ and the sign of $P_k(-\infty)$ is related to the parity of $k$. $\square$