Closed form asymptotically

Question

The bound for $$\sum_{i=1}^n\binom{n}{i}2^i$$ is $O\left(3^n\right)$ but what will be the bound for $$\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i$$ Any idea how should I proceed?

Answer 1

$\def\pp{\mathbb{P}}$$\Large\frac{1}{3^{2m}} \sum_{k=1}^m \binom{2m}{k}\ 2^k = \sum_{k=1}^m \binom{2m}{k}\ (\frac23)^k (\frac13)^{2m-k}$

$\large\ = \pp\Big(Bin(2m,\frac23) \in [1,m] \Big) < \exp(-\frac{m}{9})$   [by the tail bound via Hoeffding's inequality]

Numerically, this is far from asymptotically tight, but at least it shows that $\large\sum_{i=1}^{\frac{n}{2}}\binom{n}{i}2^i \in o(3^n)$.