I am looking for an "analytical" formula for the following summation; that is, write the following function without a summation sign:
$$ f(n) = \sum_{k=0}^{n}(-1)^k \cdot {n \choose k} \cdot (n-k)^{3n-1} $$
defined for all natural numbers $ n \in \mathbb{N} $. A disclaimer in beforehand: I actually do not know whether there is a solution to my problem, but I am grateful for any idea (also for asymptotically accurate results). My intuition was to somehow use the binomial expansion here, but I did not get anywhere…
Best Answer
An asymptotics may be obtained as follows. Using the generating function of the Stirling numbers of the second kind and Cauchy's formula, we find $$ f(n)=n!\left\{{3n-1 \atop n}\right\}= \frac{{(3n - 1)!}}{{2\pi i}}\oint_{(0 + )} {\frac{{(e^t - 1)^n }}{{t^{3n} }}dt} = \frac{{(3n - 1)!}}{{2\pi i}}\oint_{(0 + )} {e^{ - n\varphi (t)} dt} $$ where $$ \varphi (t) = \log \left( {\frac{{t^3 }}{{e^t - 1}}} \right). $$ There is a relevant saddle point at $t_0 = 3 + W( - 3e^{ - 3} ) = 2.82143937214277 \ldots$, where $W$ denotes the principal branch of the Lambert $W$-function. Following the steps in N. Temme's paper Asymptotic Estimates of Stirling Numbers (https://doi.org/10.1002/sapm1993893233) and applying Stirling's formula for the factorial, we deduce $$ f(n) \sim \frac{1}{{n\sqrt {3\left| {\varphi ''(t_0 )} \right|} }}\left( {\frac{{27n^3 }}{{e^3 }}\frac{{e^{t_0 } - 1}}{{t_0^3 }}} \right)^n $$ as $n\to +\infty$, with \begin{align*} \left| {\varphi ''(t_0 )} \right| & = 0.309567474978694 \ldots , \\ \frac{{e^{t_0 } - 1}}{{t_0^3 }} & = 0.703514172238102 \ldots\, . \end{align*} For example, $f(5)=4809004200$, whereas the asymptotic formula gives $4790795320$.
Note that you can write the asymptotic formula in the form $$ f(n) \sim An^{3n - 1} B^n , $$ with \begin{align*} & A = \frac{1}{{\sqrt {3\left| {\varphi ''(t_0 )} \right|} }} = 1.037675851879 \ldots, \\ & B = \frac{{27}}{{e^3 }}\frac{{e^{t_0 } - 1}}{{t_0^3 }} = 0.9456995211564 \ldots , \end{align*} showing why @Henry's empirical formula $f(n) \approx n^{3n - 1} C^{3n - 2}$ with $C = B^{1/3} = 0.98156196 \ldots$ works so well.