2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ The website in your profile should be the full string, personal.soton.ac.uk/~ab2005/About_Me.html in which case it will act as a link. I do not see that it will let me edit your profile, so you should do it. Note that this comment also renders it as a link, visibly stripping the beginning www . WOW, it really does not want to show the http or the :// let me try separated $\endgroup$ – Will Jagy Jan 14 '14 at 18:26
  • $\begingroup$ It is already preceded by 'http : // www' (without the spaces). I'm not sure why it doesn't come up as a link. $\endgroup$ – alexbailey Jan 14 '14 at 19:32
  • $\begingroup$ Alright. Maybe a moderator will notice. Meanwhile, the link in my comment works. $\endgroup$ – Will Jagy Jan 14 '14 at 19:39
  • 3
    $\begingroup$ I would just suggest using Stirling's formula and calculus. $\endgroup$ – Lucia Jan 14 '14 at 20:07
3
$\begingroup$

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\%$.

$\endgroup$
  • $\begingroup$ This is beautiful. Yay for analytic number theory! $\endgroup$ – alexbailey Jun 15 '14 at 19:01
  • $\begingroup$ @alexbailey I don't know about that :) The way I learned this, I'd say: Yay for mathematical physics. There is a really nice book by de Bruijn that explains this type of thing. $\endgroup$ – Kirill Jun 15 '14 at 19:05
  • $\begingroup$ Just one more question, I was being a bit sloppy when I said the sum is from $0$ to $n$ as the terms when $k^2<n-k$ are not really defined, I guess it should really be something like $k$ from $0$ to $\left\lfloor{\frac{1}{2}\left(1+\sqrt{1+4n}\right)}\right\rfloor$. Does this change anything with the analytic approach? $\endgroup$ – alexbailey Jun 15 '14 at 19:14
  • $\begingroup$ @alexbailey ${m\choose n}$ is by definition $0$ when $0\leq m<n$ (the expression for it in terms of gamma functions makes this very clear). It doesn't change anything because the function still reaches its maximum on the domain. In practical terms, if you knew where the maximum was, you could sum only the few terms around it and it would be enough. $\endgroup$ – Kirill Jun 15 '14 at 19:18
  • $\begingroup$ Yes I thought it would be OK, I was just a little concerned when you pulled the $n$ out of the integral, but I guess it all cancels out in the end? Many thanks again. $\endgroup$ – alexbailey Jun 16 '14 at 9:27
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ I shouldn't hide the dependence on d: the third inequality should probably have a $(k+1)^{1/d}$ multiplier on the left hand side. However, even dropping such terms doesn't move the answer much, and once one has a good estimate, one can backtrack and refine it. Gerhard "Putting Glasses Back On Now" Paseman, 2014.06.13 $\endgroup$ – Gerhard Paseman Jun 13 '14 at 22:16
  • $\begingroup$ This is very insightful also. I don't think I'd really appreciated how much the largest term can dominate the sum. Thanks! $\endgroup$ – alexbailey Jun 15 '14 at 19:13

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.