4

Let $c>1$.

Question. What is the asymptotic behaviour of the sum \begin{align} S_n = \sum_{k=0}^{n} \left(-\frac{1}{2} \right)^k \binom{n}{k} \sum_{j=0}^{k} \binom{cn+k}{j} \end{align} as $n$ goes to infinity?

I don't need strong bounds; $\lim_{n \to \infty} \frac{\log \lvert S_n \rvert}{n}$ in terms of $c$ will do. Experimentally the limit exists for each $c$.

I tried generating functions, but the prefix-sum-of-binomials term is hard to handle. Also, the dominant term in the alternating sum seems to be $k = (1 - \alpha_c)n$ for some constant $\alpha_c$ which goes to $0$ as $c$ becomes larger.

See the figure below, graphing $\frac{\log_2 S_n}n$ for $n=100$, for different $c$.

The dependency on c is linear with errors until approximately c=6, where it changes shape into a concave function.

Daniel Paleka
  • 233
  • 1
    Is the case $c=1$ understood ? It may (or may not) help to note that the case $c=1$, $\sum_{j=0}^k {n+k\choose j}$ is the max number of subregions in which $n+k$ hyperplanes of codimension $1$ subdivide $\mathbb R^{k}$. – dohmatob Aug 20 '21 at 19:44
  • Maybe this can help ? https://mathoverflow.net/a/223300/78539 – dohmatob Aug 20 '21 at 19:51
  • Thanks! I was mainly interested about a certain $7 < c < 8$, or precisely the experimental threshold when $2^{n(c - 1 - H(1/c))} > S_n$, where $H(x)$ is the binary entropy function. This to some questions about ReLU neural networks using conic integral geometry and the statistical dimension. I can try to solve $c=1$, or maybe even $c=0$. – Daniel Paleka Aug 20 '21 at 20:07
  • I put $c > 1$ because some experiments got weird for $c<1$, but maybe it is not important. Not sure how to exploit hypergeometric functions, we can already approximate the prefix binomial sum well by the leading binomial coefficient, but still the series need to be summed up and the errors controlled. Cancellation here seems to matter a lot. – Daniel Paleka Aug 20 '21 at 20:12
  • 1
    Concerning your previous comment, note that the case $c=0$ is not very interesting since $S_n|{c=0}=\sum{k=0}^k(-1/2)^k {n \choose k}\sum_{j=0}^k {k\choose j}=\sum_{k=0}^n (-1)^k{n \choose k} = (1-1)^n=0$. – dohmatob Aug 20 '21 at 20:32
  • 1
    is $c$ an integer or just a real number larger than 1? – Pietro Majer Aug 21 '21 at 13:45
  • 1
    Hmmm... You are writing as if you knew for sure that $S_n>0$ while for small $n$ and large $c$ it definitely changes sign a few times. Does it really look positive from your numerics as $n\to\infty$ or you just care about the absolute value? – fedja Aug 21 '21 at 14:17
  • 2
    $S_n$ equals the coefficient of $x^n$ in $-\frac12 (t-\frac12)^{n-1} (1-t)^{-cn}$. So, perhaps using Lagrange inversion and standard methods for estimating the coefficients of generating functions can give the aymtotics. – Max Alekseyev Aug 21 '21 at 17:51
  • @fedja: Uh, sorry, I care for its absolute value only. Actually it is negative sometimes, I will fix the notation. But experimentally it seems that in the $c$ regime where I care for it, the sign depends on the parities of $n$ and $cn$? – Daniel Paleka Aug 21 '21 at 17:59
  • @PietroMajer: Yeah, that may be imprecise, actually think $ \lfloor cn \rfloor$ instead of $cn$. Experimentally the magnitude of $S_n$ is not affected by whether we take floor or ceil or sublinear changes to the $cn$ term in general, but the sign of $S_n$ may be. – Daniel Paleka Aug 21 '21 at 18:02
  • A transcription error on a the first comment of mine, doesn't matter at all the question at hand: it should be $2^{n(c - (c+1) H(\frac1{c+1}))}$ instead of $2^{n(c - 1 - H(\frac1c))}$. The regime $7 < c < 8$ is correct. – Daniel Paleka Aug 21 '21 at 18:48

2 Answers2

5

The sum $\sum_{j=0}^{k} \binom{cn+k}{j}$ equals the coefficient of $x^k$ in $(1+x)^{cn+k}(1-x)^{-1}$, and by Lagrange–Bürmann formula it is also the coefficient of $t^k$ in $(1-2t)^{-1}(1-t)^{-cn}$. It follows that $S_n$ is the coefficient of $t^n$ in $-\frac12 (t-\frac12)^{n-1}(1-t)^{-cn}$.

