11
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 1, 2021 at 12:44
  • 5
    $\begingroup$ I'd bet it's an algebraic number $\endgroup$ Apr 1, 2021 at 15:29
  • 1
    $\begingroup$ Where'd this problem come from, and what have you tried so far? $\endgroup$ Apr 1, 2021 at 19:21
  • 2
    $\begingroup$ 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 $\endgroup$ Apr 1, 2021 at 19:30

3 Answers 3

9
$\begingroup$

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.

$\endgroup$
37
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ so you are the author of the book you mention, right? $\endgroup$
    – vidyarthi
    Apr 2, 2021 at 4:55
  • $\begingroup$ 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). $\endgroup$ Apr 2, 2021 at 14:29
  • 4
    $\begingroup$ hi @robinpemantle and welcome to MathOverflow! $\endgroup$ Apr 5, 2021 at 21:34
7
$\begingroup$

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}

$\endgroup$
7
  • 2
    $\begingroup$ but calculating limit using this formula seems more difficult, is it easy? $\endgroup$
    – vidyarthi
    Apr 2, 2021 at 4:54
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 2, 2021 at 14:26
  • 2
    $\begingroup$ 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. $\endgroup$ Apr 2, 2021 at 14:27
  • 3
    $\begingroup$ 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$$ $\endgroup$ Apr 2, 2021 at 18:22
  • 3
    $\begingroup$ 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)$$ $\endgroup$ Apr 3, 2021 at 4:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.