Inequality involving sums with binomial coefficient

Question

I am trying to show upper- and lower-bounds on

$$\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\min(i, n-i)$$

(where $n\geq 1$) in order to show that it basically grows as $\Theta(n)$.

The upper-bound is easy to get since $\min(i, n-i)\leq i$ for $i\in\{0, \dots n\}$ so that

$$\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\min(i, n-i)\leq \frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}i = \frac{n}{2}.$$

Thanks to Desmos, I managed to find a lower bound, but I am struggling to actually prove it. Indeed, I can see that the function $f(n)=\frac{n-1}{3}$ does provide a lower-bound. One can in fact rewrite

$$\frac{n-1}{3}=\frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\frac{2i-1}{3}.$$

I was thus hoping to show that for each term we have $\frac{2i-1}{3}\leq \min(i, n-i)$, but this is only true if $i\leq \frac{3n+1}{5}$ and not generally for $i\leq n$. I imagine there is a clever trick to use at some point but for some reason I am stuck here.

Any help would be appreciated, thank you!

EDIT: Thank you everyone for all the great and diverse answers! I flagged River Li's answer as the "accepted" one because of its simplicity due to the use of Cauchy-Schwartz inequality, which does not require a further use of Stirling's approximation. Note that the other answers which involve such an approximation are much tighter though, but proving $\Theta(n)$ growth was sufficient here.

Answer 1

Both $\binom ni$ and $\min(i,n-i)$ are largest for $i$ near $n/2$. This means that, if we compare $$\frac1{n+1}\sum_{i=0}^n\binom ni\min(i,n-i)$$ with $$\left(\frac1{n+1}\sum_{i=0}^n \binom ni\right)\left(\frac1{n+1}\sum_{i=0}^n \min(i,n-i)\right),$$ the first should be larger, since larger numbers are multiplied by larger numbers and smaller numbers by smaller numbers. This can in fact be made more precise by (one form of) the rearrangement inequality:

If $a_1\leq \cdots\leq a_m$ and $b_1\leq \cdots\leq b_m$ are sequences of real numbers, then $$\frac{a_1b_1+\cdots+a_mb_m}m\geq \frac{a_1+\cdots+a_m}m\cdot \frac{b_1+\cdots+b_m}m.$$

(This can be proven by summing $(a_i-a_j)(b_i-b_j)\geq 0$ over all $i$ and $j$.) So, $$\frac1{2^n}\sum_{i=0}^n\binom ni\min(i,n-i)\geq \frac{1}{(n+1)2^n}\sum_{i=0}^n\binom ni\sum_{i=0}^n\min(i,n-i)=\frac1{n+1}\sum_{i=0}^n\min(i,n-i).$$ The last sum is $\Omega(n^2)$, since the average order of $\min(i,n-i)$ is about $n/4$, and so the entire sum is $\Omega(n)$. You've also shown that it's $O(n)$, so this is enough to show that it's $\Theta(n)$.

Answer 2

Let's first note that $\binom{n}{i}\cdot i = n\cdot \binom{n-1}{i-1}$.

For odd $n=2m+1$, this makes $$ \begin{align} S_n = \sum_{i=0}^{n}\binom{n}{i}\cdot\min(i,n-i) &= 2\sum_{i=0}^m\binom{n}{i}\cdot i = 2n\sum_{i=1}^m\binom{n-1}{i-1} = 2n\sum_{j=0}^{m-1}\binom{2m}{j} \\ &= n\cdot\left( \sum_{j=0}^{2m}\binom{2m}{j} - \binom{2m}{m} \right) = n\cdot\left( 2^{2m} - \binom{2m}{m} \right) \end{align} $$ where we have used that $\binom{2m}{j}=\binom{2m}{2m-j}$. This makes $$ \frac{S_n}{2^n} = \frac{n}{2}\cdot\left (1 - \frac{\binom{2m}{m}}{2^{2m}} \right) \approx \frac{n}{2}\cdot\left( 1 - \frac{1}{\sqrt{\pi m}} \right). $$

For even $n=2m$, we get $$ \begin{align} S_n = \sum_{i=0}^{n}\binom{n}{i}\cdot\min(i,n-i) &= 2\sum_{i=0}^m\binom{n}{i}\cdot i - \binom{2m}{m}\cdot m = 2n\sum_{i=1}^m\binom{n-1}{i-1} - \binom{2m}{m}\cdot m \\ &= n\sum_{j=0}^{n-1}\binom{n-1}{j} - \binom{2m}{m}\cdot m = n\cdot\left( 2^{n-1} - \frac{1}{2}\binom{2m}{m} \right) \end{align} $$ which once more makes $$ \frac{S_n}{2^n} = \frac{n}{2}\cdot\left(1-\frac{\binom{2m}{m}}{2^{2m}}\right). $$

In both cases, you get $n/2$ as an upper bound. However, there are strong bounds on $\binom{2m}{m}/2^{2m}$ which can be applied: $$ \frac{e^{-1/8m}}{\sqrt{\pi m}} \le \frac{\binom{2m}{m}}{2^{2m}} \le \frac{1}{\sqrt{\pi m}} $$ Eg, see Jack D'Aurizio's derivation of this, or Wikipedia.

---

Additional bounds have been provided by robjohn. The following bounds seem to be the tightest proven so far: $$ \frac{4^me^{-1/8m}}{\sqrt{\pi m}} < \binom{2m}{m} < \frac{4^m}{\sqrt{\pi\left( m+\frac{1}{4} \right)}} $$