Applying Lagrange–Bürmann formula again, we get the following generating function for $S_n$: $$\sum_{n\geq 0} S_n t^n = \frac{1-h(t)} {1-(c+1)h(t)+2ch(t)^2},$$ where $h(t)$ is the compositional reverse of $g(t):=\frac{t (1-t)^c}{t - 1/2}$, that is $h(t)$ satisfies $g(h(t))=t$.

It can be seen that g.f. decomposes to $$\frac{\sqrt{c^2-6c+1} - (3c-1)}{4c\sqrt{c^2-6c+1}}\frac1{\alpha_+-h(t)}+\frac{\sqrt{c^2-6c+1} + (3c-1)}{4c\sqrt{c^2-6c+1}}\frac1{\alpha_- - h(t)},$$ where $\alpha_{\pm} = \frac{c+1\pm\sqrt{c^2-6c+1}}{4c}$ are the zeros of $1-(c+1)x+2cx^2$. Noticing that poles $h(t)=\alpha_\pm$ correspond to $t=g(\alpha_\pm)$, we conclude that

$$\lim_{n\to\infty} \dfrac{\log |S_n|}{n} = \begin{cases} - \log |g(\alpha_+)|, & \text{if } c < 3-2\sqrt{2};\\ \frac{c-1}2\log(2), & \text{if } c\in [3-2\sqrt{2},0)\cup (0,3+2\sqrt{2}];\\ - \log |g(\alpha_-)|, & \text{if } c > 3+2\sqrt{2}. \end{cases}$$

Max Alekseyev
  • 30,425
  • 2
    Nice answer. Would you mind adding a one-liner explaning how you obtain that formula for the generating function of $S_n$ ? – dohmatob Aug 22 '21 at 08:50
  • This is a consequence of your comment that $S_n$ is the coefficient of $t^n$ in $-\dfrac{1}{2}(t-\frac{1}{2})(1-t)^{-cn}$, right ? – dohmatob Aug 22 '21 at 09:00
  • 1
    @dohmatob: Correct. I've added some leads. – Max Alekseyev Aug 22 '21 at 11:42
  • 1
    Thanks, I will accept this answer when I digest it. I think I need to read Chapter 5 of Wilf's book first. – Daniel Paleka Aug 22 '21 at 12:37
  • @MaxAlekseyev Sorry, but should it be easy to see that $\log_2 g(a_+) = -\frac{c-1}2$? I can't get it. – Daniel Paleka Aug 22 '21 at 15:36
  • Yes - it's easy to see noticing that $g(\alpha_+)$ and $g(\alpha_-)$ are conjugates, and using the formula $|g(\alpha_+)|=\sqrt{g(\alpha_+)g(\alpha_-)}$. – Max Alekseyev Aug 22 '21 at 18:30
  • @MaxAlekseyev Unfortunately the regime I am interested in has $c^2 - 6c + 1 > 0$, and this no longer holds. The answer seems a bit uglier now. So weird that it does not depend algebraically on $c$. – Daniel Paleka Aug 22 '21 at 22:40
  • 1
    @DanielPaleka: In that case, it grows as $1/|g(\alpha_-)|^n$, but $|g(\alpha_-)|\ne 2^{(c-1)/2}$ anymore. – Max Alekseyev Aug 23 '21 at 00:32
  • Yeah, I got it. It doesn't seem to have a nice form. Thanks anyway. – Daniel Paleka Aug 23 '21 at 00:49
  • My actual application has another integer parameter $r \ge 0$, and I need to evaluate the above with $\binom{n-r}{k-r}$ instead of $\binom{n}{k}$ in the definition of $S_n$. But, I think I can do it myself based on your answer. Thanks again. – Daniel Paleka Aug 23 '21 at 00:53
  • 1
    This is an amazing computation. Yet I do not follow the conclusion: how can one be sure that the g.f of $S_n$ has no other poles closer to the origin than $g(\alpha_\pm)$? The function $h(t)$ is a local inverse of $g$ at $0$, but it may fail to be defined outside the disk $|t|<r<|g(\alpha_\pm)|$ e.g. because $r=|g(z_0)|$ for some $z_0$, zero of $g'$. – Pietro Majer Aug 23 '21 at 07:56
  • 1
    @PietroMajer: Indeed, there are some gaps to fill in w.r.t. asymptotic, but I checked the conclusion numerically for many values of $c$ and it seems to hold. I leave proving it rigorously (which I believe is rather routine) to the OP. – Max Alekseyev Aug 23 '21 at 12:21
  • @PietroMajer Once you have if in the form where you have an integral of the $n$-th power of a fixed analytic function times some fixed function over a contour surrounding the origin, the usual saddle point method works (and gives the same result, of course). So we are really talking about the landscape of |(z-1/2)(1-z)^{-c}z^{-1}|$, which may be a bit easier to comprehend than the inverse function argument. – fedja Aug 27 '21 at 22:22
  • @fedja When you have time, do you mind elaborating on your last comment? I don't get what form the first sentence of your comment is referring to in the above answer. – Daniel Paleka Sep 11 '21 at 21:18
  • @DanielPaleka The coefficient at $z^n$ in the Taylor expansion of $(z-1/2)^n(1-z)^{-cn}$ at $0$ is (up to some nonsense like $2\pi i$) $\oint F(z)^n\frac{dz}{z}$ where $F(z)=(z-1/2)(1-z)^{-c}z^{-1}$, so, to find the asymptotics, we need to create a "mountain pass" loop around the origin in $\mathbb C\setminus [1,+\infty)$ according to the landscape of $|F(z)|$, i.e., to find the critical points of $\log F(z)$, say. I hope I don't miss anything here :-) – fedja Sep 11 '21 at 21:34
  • This recent question is relevant and has pointers to the book "Analytic Combinatorics" by Flajolet and Sedgewick in the comments. – Max Alekseyev Sep 14 '21 at 17:10
