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?


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


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.