Asymptotics of Binomial Transform of a Sequence

Question

I have a sequence of nonnegative integers $w(k)$ that I know grows asymptotically as $$w(k)\sim C\frac{\rho^k}{k^\alpha}.$$ Here, $C\approx 3.422$, $\rho\approx 4.729$, and $\alpha\approx 4.515$ are specific constants. I can define a new sequence $v(n)$ by $$v(n)=\sum_{k=0}^n{n\choose k}w(k).$$ Is there any way to find an asymptotic formula for $v(n)$ in terms of the constants $C$, $\rho$, and $\alpha$. I think it isn't too difficult to show that $$\lim_{n\to\infty}v(n)^{1/n}=\rho+1,$$ but I'm wondering if I can say more. One possible attempt is to use generating functions. If $W(z)=\sum_{k\geq 0}w(k)z^k$ and $V(z)=\sum_{n\geq 0}v(n)z^n$, then $$V(z)=\frac{1}{1-z}W\left(\frac{z}{1-z}\right).$$

Answer 1

Yes, you can say more. I'll be rough here; you can look at Chapter VI of Flajolet and Sedgewick's Analytic Combinatorics for details.

Our starting point is the observation that for arbitrary complex $r$ not equal to a nonnegative integer, we have

$$[z^k] (1 - \rho z)^{-r} \sim \frac{k^{r-1} \rho^k}{\Gamma(r)}$$

where $\Gamma$ is the Gamma function and $[z^k]$ extracts the $k^{th}$ coefficient. Setting $r - 1 = - \alpha$, hence $r = 1 - \alpha$, this means we can approximate the generating function of $w(k)$ as

$$W(z) \sim C_2 \left( 1 - \rho z \right)^{\alpha - 1}.$$

where $C_2 = C \cdot \Gamma(1 - \alpha)$. Applying the binomial transform then gives

$$\begin{eqnarray*} V(z) &\sim C_2 (1 - z)^{-1} \left( 1 - \frac{\rho z}{1 - z} \right)^{\alpha - 1} \\ &\sim C_2 (1 - z)^{-\alpha} \left( (1 - z) - \rho z \right)^{\alpha - 1} \\ &\sim C_2 (1 - z)^{-\alpha} \left( 1 - (\rho+1) z \right)^{\alpha - 1}\end{eqnarray*}$$

Since $|\rho + 1| > 1$ this generating function's closest singularity to the origin is at $z = \frac{1}{\rho + 1}$, and analyzing the behavior at this singularity (basically using the first approximation above again) gives

$$\boxed{ v(n) \sim C_3 \frac{(\rho+1)^n}{n^{\alpha}} }$$

where $C_3 = C \left( 1 - \frac{1}{\rho+1} \right)^{-\alpha}$ (the Gamma factor cancels).