# A conjecture on the sum of binomial coefficients

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$$

• Let $C$ consist of all positive integers less than $2$, then $S_n = n$ and $N(n) = 1$, so $S_n/N(n)$ is not asymptotically equivalent to $2^n/n$. Can you try to give a more precise statement of the conjecture. The role of the "characteristic" (in my example "being less than 2") is not clear to me. Feb 24, 2019 at 12:43
• I have a feeling that something like this might be a counterexample: let $C$ be the set of all numbers with an odd number of digits (in base $10$).
– bof
Feb 24, 2019 at 14:09
• For $C=k\mathbb{Z}$ with positive $k$ (well-known), $C=\mathcal{P}$ primes (work in progress), the asymptotic is true. But, there are going to be counterexamples by making $C$ stay far away from the central binomial coefficient. Feb 24, 2019 at 14:19
• Now, I am not sure on $C=\mathcal{P}$. For $C=\mathcal{P}$, the asymptotic is true for "almost all" $n$. It may be true for primes, but currently there is a technical barrier. Feb 26, 2019 at 4:37
• @i707107 Just an FYI, even the primes satisfy this uniform distribution condition i.e. the ratios $\frac{p_1}{p_n}, \frac{p_2}{p_n}, \ldots \frac{p_{n-1}}{p_n},1$ are uniformly distributed in 0,1. Feb 27, 2019 at 23:14

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

• This shows that we need stronger conditions on $C$ for the conjecture to hold. I think a sufficient but not necessary condition is that the sequence of numbers $k_1/k_n, k_2/k_n, k_3/k_n, \ldots$ approach uniform distribution in $(0,1)$. Feb 25, 2019 at 11:17

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.

• As demonstrated by @bof we need stronger condition on $C$ for the conjecture to hold. Feb 25, 2019 at 11:13

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