# Why $\lim_{n\rightarrow \infty}\frac{F(n,n)}{F(n-1,n-1)} =\frac{9}{8}$?

$$F(m,n)= \begin{cases} 1, & \text{if m n=0 }; \\ \frac{1}{2} F(m ,n-1) + \frac{1}{3} F(m-1,n )+ \frac{1}{4} F(m-1,n-1), & \text{ if m n>0. }% \end{cases}$$

$$\lim_{n\rightarrow \infty}\frac{F(n,n)}{F(n-1,n-1)} =\lim_{n\rightarrow \infty}\frac{F(n,n-1)}{F(n-1,n-1)}=\frac{9}{8}$$

$$\lim_{n\rightarrow \infty}\frac{F(n-1,n)}{F(n-1,n-1)}=1$$

• @robinpemantle Here Robin Pemantle's standard theory does not work Apr 22, 2021 at 20:04
• This should lead to a straightforward polynomial equation for the generating function that would let you determine coefficients explicitly, unless there's something that I'm missing... Apr 22, 2021 at 20:27
• $$J(x,y)=-\frac{x y}{4}-\frac{x}{2}-\frac{y}{3}+1$$ $$J(x,y)=0\land x J^{(1,0)}(x,y)=y J^{(0,1)}(x,y)$$ $$\left\{x=\frac{2}{3} \left(\sqrt{10}-2\right),y=\sqrt{10}-2\right\}$$ $$\frac{1}{x y}=\frac{1}{12} \left(7+2 \sqrt{10}\right)=1.11038 ...$$ Apr 22, 2021 at 20:42
• If I'm doing my generatingfunctionology right then the GF satisfies $f(w,z) = \frac1{1-w}+\frac1{1-z}-1+\frac z2f(w,z) + \frac w3 f(w,z) + \frac{zw}4 f(w,z)$; I suspect that gives a very different result than what you claim there. Apr 22, 2021 at 21:42
• @StevenStadnicki I was just computing the generating function, and I got something slightly different for the last three summands. Apr 22, 2021 at 22:00

We will compute the generating function, and use the method described in section 2 of this paper.

