Let $a(n) = f(n,n)$ where $f(m,n) = 1$ if $m < 2 $ or $ n < 2$ and $f(m,n) = f(m-1,n-1) + f(m-1,n-2) + 2 f(m-2,n-1)$ otherwise.


What is the limit of $a(n + 1) / a (n)$? $(2.71...)$



What is the limit of $a (n + 1) / a (n)$?
Decided to do a separate answer as there is a subtle point involved which is not mentioned in my comments to the answer by @Max


Starting from the generating function by Max Alexeyev
$$
\sum\_{m,n\geqslant0}f(m,n)x^my^n=\frac1{(1-x)(1-y)}\left(1+\frac{3x^2y^2}{1-xy(1+2x+y)}\right)
$$
we need to find the generating function for $F(t):=\sum f(n,n)t^n$. It can be done, as mentioned by @robinpemantle, using the method of residues, and this gives
$$
F(t)=\frac1{2(1-2t-2t^2)(1-3t-t^2)}\left(2-8t+4t^2+5t^3-3t^3\frac{3-7t-4t^2}{\sqrt{1-2t+t^2-8t^3}}\right).
$$
The subtle point here is that the apparent poles at the roots of $1-2t-2t^2$ and $1-3t-t^2$ (respectively, $\approx.366025$ and $\approx.302776$) are closer to the origin than the 2-branching pole at the root of $1-2t+t^2-8t^3$ ($\approx.36816293915706916$). However it turns out that these poles are actually cancelled out by zeros. To see this, observe that
$$
2-8t+4t^2+5t^3-3t^3\frac{3-7t-4t^2}{\sqrt{1-2t+t^2-8t^3}}=0
$$
happens when
$$
R(t):=1-2t+t^2-8t^3-\left(3t^3\frac{3-7t-4t^2}{2-8t+4t^2+5t^3}\right)^2
$$
is zero. But
$$
R(t)=\left(\frac2{2-8t+4t^2+5t^3}\right)^2(1-2t-2t^2)(1-3t-t^2)(1-5t+9t^2-15t^3+26t^4-16t^5-18t^6)$$
so that $R(t)$ vanishes at the roots of $1-2t-2t^2$ and $1-3t-t^2$ (to be entirely rigorous, one has to check that these do not have common roots with $2-8t+4t^2+5t^3$, which can be checked e. g. by looking at resultants).


Thus the singularity of $F(t)$ nearest to the origin is the root of $1-2t+t^2-8t^3$ with smallest absolute value, so that the leading asymptotics is given by the root of $x^3-2x^2+x-8$ with largest absolute value (as in the answer by Robin Pemantle), i. e.
$$
\frac{1}{3} \left(\sqrt[3]{107+6 \sqrt{318}}+\sqrt[3]{107-6 \sqrt{318}}+2\right)\approx2.7161886589931057
$$


**PS**


As, judging by upvotes (thanks!) this answer seems to attract some attention, I decided to re-check it still more carefully, and it seems that that subtle issue is not actually fully exhausted in this answer.


Not to repeat lengthy expressions, let me abbreviate $F(t)=(1/P)(A-B/\sqrt Q)$ (where $P$, $Q$, $A$, $B$ are polynomials in $t$). I claimed something like that if $P=0$, then $A-B/\sqrt Q=0$, and this is actually not true. What is true is that if $P=0$, then $A^2-B^2/Q=0$. Now $P$ has four roots (all real), of which only two are relevant (meaning that of the four only these two are closer to the origin than the smallest root of $Q$, which might influence the final answer). What actually happens is that in the vicinity of all four $Q$ is positive, and, denoting by $\sqrt Q$ the positive square root of $Q$ there, $A+B/\sqrt Q$ vanishes at the irrelevant roots of $P$, while $A-B/\sqrt Q$ vanishes at the relevant ones. And this requires additional analysis. I just now checked numerically that $A+B/\sqrt Q$ is away from zero at both relevant roots, which suffices after one knows about $A^2-B^2/Q$ rigorously. I can supply more detailed explanation if anybody requests it.


