Asymptotic behaviour of sequence

Question

I am interested in the sequence

$$a(n)=\sum_{k=0}^n {p(n-k) \choose k}$$

where $p(n)$ is a polynomial equation.

When $p(n)=n$ this reduces to the Fibonacci sequence, but what about when $p(n)$ is quadratic?

For example when $p(n)=n^2$, it can be seen that $a(n)$ has superexponential growth by considering only one of the terms of the sum $$a(n) \ge {p(n-(n/2)) \choose n/2}={p(n/2) \choose n/2}\ge\left(\frac{p(n/2)}{n/2}\right)^{n/2}=\left(\sqrt{\frac{n}{2}}\right)^n$$ But I would like to know more information than just this lower bound - an asymptotic formula would be great. Any ideas?

I found a related sequence here (which is equivalent to the case when $p(n)=n^2$) along with its generating function if that is any help to anyone.

Answer 1

The easiest way to answer this question is with the steepest descent method, which is a standard techinque for calculating such asymptotic expansions. Here is the case $p(x)=x^2$. Write the sum as $$ S = \sum_{0\leq k\leq n} \binom{p(k)}{n-k} = \sum_{0\leq k\leq n} s(k). $$

For the binomial coefficients one useful asymptotic formula is $$ \binom{n}{n y} = q(n,y) = (2\pi n y(1-y))^{-1/2}\exp(n H(y)), $$ where $H(y) = -y\log y-(1-y)\log(1-y)$ is the binary entropy function.

We can approximate the sum by the equivalent integral, and then expand the function $s(k)$ in Taylor series around its maximum $s(k_*)=s_*$: $$ \begin{aligned} S &\sim \int_0^n s(k)\,dk = n \int_0^1 s(n z)\,dz \\&\sim n \int_{-\infty}^\infty s_* e^{\frac12\partial_z^2(\log s)(z-z_*)^2}\,dz \\&= s_* n \sqrt{2\pi/(-\partial_z^2(\log s))}. \end{aligned} $$

The find the point $z_*$ and the corresponding term $-\partial_z^2(\log s)$, it is sufficient to approximate $s(n z)$ by $$ s(n z) \sim q(p(n z), n(1-z)/p(n z)) = q\left(n^2z^2,\frac{1-z}{z^2n}\right). $$ To find the leading asymptotic term in $z$, it is easiest to use $\log q$ instead of $q$: $$\begin{aligned} \log q &= n^2 z^2 H\left(\frac{1-z}{n z^2}\right) \sim n(1-z)\log\frac{e n z^2}{1-z}, \\ \partial_z \log q &\sim n\left(-2+\frac2z - \log n + \log\frac{1-z}{z^2} \right) \\ \partial_z^2 \log q &\sim -\frac{n(2-z^2)}{z^2(1-z)}. \end{aligned}$$ Setting $\partial_z \log q=0$, and substituting $z=1/w$ gives the equation $$ w + \log w + \frac12\log(1-1/w) = \frac12 \log e^2n, $$ which can be written in this form: $$ w e^w = \frac{e \sqrt{n}}{\sqrt{1-1/w}}. $$ To leading order, $w$ is given by the Lambert W function: $$ w = W(e \sqrt{n}), $$ and the next approximation is: $$ w = W(e \sqrt{n})/\sqrt{1-1/W(e \sqrt{n})}. $$ From $z=1/w$ it is also possible to calculate the asymptotic form for $s_*$.

So the result is that $$ \frac{S}{s_*} \sim n\sqrt{2\pi}\left(\frac{n W(e\sqrt{n})(-1+2W(e \sqrt n)^2)}{W(e \sqrt{n})-1} \right)^{-1/2}. $$ At $n=100$, the error is $6.6\%$, and the next order for $w$ gives an error of $0.69\%$. Asymptotically, $W(e \sqrt n) \sim \log(e\sqrt n)$, but the convergence is slow, at $n=100$ the error is $-16.6\%$.

Answer 2

For sums like this, usually one term dominates. Taking $p(n)=n^d$ to play with, consider when $\binom{(n-k)^d}{k} \lt \binom{(n-k-1)^d}{k+1}$ stops holding. This is not far from when $(k+1) \lt (\frac{n-k-1}{n-k})^{kd} ((n-k-1)^d - k)$ stops holding, which in turn happens not far from when $(\frac{n-k}{n-k-1})^k \gt (n-k-1)$ which in turn doesn't happen until somewhere near $k \gt (n-k-1)\log(n-k-1)$. (For large $n, k \approx n(\log(n)-1)/\log n$ is a good value to start with in an approximation routine.) As recommended in the comments, you should use calculus and similar approximations to find the actual value of $k$, but it will usually be $k \gt n/2$. Once you have that term, the sum will usually be not much larger than the term.

Gerhard "There's An Order To This" Paseman, 2014.06.13