Let $$F_{m,n}=F(m,n)$$. Consider the generating function $$G(x,y)=\sum_{m=0}^\infty\sum_{n=0}^\infty F_{m,n}x^my^n.$$ Then the recurrence gives \begin{align*} &G(x,y)=\sum_{m=0}^\infty F_{m,0}x^m+\sum_{n=1}^\infty F_{0,n}y^n+\sum_{m=1}^\infty\sum_{n=1}^\infty F_{m,n}x^my^n\\ &=\frac{1}{1-x}+\frac{y}{1-y}+\sum_{m=1}^\infty\sum_{n=1}^\infty\left(\frac{1}{2}F_{m,n-1}+\frac{1}{3}F_{m-1,n}+\frac{1}{4}F_{m-1,n-1}\right)x^my^n\\ &=\frac{1-xy}{(1-x)(1-y)}+\frac{y}{2}\sum_{m=1}^\infty\sum_{n=0}^\infty F_{m,n}x^my^n+\frac{x}{3}\sum_{m=0}^\infty\sum_{n=1}^\infty F_{m,n}x^my^n+\frac{xy}{4}G(x,y)\\ &=\frac{1-xy}{(1-x)(1-y)}+\frac{y}{2}\left(G(x,y)-\frac{1}{1-y}\right)+\frac{x}{3}\left(G(x,y)-\frac{1}{1-x}\right)+\frac{xy}{4}G(x,y)\\ &=\frac{1-xy-\frac{y}{2}(1-x)-\frac{x}{3}(1-y)}{(1-x)(1-y)}+\left(\frac{x}{3}+\frac{y}{2}+\frac{xy}{4}\right)G(x,y)\\ &=\frac{1-\frac{x}{3}-\frac{y}{2}-\frac{xy}{6}}{(1-x)(1-y)}+\left(\frac{x}{3}+\frac{y}{2}+\frac{xy}{4}\right)G(x,y). \end{align*} Solving for $$G(x,y)$$ gives $$G(x,y)=\frac{1-\frac{x}{3}-\frac{y}{2}-\frac{xy}{6}}{(1-x)(1-y)\left(1-\frac{x}{3}-\frac{y}{2}-\frac{xy}{4}\right)}.$$ Let $$R(x,y)$$ denote this rational function. We have shown that $$G(x,y)$$ converges to $$R(x,y)$$ in some neighborhood of the origin. Then for fixed small $$x$$, the Laurent series $$G(x/y,y)$$ will converge to $$R(x/y,y)$$ in some annulus around $$y=0$$. Furthermore, $$H(x)=\sum_{m=0}^\infty F_{m,m}x^m$$ is the constant term of $$G(x/y,y)$$, and can be found via residue calculus as \begin{align*} H(x)&=\frac{1}{2\pi i}\int_\gamma\frac{1}{y}G(x/y,y)\,dy\\ &=\frac{1}{2\pi i}\int_\gamma\frac{1}{y}R(x/y,y)\,dy\\ &=\sum_k\mathrm{Res}\left[\frac{1}{y}R(x/y,y),y=z_k\right] \end{align*} where $$\gamma$$ is a counterclockwise contour in the annulus, and where $$z_k$$ are the singularities of $$R(x/y,y)$$ lying inside of $$\gamma$$. We can compute \begin{align*} \frac{1}{y}R(x/y,y)&=\frac{y-\frac{x}{3}-\frac{y^2}{2}-\frac{xy}{6}}{(y-x)(1-y)\left(y-\frac{x}{3}-\frac{y^2}{2}-\frac{xy}{4}\right)}. \end{align*} This rational function has poles at the following points:

• $$y=1$$. This pole does not lie inside of $$\gamma$$.

• $$y=x$$. This pole lies inside of $$\gamma$$, and has residue $$\frac{8}{8-9x}$$.

• $$y=(1-\frac{x}{4})+\sqrt{(\frac{x}{4}-1)^2-\frac{2}{3}x}$$. This pole does not lie inside of $$\gamma$$.

• $$y=(1-\frac{x}{4})-\sqrt{(\frac{x}{4}-1)^2-\frac{2}{3}x}$$. This pole lies inside of $$\gamma$$, and has residue $$\frac{\frac{x}{12}\left((1-\frac{x}{4})-\sqrt{(\frac{x}{4}-1)^2-\frac{2}{3}x}\right)}{\left((1-\frac{5x}{4})-\sqrt{(\frac{x}{4}-1)^2-\frac{2}{3}x}\right)\left(\frac{x}{4}+\sqrt{(\frac{x}{4}-1)^2-\frac{2}{3}x}\right)\left(\sqrt{(\frac{x}{4}-1)^2-\frac{2}{3}x}\right)}$$ which Wolfram Alpha can simplify to $$\frac{x\left(13\sqrt3\,x-12\sqrt3+\sqrt{3x^2-56x+48}\right)}{(7x-6)(9x-8)\sqrt{3x^2-56x+48}}.$$

Putting this all together gives $$H(x)=\frac{8}{8-9x}+\frac{x\left(13\sqrt3\,x-12\sqrt3+\sqrt{3x^2-56x+48}\right)}{(7x-6)(9x-8)\sqrt{3x^2-56x+48}}.$$ The second summand is actually holomorphic at $$x=6/7$$ and $$x=8/9$$. Then the singularity of $$H(x)$$ closest to the origin is $$x=8/9$$, and we obtain the asymptotic $$F_{m,m}\sim\left(\frac{9}{8}\right)^m$$ which proves the first limit.

The remaining limits can be solved in a similar way, by first determining the asymptotics of $$F(m,m-1)$$ and $$F(m-1,m)$$.