A conjecture on the sum of binomial coefficients

Question

I am looking for a proof, disproof or counter example of the following claim.

Let $C = \{k_1, k_2, \ldots, \}$ be a strictly increasing infinite sequence of positive integers which have a certain characteristic $C$. For example $C$ can be the set of all natural numbers, or all odd numbers or all even numbers or all primes or all numbers not divisible by 4 etc.

Let $N(x)$ be the numbers of positive integers $\le x$ that have this characteristic $C$ i.e. $N(x) = \sum_{k_i \le x} 1$. For example the number of integers less than $x$ have the characteristic of being even or prime is $x/2$ and $\pi(x)$ respectively.

Conjecture: If $(\frac{k_1}{k_n}, \frac{k_2}{k_n}, \ldots, \frac{k_{n-1}}{k_n},1)$ approach uniform distribution in $(0,1)$ as $n \to \infty$ then,

$$ \sum_{k_i \le n}{n\choose k_i} \sim \frac{2^n}{n}N(n). $$

The progress on the case of primes is present in this MSE post.

Edit: The additional constraint on uniform distribution has been added in light of @Paul SInclair's comment and @bof's counter example for non-uniformly distributed $k_i/k_n$

Answer 1

I think this is a counterexample.

Let $C$ be the set of all positive integers whose base $10$ representation has an odd number of digits. Let $$f(n)=\frac n{N(n)2^n}\sum_{k\in C}\binom nk.$$ The conjecture is that $\lim_{n\to\infty}f(n)=1$. In fact, $$\lim_{n\to\infty}f\left(10^{2n}\right)=0$$ and $$\lim_{n\to\infty}f\left(10^{2n+1}\right)=1.1.$$

Answer 2

A general reason for this to hold is just that $\sum_{k\le n}{n\choose k} = 2^n$. There are $n+1$ terms in this sum. For large $n$, if you add up some $N < n$ of the terms, uniformly distributed, it is reasonable to expect that you will get approximately $\frac N{n+1}$ of the total value, i.e., $\frac N{n+1}2^n \sim \frac Nn2^n$

Of course, this heuristic argument hinges on the summed values being proportionate to the fraction of terms chosen. For sets that are approximately uniformly distributed for large $n$, this is likely to hold. But bof has provided an example where they are not uniformly distributed, and thus it fails.

Answer 3

This method is also present in my other answer to the linked question about binomial coefficients over primes.

Let $T_n\sim B(n,1/2)$ be the binomial distribution. Then by Hoeffding's inequality,

$$ P(T_n \notin [\frac n2-\sqrt{n\log\log n}, \frac n2 + \sqrt{n\log\log n}]) \leq \frac 2{(\log n)^2}.$$

Now, let $k_1, \ldots, k_m$ denote the enumeration of integers $1,\ldots, n$ outside $[\frac n2-\sqrt{n\log\log n}, \frac n2+\sqrt{n\log\log n}]$ in increasing order, and the last number is $n$. Then we have for any $0\leq a<b\leq 1$, $$ \frac{ \# \{ a\leq \frac kn \leq b | k\notin [\frac n2-\sqrt{n\log\log n}, \frac n2+\sqrt{n\log\log n}]\}}{n+O(\sqrt{n\log\log n})}=\frac{(b-a)n+O(\sqrt{n\log\log n})}{n +O(\sqrt{n\log\log n})}\rightarrow b-a \ \mathrm{as} \ n\rightarrow\infty. $$ Therefore the sequence $k_1/k_m,k_2/k_m,\ldots, k_{m-1}/k_m, 1$ approach uniform distribution in $(0,1)$. However, the asymptotic for the sum of binomial coefficients over the set $k_1, \ldots, k_m$ is at most $$ \lesssim \frac{2^{n+1}}{(\log n)^2}. $$ This is much less than the conjectured asymptotic of $\sim 2^n$.