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

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

• Numerics (using en.wikipedia.org/wiki/…) suggest the limit is suspiciously close to $e$. In particular, $a(10000)/a(9999) \approx 2.71605473$, while $a(1000)/a(999) \approx 2.71497203$. I suggest you try a generating function for an analytical result. Apr 1, 2021 at 12:44
• I'd bet it's an algebraic number Apr 1, 2021 at 15:29
• Where'd this problem come from, and what have you tried so far? Apr 1, 2021 at 19:21
• It arose when registering a succession in OEIS. I want to know if there is a systematic methodology to calculate these limits. oeis.org/draft/A342600 Apr 1, 2021 at 19:30

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.

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.

• so you are the author of the book you mention, right? Apr 2, 2021 at 4:55
• Yes, I am the author, with one collaborator on edition 1 (Mark Wilson) and a second collaborator added for the upcoming edition 2 (Steve Melczer). Apr 2, 2021 at 14:29
• hi @robinpemantle and welcome to MathOverflow! Apr 5, 2021 at 21:34

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}$$

• but calculating limit using this formula seems more difficult, is it easy? Apr 2, 2021 at 4:54
• There is an algebraic GF, but probably not very nice. Extraction of the diagonal of a bivariate generating function is spelled out in Stanley vol. 1, or see Pemantle-Wilson2013 page 39. There used to be a module in Macaulay2 to compute this, in the sense of computing a differential equation solved by this algebraic function (the annihilator in the Weyl algebra) but I doubt it still runs. Apr 2, 2021 at 14:26
• Also, because the signs are all the same in Alekseyev's formula, one can estimate it well by saddle point methods obtaining an expression up to a factor of 1 + o(1), from which the limiting ratio follows. Apr 2, 2021 at 14:27
• For the limit this gives$$\frac{1}{3} \left(\sqrt[3]{107+6\sqrt{318}}+\sqrt[3]{107-6\sqrt{318}}+2\right)\approx2.71618865899311$$ Apr 2, 2021 at 18:22
• Not sure if this any better but it is certainly shorter: the above horror equals$$\frac1{2 \left(1-2 y-2 y^2\right) \left(1-3 y-y^2\right)}\left(2-8 y+4 y^2+5 y^3-3y^3\frac{3-7 y-4 y^2}{\sqrt{1-2 y+y^2-8 y^3}}\right)$$ Apr 3, 2021 at 4:24