By induction, it is immediate that $a_{m,n}\le 2\min(m,n)$. In addition, when $m$ is fixed and $n>m$ we have $a_{m,n}=2m-P_m(n)/2^n$, where $P_m(x)$ is a polynomial of degree $m$, so $2m$ is an exponentially good bound. For $m=n$, it seems that $a_{n,n}=2n(1-1/\sqrt{\pi n}+o(1/\sqrt{n}))$, but I have not taken the time to prove it.
Henri Cohen
- 13.1k
- 1
- 34
- 62