About the sequence $s_n:=f_{n,n} $ where $f_{0,n}=f_{n,0}= n^n$ and $f_{m,n} = f_{m-1,n}+ f_{m,n-1} + f_{m-1,n-1}$

Question

Let the sequence:

$s_n:=f_{n,n} $ where $f_{0,n}=f_{n,0}= n^n$ and $f_{m,n} = f_{m-1,n}+ f_{m,n-1} + f_{m-1,n-1}$, for $mn>0$.

Computationally it seems that $\frac{s_{n+1}}{s_{n}} \approx e\cdot n -\frac{e}{2}$ .

Can you prove it?

Answer 1

Here is a proof modulo filling in some details of rigor. Let $\frac{1}{1-x-y-xy}=\sum_{i,j}D(i,j)x^iy^j$. $D(i,j)$ is a Delannoy number (irrelevant here). The recurrence is equivalent to $$ \sum_{m,n}f_{m,n}x^my^n = \frac{1+\sum_{k\geq 2}(k^k-(k-1)^{k-1}) (x^k+y^k)}{1-x-y-xy}. $$ Hence $$ f_{n,n} = D(n,n)+\sum_{k=2}^n(k^k-(k-1)^{k-1})(D(n-k,n) +D(n,n-k)). $$ (In fact, $D(n-k,n)=D(n,n-k)$.) The dominant terms in the asymptotic expansion of $f_{n,n}$ will come from the largest values of $k$. In particular, the first two terms of the asymptotic expansion of $f_{n+1,n+1}/f_{n,n}$ will arise from the terms with factors $(n+1)^{n+1}$, $n^n$, and $(n-1)^{n-1}$. Hence it suffices to take $$ f_{n,n}\sim (n^n-(n-1)^{n-1})(D(0,n)+D(n,0)) +((n-1)^{n-1}-(n-2)^{n-2})(D(1,n)+D(n,1)) +(n-2)^{n-2}(D(2,n)+D(n,2)). $$ Using $D(0,n)=1$, $D(1,n)=2n+1$, and $D(n,2)=2n^2+2n+1$, it is routine to compute $$ \frac{s_{n+1}}{s_n} \sim en+\frac e2+O(1/n).\qquad (1) $$ This disagrees with the proposed formula. I computed numerically that $$ \frac{s_{100}}{s_{99}}-99e = 1.3398\cdots, $$ so it is likely that (1) is correct. Perhaps what was meant is $$ \frac{s_n}{s_{n-1}} \approx en-\frac e2.\qquad (1) $$