39
$\begingroup$

Experimentation suggests the limit $$\lim_{n\rightarrow\infty} (-1)^n\sum_{k=1}^n(-1)^k{n\choose k}^{-1/k}=\frac{1}{2}\ .$$ Does somebody have an idea for (a start of) a proof?

Added: There seem to be variations: $$\lim_{n\rightarrow\infty} (-1)^n\sum_{k=1}^n(-1)^k{2n\choose k}^{-1/k}=\frac{1}{8}\ ,$$ $$\lim_{n\rightarrow\infty} (-1)^n\sum_{k=1}^n(-1)^k{3n\choose k}^{-1/k}=\frac{2}{27}\ ,$$ etc.

Moreover, the exponent $-1/k$ in the original identity can seemingly be replaced by $-2/k$, $-3/k$ (by $-\alpha/k$ for strictly positive $\alpha$?) without changing the limit value.

Update: Given a strictly positive rational number $\frac{p}{q}\leq 1$ (with coprime natural integers $p,q$), there is perhaps a number $\lambda(p/q)$ such that $$\lim_{n\rightarrow\infty}(-1)^n\sum_{k=1}^{pn}(-1)^k{qn\choose k}^{-\alpha/k}= \frac{(\lambda(p/q))^\alpha}{2}$$ for $\alpha$ real and strictly positive. A few values for $\lambda$ are seemingly $$\lambda\left(\frac{1}{3}\right)=\frac{4}{27},\ \lambda\left(\frac{1}{2}\right)=\frac{1}{4},\ \lambda\left(\frac{2}{3}\right)=\frac{2}{3\sqrt{3}},\ \lambda\left(1\right)=1\ .$$ Two more conjectures: $\lambda\left(\frac{1}{q}\right)=\frac{(q-1)^{q-1}}{q^q}$ and $\lambda(x)^x=\lambda(1-x)^{1-x}$ for rational $x$ in $(0,1)$.

The correct formula for $\lambda$ is perhaps $\lambda(x)=x(1-x)^{(1-x)/x}$.

$\endgroup$
11
  • 2
    $\begingroup$ What led you to conjecture this? It's very unusual-seeming (to me, anyhow). $\endgroup$
    – Igor Rivin
    Feb 2, 2012 at 18:56
  • 2
    $\begingroup$ Serendipity (playing around with Maple). $\endgroup$ Feb 2, 2012 at 19:04
  • 2
    $\begingroup$ What happens if you use Stirlings Formula to estimate the factorials in the binomial coefficient? A back-of-an-envelope calculation seems to indicate some nice cancellation... $\endgroup$ Feb 2, 2012 at 19:14
  • $\begingroup$ @Kevin Buzzard: I agree but how can one exploit this! $\endgroup$ Feb 2, 2012 at 19:20
  • 1
    $\begingroup$ You would need to have (for $n$ even), $\sum_{k=pn+1}^{k=pn+n} (-1)^k \left(\begin{array}{c} qn \\ k \right)^{-1/k}=\lambda(p+1/q)-\lambda(p/q)$. If $qn$ has a lot of prime factors, this seems to imply that a very short chunk should look exactly like the derivative of $\lambda$. Is the difference of two terms propoprtional to $d\lambda$? $\endgroup$
    – Will Sawin
    Feb 4, 2012 at 22:03

3 Answers 3

12
$\begingroup$

Off-the-wall suggestion... Take $n$ even, I call it $2n$ now. Then asymptotically as $n \to \infty$ $$ \binom{2n}{2n-2j-1}^{-1/(2n-2j-1)} - \binom{2n}{2n-2j}^{-1/(2n-2j)} \sim \frac{1}{2n}\log \frac{2n}{2j-1} $$ and the sum $$ \frac{1}{2n}\sum_{j=1}^{n}\log\frac{2n}{2j-1} $$ is a Riemann sum for the integral $$ \frac{1}{2}\int_0^1 \log\frac{1}{t}\;dt = \frac{1}{2} . $$


Added Feb.3 I said it was off-the-wall. The asymptotic expansion is from Maple, like this:

     asymptotics

