Return to Answer

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.

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.

Added: numerically $$a_{n,n}=2n(1-1/\sqrt{\pi n}+1/(8\sqrt{\pi n^3})-1/(128\sqrt{\pi n^5})+...)$$

Looks like a well-known expansion, probably in Knuth vol 1.

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/\sqrt{\pi n}+o(1/\sqrt{n})$, but I have not taken the time to prove it.

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.

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 would be interesting to investigate if $a_{n,n}/n$ tends to $2$ and if yes, at what speed.

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/\sqrt{\pi n}+o(1/\sqrt{n})$, but I have not taken the time to prove it.