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](http://oeis.org/A121689) (which is equivalent to the case when $p(n)=n^2$) along with its generating function if that is any help to anyone.



Asymptotic behaviour of sequence
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](http://mathworld.wolfram.com/LambertW-Function.html):
$$ 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\%$.