$\endgroup$
5
  • $\begingroup$ Sounds pretty reasonable. I assume all you need to do from here is bound the error... $\endgroup$
    – Igor Rivin
    Feb 2, 2012 at 20:17
  • 1
    $\begingroup$ I am not sure that your asymptotic expansion is correct (it seems not to work numerically, for $n=100000,j=50000$, the error is $\sim 1/144267$ which is of order $0(1/n)$). How do you get it? $\endgroup$ Feb 3, 2012 at 9:52
  • 2
    $\begingroup$ Your method should also apply to $(-1)^n\sum_{k=1}^n(-1)^k{2n\choose k}^{1/k}$ which converges numerically quite convincingly to $1/8$ while your method suggests $(1+\log 2)/4$ as the limit. $\endgroup$ Feb 3, 2012 at 10:19
  • $\begingroup$ @Gerald Edgar: Sorry, I did misunderstand the expression "off-the-wall". I guess the asymptotics is correct for fixed $j$ and $n$ going to infinity. The correct value of the integral is thus probably a happy coincidence, since contributions to the limit come from most terms of the sum (except the very first which can of course be neglected). $\endgroup$ Feb 3, 2012 at 15:58
  • $\begingroup$ @Gerald: Roland seems to be correct. You need the bulk of the terms, but your asympt() is for fixed $j$. You also have the sign wrong. Putting $j=an$ before applying asympt(), assuming $0<a<1$, gives for your first expression $a^{a/(1-a)}\ln(a)/(2(1-a)n)$, which integrates to exactly $-1/(2n)$. So it does seem like a happy coincidence. The same approach also verifies that the answer (remarkably) doesn't change if the exponent $-1/k$ is replaced by $-c/k$ for $c\ge 1$. $\endgroup$ Feb 6, 2012 at 21:57
10
$\begingroup$

I would suggest to re-write the problem as $$\lim_{n\to\infty} \sum_{k=0}^{n-1} (-1)^k \binom{n}{k}^{-1/(n-k)} = {}?\,.$$ Now if I'm not mistaken, it is true that for fixed $x$ with $|x| < 1$, we have $$\lim_{n\to\infty} \sum_{k=0}^{n-1} (-1)^k \binom{n}{k}^{-1/(n-k)} x^k = \frac{1}{1+x}$$(the coefficients have absolute value $\le 1$ and converge termwise to $(-1)^k$; multiplying by $x^k$ lets us apply dominated convergence). So it would be sufficient to show that $\lim_{n \to \infty}$ and $\lim_{x \to 1-}$ commute. I don't have time right now to really dive into it, but maybe somebody else would like to go from here.

Note that this would also give a proof of the more general version: $$\lim_{n\to\infty} \binom{qn}{pn+k}^{-a/(n-k)} = \lim_{n\to\infty} \binom{qn}{pn}^{-a/n} = \left(\frac{p^p (q-p)^{q-p}}{q^q}\right)^a$$

$\endgroup$
8
$\begingroup$

Here is a different approach. Write $$a_{n,k} = \binom{n}{k}^{-1/(n-k)}$$ (or whatever the term is) for $0 \le k < n$ and $a_{n,k} = 0$ for $k \ge n$. Then $$\sum_{k=0}^{n-1} (-1)^k \binom{n}{k}^{-1/(n-k)} = \sum_{k=0}^\infty (-1)^k a_{n,k} = \frac{a_{n,0}}{2} + \frac{1}{2} \sum_{k=0}^\infty (a_{n,2k} - 2 a_{n,2k+1} + a_{n,2k+2})\,.$$ So if you can show that $$\lim_{n\to\infty} \sum_{k=0}^\infty |a_{n,2k} - 2 a_{n,2k+1} + a_{n,2k+2}| = 0\,,$$ the claim will follow. This should hold for any sufficiently "smooth" double sequence $(a_{n,k})$, since it just means that locally the sequence (for fixed $n$) varies nearly linearly.

If $a_{n,k} = f_n(k)$ for some nice function $f_n$, then the second order difference is bounded by $\max \{|f''_n(x)| : 2k \le x \le 2k+2\}$, which may help in the estimate. For example, taking $a_{n,k} = n^{-1/(n-k)}$, so $f_n(x) = \exp\left(-\frac{1}{n-x} \log n\right)$, we have $$f''_n(x) = \left(\left(\frac{\log n}{(n-x)^2}\right)^2 + \frac{2\log n}{(n-x)^3}\right) f_n(x)\,.$$ For $0 < \alpha < 1$, we find that $$\sum_{k=0}^{\lfloor n - \alpha \log n\rfloor} |a_{n,2k} - 2 a_{n,2k+1} + a_{n,2k+2}| \le C \frac{1}{\alpha^3 \log n}\,,$$and the tail can be estimated by a constant times $\exp(-1/\alpha)$. Taking $\alpha$ arbitrarily close to zero shows that $$\lim_{n\to\infty} \sum_{k=0}^{n-1} (-1)^k n^{-1/(n-k)} = \frac{1}{2}\,.$$ For the original problem, the estimates are likely to be more involved, but should be possible.

Addition:
The formula for $\sum_{k=0}^n (-1)^k a_{n,k}$ given near the beginning of this answer can (in the case $a_{n,k} = f_n(k)$) be interpreted as $a_{n,0}/2$ plus half the difference between the trapezoid-rule and midpoint-rule approximations to $\int_0^\infty f_n(x)\,dx$ using the even integers as subdivision points. For a well-behaved sequence of functions, this difference should tend to zero.

So the problem has only little to do with binomial coefficients as such.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.