Indeed one of the most beautiful problems I've seen recently. For solving it, consider polynomial $Q_k(x)$ to be: $Q_k(x) = \sum_{i=0}^{k}a(i, 2k-2i)x^i$, Then, one can easily see that the relations $P_k(x)=xP_{k-1}(x)+Q_k(x)$ $Q_k(x)=xQ_{k-1}(x)+P_{k-1}(x)$ hold for $k \ge 1$. Thus, we can conclude that $P_k(x)=(2x+1)P_{k-1}(x)-x^2P_{k-2}(x)$ for each $k \ge 2$. Now using the fact that $P_1(x) = 1+3x$ and $P_2(x) = 1+5x+5x^2$, we can prove by induction that $P_k(x)$ changes it's sign on $0$ and roots of $P_{k-1}(x)$ alternatively. (It can also be proved that all these roots are negative numbers). Hence we conclude that $P_k(x)$ has $k$ real roots for each natural number $k$.

@Mahan

$a(n,m)+a(n-2,m)=2a(n-1,m)+(a(n,m)-a(n-1,m)-a(n-1,m)+a(n-2,m))$ $a(n,m)+a(n-2,m)=2a(n-1,m)+a(n,m-1)-a(n-1,m-1)=2a(n-1,m)+a(n,m-2)$ $a(n,m)=2a(n-1,m)+a(n,m-1)-a(n-1,m-1)=2a(n-1,m)+a(n,m-2)-a(n-2,m)$----(*) Now so taking $n=i,m=2k+1-2i$ basically we get, $\sum x^ia(i,2k+1-2i)=\sum (2x+1)(2a(i-1,2k+1-2i)x^{i-1}+a(i,2k+1-2i))-\sum x^2a(i-2,2k+1-i)x^{i-2}$ So finally we get $P_k(x)=(2x+1)P_{k-1}(x)-x^2P_{k-2}(x)$. Now note $P_{k+1}(x)P_{k-1}(x)<P_{k}(x)$ So $P_k(a)=0\implies P_{k+1}(x)P_{k-1}(x)<0$ , now so just applying induction with help of behavior of the pair $P_k(x),P_{k-1}(x)$ we'll be able to locate the location of roots $P_{k+1}(x)$ and those are between two consecutive roots of $P_k(x)=0$ and also one roots is between zero and minimum root of $P_{k-1}(x)=0$, thus we get there are at least $k$ roots of $P_{k+1}(x)=0$ and so that has exactly $k+1$ roots.

@goodarz

Proposed by Morteza Saghafian