7
$\begingroup$

I've encountered the following sum: $$ s_n = \sum_{j=1}^n {n \brace j}(\alpha n)_j \beta^j. $$ Here $\alpha$ and $\beta$ are positive constants, $(\alpha n)_j$ is a falling power, and ${n \brace j}$ is the Stirling number of second kind. My computations suggests that $s_n$ grows like $n^n C^n$ (where the constant $C$ depends on $\alpha$ and $\beta$); specifically, $\sqrt[n]{(s_n/n^n)}$ seems to converge to a limit as $n \rightarrow \infty$.

Are there good approaches to figuring out these kinds of limits? A similar situation was discussed in this question, but the sum there had $(\alpha)_j$ rather than $(\alpha n)_j$; the extra dependence on $n$ is causing me headaches!

$\endgroup$
4
  • $\begingroup$ your earlier question had a rising factorial (Pochhammer) instead of a falling factorial, is that intentional? $\endgroup$ Commented May 31, 2020 at 20:39
  • $\begingroup$ Yes, my sum has a falling rather than a rising power. But as observed in a comment in the earlier question, when the argument of the Pochhammer symbol is constant (not depending on n), there's not any difference in difficulty between falling and rising power. $\endgroup$ Commented May 31, 2020 at 20:49
  • $\begingroup$ The factor $\beta^n$ seems superfluous. $\endgroup$ Commented Jun 1, 2020 at 0:30
  • $\begingroup$ @RichardStanley I have corrected the sum --- the power of $\beta$ should have been $j$ rather than $n$. $\endgroup$ Commented Jun 1, 2020 at 1:34

1 Answer 1

5
$\begingroup$

The sum in question can be written (using Latin letters instead of Greek) as $$ S_n(a,b):= \sum_{k=0}^n {n \atopwithdelims \{ \} k} k! \binom{na}{k} b^k $$ where the round brackets denotes an ordinary binomial. It will be shown as $n \to \infty$ $$ (1)\quad S_n(a,b) \sim \frac{n!}{2}\,\exp{\Big(n\big( h(u_0) + \frac{h''(u_0)}{2}\,u_0^2\big)\Big)} \, \text{erfc}\big(\sqrt{\frac{n}{2} h''(u_0)} \,\,u_0 \big) $$ where $$h(u) = \frac{\log(1+b(e^u-1))^a}{u}, \quad u_0=\frac{1}{a} + \text{W}\big(\frac{1-b}{a\,b}\,e^{-1/a}\big) $$ and $W()$ is the Lambert W function. This follows from an asymptotic analysis of an alternative form,

$$(2) \quad S_n(a,b)=n!\,[u^n] (1+b\,(e^u-1))^{n \,a}$$

where $[u^n]$ is the 'coefficient of' operator. Note that when $b=1,$ the sum can be solved exactly, and gives the form the OP suspects. (This summation is known.) To derive the alternative form, note that sum is the Hadamard product of

$$ \omega_n(z) = \sum_{k=0}^\infty {n \atopwithdelims \{ \} k} k! z^k \quad \text{& } \quad (1+z)^{na}=\sum_{k=0}^\infty \binom{na}{k} z^k $$ The expression for $\omega_n$ can be written in terrms of Eulerian polynomials, but I prefer the polylogarithm at negative argument, $$ \omega_n(t) = \frac{\text{Li}_{-n}(t/(1+t))}{1+t} $$ Taking the Hadamard product,

