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$ – Carlo Beenakker May 31 '20 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$ – David Galvin May 31 '20 at 20:49
  • $\begingroup$ The factor $\beta^n$ seems superfluous. $\endgroup$ – Richard Stanley Jun 1 '20 at 0:30
  • $\begingroup$ @RichardStanley I have corrected the sum --- the power of $\beta$ should have been $j$ rather than $n$. $\endgroup$ – David Galvin Jun 1 '20 at 1:34
4
$\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$ – David Galvin Jun 2 '20 at 1:03

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.