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

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?

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