Asymptotic behaviour of sequence 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.
 A: 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\%$.
A: 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
