Maximum of the weighted binomial sum $2^{-r}\sum_{i=0}^r\binom{m}{i}$

Question

Let $m$ be a positive integer and let $f_m(r)=2^{-r}\sum_{i=0}^r\binom{m}{i}$. Clearly $f_m(0)=f_m(m)=1$ and $f_{2r+1}(r)=2^{2r}$.

Conjecture: If $m>12$, then the maximum value of $f_m(r)$ for $r\in\{0,1,2,\dots,m\}$ occurs when $r=\lfloor m/3\rfloor +1$.

Such a weighted sum arises in Coding Theory and in Information Theory, so experts may know the answer to this conjecture. (Computation shows that it is true for $m\leqslant1000$.) The following seem helpful and relevant: (1) the entropy function $H(p)=-p\log p-(1-p)\log(1-p)$, (2) Stirling's approximations, and (3) the MO questions Lower bound for sum of binomial coefficients?, and Estimating a partial sum of weighted binomial coefficients. Alas, I couldn't see how to prove such a precise conjecture. Proving that the maximum is "near" $m/3$, in some sense, may be more tractable.

Answer 1

I'll give a crude calculation on the back of this envelope.

Assume that $c'm<r<cm$ for some $0<c'<c<\frac12$.

When $i=o(r^{1/2})$, we have $$\binom{m}{r-i}= (1+o(1))\, \left(\frac{r}{m-r}\right)^i\binom mr ,$$ so $$f_m(r)= (1+o(1))\, 2^{-r}\frac{m-r}{m-2r}\binom mr.$$ (The condition $c<1/2$ keeps the ratio below 1 so the sum converges quickly, while the condition $c'>0$ means that $i=o(r^{1/2})$ is enough terms to get most of the sum.)

Consequently, $$\frac{f_m(r-1)}{f_m(r)} = (1+o(1)) \frac{2r}{m-r},$$ which is increasing in $r$ and equals 1 when $r=\bigl(\frac13 +o(1)\bigr) m$.

To get more precision, find a first approximation to the actual error terms. The calculations become more difficult of course.

ADDED. Now I found a bigger envelope and can explain how to get the full result at least for sufficiently large $m$. Having proved that the maximum is close to $m/3$, we will home in on it more accurately. Put $r=m/3+k$ where $k$ is small and $r$ is an integer.

I'll leave out lots of details (often because I don't have them).

First, $$ \binom{m}{r-i} = 2^{-i}\binom{m}{r}\biggl(1 - \frac{3i(3i-6k-1)}{4m} + \cdots\biggr),$$ where I think that is enough terms but I'm not sure (the next term is $O((i^4+i^2k^2)/m^2)$). Summing over $i\ge 0$, $$ f_m(r) = 2^{-r}\binom{m}{r}\biggl(2 + \frac{9k-12}{m} + O((1+k^2)/m^2)\biggr).$$

Dividing two values, $$ \frac{f_m(m/3+k+1)}{f_m(m/3+k)} = 1 - \frac{3(3k-1)}{2m} + O((1+k^2)/m^2). $$

Now consider the class of $m$ modulo 3. For $m=3M$, integer $M$, $$ \frac{f_m(M+k+1)}{f_m(M+k)}=\begin{cases} 1+\frac{1}{2M}+O(M^{-2}), & \text{ for $k=0$};\\ 1-\frac{1}{M}+O(M^{-2}), & \text{ for $k=1$}, \end{cases} $$ so the maximum occurs for $r=m/3+1$ provided the $O(M^{-2})$ is small enough to not interfere. The same phenomenon occurs if $m$ is 1 or 2 modulo 3 (use $k=-1/3,2/3$ for 1, $k=-2/3,1/3$ for 2). There is always a gap of $\Omega(m^{-1})$ that will dominate the $O(m^{-2})$ extras if $m$ is large enough.

To turn this into a theorem, make explicit bounds on the error terms. It could be that easily obtained bounds don't work when $m$ is small, but hopefully that will overlap the computational range.

Answer 2

Unfortunately I cannot recall exactly where I saw it (maybe an exercise in a combinatorics book) but I believe the following is known, the binomial coefficients $$ \left\{\binom{m}{i}\right\}_{0\leq i\leq m} $$ form a super-increasing sequence (last term is bigger than the sum of all previous terms) until $m/3$ (floor or ceiling).

Could this be used to prove what you want?