Iranian Mathematical Olympiad

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{array}{rl}{P}_k(x)& =x{P}_{k-1}(x)+Q_k(x)\\ Q_k(x)& =x{Q}_{k-1}(x)+P_{k-1}(x).\end{array}$$ So $Q_k(x)=P_k(x)-x{P}_{k-1}(x)$ and therefore, $P_k(x)-x{P}_{k-1}(x)=x(P_{k-1}(x)-x{P}_{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^2{P}_{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}{ccccccccccc}x& -\infty & b_1& a_1& b_2& a_2& \cdots & b_{k-1}& a_{k-1}& b_k& +\infty \\ 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^2{P}_{k-1}(x)$, for the sign of $P_{k+1}$ in respective $b_i$'s we have $$\begin{array}{ccccccccccc}x& -\infty & b_1& a_1& b_2& a_2& \cdots & b_{k-1}& a_{k-1}& b_k& +\infty \\ 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^2{P}_{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$