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?

$\begingroup$
$\endgroup$

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

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

or