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

Question

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...)$

Answer 1

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.

Answer 2

The value is close to $e$ but not. It's actually the positive real root of $p(t) := t^3 - 2t^2 + t - 8$. This is solvable via ACSV (see book by Pemantle and Wilson 2013). To summarize, the bivariate generating function is $1/Q := 1 / (1-xy-xy^2-2x^2y)$. The intersection of this in the positive quadrant with $xQ_x = yQ_y$ is a point $(x_0,y_0)$, where $\frac{1}{(x_0 y_0)}$ has minimal polynomial $p(t)$. Diagonal growth rate of $(x_0 y_0)^{-n}$ follows from some standard stuff. Happy to explain more if anyone is curious.

Answer 3

Here is a derivation for an explicit formula for $a(n)$.

The generating function for $f(m,n)$ is $$F(x,y) := \sum_{m,n\geq 0} f(m,n)x^m y^n = \big(1 + \frac{3x^2y^2}{1-xy(1+2x+y)}\big)\frac{1}{1-x}\frac{1}{1-y}.$$ It follows that \begin{split} a(n) &= 1 + \sum_{i,j=0}^n [x^iy^j]\ \frac{3x^2y^2}{1-xy(1+2x+y)} \\ &= 1 + 3\sum_{i,j=0}^{n-2} [x^iy^j]\ \frac{1}{1-xy(1+2x+y)} \\ &= 1 + 3\sum_{i,j=0}^{n-2} [x^iy^j]\ \sum_{k=0}^{n-2} x^ky^k(1+2x+y)^k \\ &= 1 + 3\sum_{k=0}^{n-2} \sum_{i,j=0}^{n-2-k} [x^iy^j]\ (1+2x+y)^k \\ &= 1 + 3\sum_{k=0}^{n-2} \sum_{i,j=0}^{n-2-k} \binom{k}{i,j,k-i-j} 2^i \\ &= 1 + 3\sum_{i,j=0}^{n-2} \binom{i+j}{i} 2^i \sum_{k=i+j}^{n-2-\max(i,j)} \binom{k}{i+j} \\ &= 1 + 3\sum_{i,j=0}^{n-2} \binom{i+j}{i}\binom{n-1-\max(i,j)}{i+j+1}2^i. \end{split}