# Show that $\sum_{i=1}^{k/2} {{k}\choose i}2^i < 3^{k-1}$

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

• @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). – antkam Nov 8 at 19:29
• @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. – antkam Nov 8 at 20:57
• @antkam: Done (removed my comments above as redundant now). – 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$$).

UPDATED

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

• 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 – user1768368 Nov 8 at 18:05
• 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. :( – 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}$$.