3

My two cents. We can express the inner sum of binomial coefficients $\sum_{j=0}^k{N\choose j}$ with $N=cn+k$ by means of the integral remainder formula for the Taylor expansion of $(1+x)^{N}$ (this one). By linearity the sums over $j$ splits into two sums, the first of whom vanishes:
$$\sum_{k=0}^{n} \left(-\frac{1}{2} \right)^k \binom{n}{k} 2^{cn+k}= 2^{cn}\sum_{k=0}^{n} \left(-1 \right)^k \binom{n}{k}=0,$$ so we are left with $$ S_n= -cn\sum_{k=0}^{n} \left(-\frac{1}{2} \right)^k \binom{n}{k} {cn+k\choose k}\int_0^1(1+x)^{cn -1}(1-x)^kdx= $$ $$ = -cn\int_0^1\Bigg[ \sum_{k=0}^{n} \binom{n}{k}{cn+k\choose k} \left(\frac{x-1}{2} \right)^k\Bigg]\big(1+x\big)^{cn -1}dx. $$ We recognize the sum into brackets as the $n$-th Jacoby polynomial $ P^{\alpha,\beta}_n(x)$, with $\alpha=0$ and $\beta=(c-1)n$: $$P^{0,(c-1)n}_n(x)=\sum_{k=0}^{n} \binom{n}{k}{cn\choose k} \left(\frac{x-1}{2} \right)^k\left(\frac{x+1}{2} \right)^{n-k}=\sum_{k=0}^{n} \binom{n}{k}{cn+k\choose k} \left(\frac{x-1}{2} \right)^k,$$ and your sum can be written $$S_n=-cn\int_0^1 P^{0,(c-1)n}_n(x)(1+x)^{cn-1}dx.$$

Note: the integral over $[-1,1]$ vanishes, since it is $$\int_{-1}^1 P^{0,(c-1)n}_n(x)(1+x)^{n-1}(1+x)^{(c-1)n}dx,$$ and $P^{0,(c-1)n}_n(x)$ is orthogonal w.r.to the weight $(1+x)^{(c-1)n}$ to all polynomials of degree less than $n$. So the integral on $[-1,0]$ gives $-S_n$, whence we may also express $S_n$ as $-cn/2$ times the $n$th Fourier coefficient of the function $(1+x)^{n-1}\text{sgn}(x)$ w.r.to the said scalar product on $[-1,1]$, namely $S_n=-\frac{cn}2\Big\langle P^{0,cn-n}_n(x),\;(1+x)^{n-1}\text{sgn}(x)\Big\rangle.$

Here I stop; but since there is a huge knowledge on Jacobi polynomials, one may hope that the existing bounds or a some smart use of formulas may give a quick conclusion.

Pietro Majer
  • 56,550
  • 4
  • 116
  • 260