The following bound is even tighter, but I have no proof of it, just numerical evidence: $$ \frac{4^m}{\sqrt{\pi\left( m+\frac{1}{4}+\frac{1}{32m} \right)}} < \binom{2m}{m} $$ It's the same as the above up to second order approximation, so not a bit difference, but easier to compute.

---

Answer 3

We start with $$ \sum_{k=0}^{\left\lfloor\frac{n}2\right\rfloor}\binom{n}{k} =\left\{\begin{array}{} 2^{n-1}&\text{if $n$ is odd}\\ 2^{n-1}+\frac12\left(\raise{2pt}{n}\atop\frac{n}2\right)&\text{if $n$ is even} \end{array}\right.\tag1 $$ Substitute $n\mapsto n-1$: $$ \sum_{k=0}^{\left\lfloor\frac{n-1}2\right\rfloor}\binom{n-1}{k} =\left\{\begin{array}{} 2^{n-2}&\text{if $n$ is even}\\ 2^{n-2}+\frac12\left(\raise{2pt}{n-1}\atop{\frac{n-1}2}\right)&\text{if $n$ is odd} \end{array}\right.\tag2 $$ Subtract the $k=\left\lfloor\frac{n-1}2\right\rfloor$ term: $$ \sum_{k=0}^{\left\lfloor\frac{n-1}2\right\rfloor-1}\binom{n-1}{k} =\left\{\begin{array}{} 2^{n-2}-\left(\raise{2pt}{n-1}\atop{\frac{n}2-1}\right)&\text{if $n$ is even}\\ 2^{n-2}-\frac12\left(\raise{2pt}{n-1}\atop{\frac{n-1}2}\right)&\text{if $n$ is odd} \end{array}\right.\tag3 $$ Substitute $k\mapsto k-1$: $$ \sum_{k=1}^{\left\lfloor\frac{n-1}2\right\rfloor}\binom{n-1}{k-1} =\left\{\begin{array}{} 2^{n-2}-\frac12\left(\raise{2pt}{n}\atop{\frac{n}2}\right)&\text{if $n$ is even}\\ 2^{n-2}-\frac12\left(\raise{2pt}{n-1}\atop{\frac{n-1}2}\right)&\text{if $n$ is odd} \end{array}\right.\tag4 $$ Then $$ \begin{align} \sum_{k=0}^{\left\lfloor\frac{n-1}2\right\rfloor}\binom{n}{k}k &=n\sum_{k=1}^{\left\lfloor\frac{n-1}2\right\rfloor}\binom{n-1}{k-1}\tag{5a}\\ &=\left\{\begin{array}{} n2^{n-2}-\frac{n}2\left(\raise{2pt}{n}\atop{\frac{n}2}\right)&\text{if $n$ is even}\\ n2^{n-2}-\frac{n}2\left(\raise{2pt}{n-1}\atop{\frac{n-1}2}\right)&\text{if $n$ is odd} \end{array}\right.\tag{5b} \end{align} $$ Explanation:
$\text{(5a)}$: $\binom{n}{k}k=\binom{n-1}{k-1}n$ and the $k=0$ term vanishes
$\text{(5b)}$: multiply $(4)$ by $n$

---

Double and add the middle term in the even $n$ case: $$ \begin{align} \sum_{k=0}^n\binom{n}{k}\min(k,n-k) &=\left\{\begin{array}{} n2^{n-1}-\frac{n}2\left(\raise{2pt}{n}\atop{\frac{n}2}\right)&\text{if $n$ is even}\\ n2^{n-1}-n\left(\raise{2pt}{n-1}\atop{\frac{n-1}2}\right)&\text{if $n$ is odd} \end{array}\right.\tag6 \end{align} $$ The estimates for the central binomial coefficients from this answer give $$ \frac{2^n}{\sqrt{\pi\!\left(\frac{n}2+\frac13\right)}}\le\binom{n}{\frac{n}2}\le\frac{2^n}{\sqrt{\pi\!\left(\frac{n}2+\frac14\right)}}\tag7 $$ which gives upper and lower bounds.

Answer 4

Let $$S := \frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\min(i, n-i),$$ $$T := \frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}\max(i, n-i).$$

We have $$S + T = \frac{1}{2^n}\sum_{i=0}^n\binom{n}{i}n = n,$$ $$T - S = \frac{1}{2^n}\sum_{i=0}^n\binom{n}{i} |n - 2i|$$ where we have used $\max(a, b) + \min(a,b) = a + b$ and $\max(a, b) - \min(a, b) = |a - b|$ for all real numbers $a, b$.

Using Cauchy-Bunyakovsky-Schwarz inequality, we have \begin{align*} T - S &= \frac{1}{2^n}\sum_{i=0}^n \sqrt{\binom{n}{i} (n - 2i)^2}\sqrt{\binom{n}{i}}\\ &\le \frac{1}{2^n} \sqrt{\sum_{i=0}^n\binom{n}{i} (n - 2i)^2 \cdot \sum_{i=0}^n\binom{n}{i}}\\ &= \sqrt n \end{align*} where we have used $\sum_{i=0}^n\binom{n}{i} i^2 = 2^{n - 2}n(n + 1)$ and $\sum_{i=0}^n\binom{n}{i} i = 2^{n - 1}n$ (easy to prove using the identity $\binom{k}{m}m = k\binom{k-1}{m-1}$).

Thus, we have $$\frac{n}{2} - \frac{\sqrt n}{2} \le S \le \frac{n}{2}.$$

The desired result follows.