Numerically evaluate a series involving Stirling numbers of the second kind

Question

How can I numerically evaluate the following for $n$ above one million: $$ \sum_{k>=n} \sum_{i=0}^{n-1} (-1)^i {{n-1}\choose{i}} \left( \frac{n-1-i}{n} \right)^{k-1} k (k+1)$$?

I have tried changing the order of summation and the getting closed form for the geometric series in $k$ but the terms are large (even for $n = 100$) and I run into precision problems.

Answer 1

Recall that $${n \brace k}=\frac{1}{k!}\sum _{i=0}^k(-1)^i\binom{k}{i}(k-i)^n,$$ so your expression is equal to $$\sum _{k\geq n}\frac{(n-1)!k(k+1)}{n^{k-1}}{k-1\brace n-1}=2(n-1)!\sum _{k\geq n}\frac{1}{n^{k-1}}\binom{k+1}{2}{k-1\brace n-1},$$ if $n$ is large, then $k$ is large, so ${k-1\brace n-1}\sim \frac{(n-1)^{k-1}}{(n-1)!}$ and so $$2(n-1)!\sum _{k\geq n}\frac{(n-1)^{k-1}}{n^{k-1}(n-1)!}\binom{k+1}{2}=2\sum _{k\geq n}\left (\frac{n-1}{n}\right )^{k-1}\binom{k+1}{2}$$ now take $x=(n-1)/n,$ we complete the sum to $\infty$ and take out the finite sum getting $$2\left (\sum _{k=0}^{\infty}\binom{k+1}{2}x^{k-1}-\sum _{k=0}^{n-1}\binom{k+1}{2}x^{k-1}\right )=2\left (\frac{1}{(1-x)^3}-\sum _{k=0}^{n-1}\binom{k+1}{2}x^{k-1}\right ),$$ recall too that taking the second derivative of $\sum _{k=1}^{n}x^{k}$ gives you $\sum _{k=1}^{n-1}(k+1)k\cdot x^{k-1}$ but that sum is $\frac{x^{n+1}-1}{x-1}$ and so we get $$\frac{2}{(1-x)^3}-\frac{(n + 1)n\cdot x^{n-1}}{x-1} + \frac{2 (n+1) x^n}{(x-1)^2} - \frac{2 (-1 + x^{1 + n})}{(x-1)^3},$$ taking $x=(n-1)/n$ back we get $$2n^3+(n + 1)n^2\cdot \left (1-\frac{1}{n}\right )^{n-1} + 2 n^2(n+1) \left(1-\frac{1}{n}\right )^n - 2 n^3(-1 + \left (1-\frac{1}{n}\right )^{n+1}).$$ For $n$ as big, if I am not mistaken, your expression should be close to $$(4-\frac{2}{e})n^3+\frac{3}{e}(n+1)n^2$$

Answer 2

Too long for comments.

Starting from the point where @Phicar wrote $$S_n=2\sum _{k= n}^\infty\left (\frac{n-1}{n}\right )^{k-1}\binom{k+1}{2}$$ we have $$S_n=\sum_{k= n}^\infty k (k+1) \left(\frac{n-1}{n}\right)^{k-1}=(n-1)^{n-1} n^{3-n} (5 n-3)$$ and for large values of $n$ $$S_n=\frac 1e\left(5 n^3-\frac{n^2}{2}-\frac{n}{24}+\frac{1}{16}+\frac{95}{1152 n}+\frac{917}{11520 n^2}+O\left(\frac{1}{n^3}\right)\right)$$ which seems to be quite different; however, none of these match the numbers that you provided as examples.