Limit of sum of terms of reccurence sequence

40 Views Asked by At

We have for $n>0$, $k>0$ $$T(n+1,k)=nT(n,k)+T(n,k-1)$$ which is the same recurrence relation to Stirling numbers of first kind.

Also we have $T(0,0)=1$, $T(n,0)=m$ for $n>0$ and $T(0,k)=0$ for $k>0$

So as you can see, we make a little change for $T(n,0)$, then if $$\sum\limits_{k=0}^{n}T(n,k)=\sum\limits_{k=0}^{\infty}T(n,k)=S(n)$$

When $m=0$ it gives us Stirling numbers, so $S(n)=n!$

But if we take $m=1$ $$\lim\limits_{n\to \infty}S(n)=n!(e-1)$$ or for $m=\frac{1}{2}$ $$\lim\limits_{n\to \infty}S(n)=\frac{n!e}{2}$$ Why do we have those results? How can I find it in general?

1

There are 1 best solutions below

0
On BEST ANSWER

If you take the sum over $k$ of your recurrence (ignoring edge effects) you get something like $$S(n+1)\approx nS(n)+S(n)=(n+1)S(n)$$ which explains why you have $S(n)$ approximately proportional to $n!$

But you have introduced edge effects with $m$, and in fact $$S(n+1)=(n+1)S(n)-m(n-1)$$

so $S(0)=0!, S(1)=1!+m, S(2)=2!+2m, S(3)=3!+5m, S(4)=4!+18m$ etc. which, using Michel Marcus's formula at OEIS A094294, means we can write $$S(n)=n!+m \lceil n!(e-2)\rceil$$ and the approximations you found are essentially this without the rounding up