<s>[INST] 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$.
 [/INST] 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$).
</s>