$$S_n(a,b) = \frac{1}{2 \pi \,i} \oint \frac{dt}{t(1+t)} \text{Li}_{-n}(\frac{t}{1+t}) \big(1+\frac{b}{t}\big)^{na} \, dt$$ where the integration path surrounds the origin. Use $\text{Li}_{-n}(t/(1+t))=(-1)^{n+1}\text{Li}_{-n}(1+1/t).$ Let $t \to 1/t$ in the integral and check residue at $\infty.$ Then $$S_n(a,b) = \frac{(-1)^n}{2\pi i}\oint \frac{ \text{Li}_{-n}(1+t)}{1+t} \big(1+b\,t\big)^{n\,a} \, dt$$ Now use the known generating function $$\sum_{n=0}^\infty \frac{u^n}{n!} (-1)^n \frac{ \text{Li}_{-n}(1+t)}{1+t} = \frac{1}{e^u-1-t}$$ Putting this equation in the penultimate and using Cauchy's theorem results in equation (2).

For the asymptotic analysis, write (2) as a countour integral $$S_n(a,b)=\frac{n!}{2 \pi \,i} \oint \Big( \frac{(1+b(e^u-1))^a}{u} \Big)^n \frac{du}{u} $$ Classic saddle point analysis tells us to write this as $$S_n(a,b)=\frac{n!}{2 \pi \,i} \oint \exp{\big(n h(u)\big)} \frac{du}{u} $$ where $h$ has been given in (1), then expand $h$ in a power series about $u_0,$ which has also been found explicitly and given in (1). Run the contour through $u_0$ and open the loop so that it becomes a vertical line. Then, so long as certain conditions are satisfied (I have not checked them, other than $h''(u_0)>0$, a necessity) then $$ S_n(a,b) \sim \exp{(n\ h(u_0))} \frac{n!}{2 \pi} \int_{-\infty}^\infty \frac{dt}{u_0+i\,t} \exp{\big(-\frac{n}{2}\ h''(u_0) t^2 \big)} $$ The integral is solvable in terms of the complementary error function. For $n$ sufficiently large, it will simplify in the asymptotic limit to an exponential, as long as $h''(u_0)$ isn't too small. A potential problem with this analysis is that if $h''(u_0)$ does become small, and much smaller than $h^{(3)}(u_0)$ then a quadratic expansion of $h$ is not sufficient.

For examples of the accuracy of the approximation, a table is shown. $$ \begin{array}{c|lcr} n & a & b & \text{true} & \text{asym} & \text{% err}\\ \\ \hline 20 & 1/2 & 1/2 & 2.7717\ 10^{17} & 2.6867\ 10^{17} & 3.07\\ {} & 1/2 & 3/2 & 3.7421\ 10^{21} &3.5745\ 10^{21} & 4.48 \\ {} & 3/2 & 1/2 & 2.1498\ 10^{25} & 2.0862\ 10^{25} &2.96\\ {} & 3/2 & 3/2 & 1.6663\ 10^{23} & 1.5884\ 10^{23} & 4.68\\ 200 & 1/2 & 1/2 & 6.634\ 10^{374} & 6.617\ 10^{374} & 0.34\\ {} & 1/2 & 3/2 & 3.336\ 10^{415} & 3.319\ 10^{415} & 0.51\\ {} & 3/2 & 1/2 & 6.158\ 10^{453} & 6.138\ 10^{453} & 0.33\\ {} & 3/2 & 3/2 & 8.720\ 10^{521} & 8.673\ 10^{521}& 0.53 \end{array} $$

It's really surprising that the approximation for a problem with 2 parameters is so easily characterized.


Added 6/3/2020

There is a much simpler derivation of (2) that bypasses the need for the Hadamard product and the polylogs with negative index. Here it is:

It is known that $$ {n \atopwithdelims \{ \} k} k! = n![u^n](e^u-1)^k $$ Then $$ \sum_{k=0}^n {n \atopwithdelims \{ \} k} k! \binom{na}{k} b^k =$$ $$ n! [u^n] \sum_{k=0}^\infty \binom{na}{k} b^k (e^u-1)^k = n! [u^n] \big(1+b(e^u-1) \big)^{n \ a} $$ by the binomial theorem.

$\endgroup$
1
  • $\begingroup$ Thank you, this is really nice! $\endgroup$ Commented Jun 2, 2020 at 1:03

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .