Show that $\sum_{i=1}^{k/2} {{k}\choose i}2^i < 3^{k-1}$ for $k\geq6$ and even. I tried using $(1+2)^k=\sum_{i=0}^k{{k}\choose{i}}2^i$, the first half has the same binomials as the second and larger powers of two. Also tried induction, but the step is proving that $\dfrac{\sum_{i=0}^{k/2+1}{k+2\choose i}2^i}{\sum_{i=0}^{k/2}{k\choose i}2^i}<9$.

  • $\begingroup$ @metamorphy - does your bound imply the OP's requested bound? Perhaps I'm missing something but I don't see how your bound relates to the request bound (at least, not in an obvious way). $\endgroup$ – antkam Nov 8 at 19:29
  • $\begingroup$ @metamorphy - I'm guessing the $\sqrt{8}$ comes from... Stirling's approximation? Actually, even though your observation does not answer the OP question directly, I am quite interested in (1) how you prove its correct, and (2) why the ratio $\to 1$, and (3) how the $\sqrt{8}$ comes about. If you don't mind writing an answer, that'd be great. $\endgroup$ – antkam Nov 8 at 20:57
  • $\begingroup$ @antkam: Done (removed my comments above as redundant now). $\endgroup$ – metamorphy Nov 8 at 21:43

Here's an inductive approach. Let $a_n = \sum_{i \leq n} \binom{2n}{i} 2^i$ (including $i = 0$ for convenience). Then since $\binom{2n+2}{i} = \binom{2n}{i-2} + 2\binom{2n}{i-1} + \binom{2n}{i}$, we have \begin{align*} a_{n+1} &= \sum_{i \leq n+1} \binom{2n+2}{i} 2^i \\ &= \sum_{i \leq n+1} \left(\binom{2n}{i-2} 2^i + \binom{2n}{i-1} 2^{i+1} + \binom{2n}{i} 2^i\right) \\ &= \sum_{i \leq n-1} \binom{2n}{i} 2^{i+2} + \sum_{i \leq n} \binom{2n}{i} 2^{i+2} + \sum_{i \leq n+1}\binom{2n}{i} 2^i \\ &= \left(4a_n - \binom{2n}{n}2^{n+2}\right) + 4a_n + \left(a_n + \binom{2n}{n+1} 2^{n+1}\right) \\ &< 9a_n \end{align*} where the last inequality holds because $\binom{2n}{n} > \binom{2n}{n+1}$. Then since $a_3 < 3^5$, by induction we have $a_n < 3^{2n-1}$ for all $n \geq 3$ (though there are better asymptotic bounds, e.g. $a_n \leq 2^n \sum_{i \leq n} \binom{2n}{i} \leq 8^n$).



OK, here is a proof using probability. It requires pretty tedious accounting.

First re-write the desired inequality as (*) below:

$$\sum_{i=1}^{k/2} {{k}\choose i}(\frac13)^{k-i} (\frac23)^i < \frac13 \,\,\,\,\,\,\,\,\text{ .....(*)}$$

Now consider a "trinomial" experiment, with $k$ i.i.d. trials, and each trial result $\in \{a, b, c\}$ each with equal prob $\frac13$. Define r.v.s $A, B, C$ as the number of occurrences of $a, b, c$ respectively. Obviously we have $A+B+C=k$ and $E[A]=E[B]=E[C] = k/3$.

Then the LHS of (*) $= P(\frac{k}{2}\le A \le k-1) < P(A \ge {k\over 2})$.

Originally, I was thinking Markov's inequality would work, but as the OP author correctly pointed out, Markov's inequality gives $P(A \ge {k \over 2}) \le {E[A] \over {k/2}} = \frac23$ which is too big (too loose).

The main idea of the proof is that, $A \ge k/2$ implies $A$ is the max among $A, B, C$. That would almost immediately give the $1/3$ bound (by symmetry), except for the case of $A$ being a joint max with $B$ or $C$ (e.g. $A=B=k/2, C=0$). Dealing with that joint max case is where most of the tedious accounting comes in.

Define these events:

  • $U_A=$ the event that $A$ is the unique max among $A,B,C$, i.e. $A> \max(B,C)$

  • $U_B, U_C$ defined similarly

  • $U = U_A \cup U_B \cup U_C =$ event that there exists a unique max

  • $V = U^c=$ complement of $U$, i.e. the max is a joint max ($2$ or $3$-way tie)

By the law of total probability,

$$P(A \ge {k\over 2}) = \color{red}{P(A \ge {k\over 2} \mid U)} P(U) + \color{blue}{P(A\ge {k\over 2} \mid V)} P(V)$$

Claim 1 (the easy case): $\color{red}{P(A \ge {k\over 2} \mid U)} \le \frac13$

Proof: conditioned on $U$, i.e. there being a unique max, then $A \ge {k \over 2}$ implies $A$ must be the unique max. So

$$\color{red}{P(A \ge {k\over 2} \mid U)} \le P(U_A \mid U) = \frac13$$

where the last equality is by symmetry among $A,B,C$.

Claim 2 (the tedious case): $\color{blue}{P(A\ge {k\over 2} \mid V)} < \frac13$

Define these $6$ events, each being a subset of $V$ (when $k \ge 6$):

  • $E_{AB} = $ the event $(A = B = {k \over 2}, C=0)$

  • $E_{BC}, E_{CA}$ defined similarly

    • By symmetry, the number of sample points in these $3$ events are equal. We will call it $e = |E_{AB}| = |E_{BC}| = |E_{CA}|$
  • $F_{AB} = $ the event $(A = B = {k\over 2} - 1, C = 2)$

  • $F_{BC}, F_{CA}$ defined similarly

    • By symmetry, the number of sample points in these $3$ events are equal. We will call it $f = |F_{AB}| = |F_{BC}| = |F_{CA}|$

Note that, when conditioned on $V$, then $(A \ge k/2) = E_{AB} \cup E_{CA}$.

Also note that the $3$ $E$-events are disjoint, and they are also disjoint from any $F$-event. So:

$$\color{blue}{P(A\ge {k\over 2} \mid V)} = {P(A\ge {k\over 2} \cap V) \over P(V)} = {P(E_{AB} \cup E_{CA}) \over P(V)} \le {e + e \over e + e + e + f} = {2e \over 3e + f}$$

For convenience write $k = 2m, m \ge 3$ (since it's given that $k\ge 6$ and is even), then

  • $e = {2m \choose m} = {(2m)! \over m! m!}$

  • $f = {2m \choose (m-1),(m-1),2} = {(2m)! \over (m-1)! (m-1)! 2!}$

  • ${f \over e} = {m! m! \over (m-1)! (m-1)! 2!} = {m^2 \over 2} \ge \frac92 > 4 $ (when $m \ge 3$)

Therefore $f > 4e$ and ${2e \over 3e + f} < {2 \over 7} < \frac13$, completing the proof of Claim 2. QED

Main result now follows by combining Claim 1 & Claim 2:

$$\text{LHS of (*)} < P(A \ge k/2) \le \frac13 P(U) + \frac13 P(V) = \frac13$$

  • $\begingroup$ This is part of a homework, this inequality is not the original problem, but a sufficient condition. I tried your hint, lets perform an experiment with 3 possible outcomes $k$ times and let $X$ count how many times we obtain one specific outcome. Then the LHS is $P(X\geq \frac{k}{2}) \leq \frac{E[X]}{k/2}$ according to Markov's inequality, but if I did it right $E[X]=k/3$ and so $LHS \leq \frac{2}{3}$. Maybe I am still missing something $\endgroup$ – user1768368 Nov 8 at 18:05
  • $\begingroup$ You are right (and I was wrong originally): Markov inequality is too weak. Instead I now have a symmetry-based argument, but it involves pretty tedious accounting to deal with a special case. :( $\endgroup$ – antkam Nov 8 at 20:49

An overkill (perhaps), but one can get the true asymptotics from $$\sum_{k=0}^{n}\binom{2n}{k}a^{2n-k}(1-a)^k=n\binom{2n}{n}\int_0^a x^{n-1}(1-x)^n~dx$$ (obtained like I did here, or just using integration by parts). At $a=1/3$, this gives $$\sum_{k=0}^{n}\binom{2n}{k}2^k=n\binom{2n}{n}\int_0^1 y^{n-1}(3-y)^n~dy$$ (after substituting $x=y/3$). The integral is asymptotically $2^{n+1}/n$; in fact $$\int_0^1 y^{n-1}(3-y)^n~dy=\frac{2^n}{n}+\int_0^1 y^n(3-y)^{n-1}~dy\qquad\color{gray}{[\text{I.B.P.}]}\\=\frac{2^n}{n}\left[1+\frac{1}{2}\int_0^n\left(1-\frac{z}{n}\right)^n\left(1+\frac{z}{2n}\right)^{n-1}dz\right]\qquad\color{gray}{[y=1-z/n]}\\\leqslant\frac{2^n}{n}\left(1+\frac{1}{2}\int_0^\infty e^{-z}e^{z/2}~dz\right)=\frac{2^{n+1}}{n},$$ the inequality is asymptotically tight. Thus $\color{blue}{\sum_{k=0}^{n}\binom{2n}{k}2^k\leqslant\binom{2n}{n}2^{n+1}}\asymp 2^{3n+1}/\sqrt{n\pi}$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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