Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$ In this question we are asked to show that
$\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$
What I did:
$\sum_{k=2012}^{n} 2^k\binom{n}{k} = \sum_{k=2012}^{n} 2^k*1^{n-k}\binom{n}{k} \leq \sum_{k=0}^{n} 2^k*1^{n-k}\binom{n}{k} = (2+1)^n = 3^n$, using newton's binomial.
So obviously, $\sum_{k=2012}^{n} 2^k\binom{n}{k} = O(3^n)$
How do I show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Omega(3^n)$? Could anyone please point me in the right direction?

Since
$$
\begin{align}
\sum_{k=2012}^n2^k\binom{n}{k}
&=3^n-\sum_{k=0}^{2011}2^k\binom{n}{k}\\
&=3^n\left(1-\sum_{k=0}^{2011}2^k\binom{n}{k}3^{-n}\right)
\end{align}
$$
we need to estimate the size of $\displaystyle \Phi(n)=\sum_{k=0}^{2011}2^k\binom{n}{k}3^{-n}$.
$2^k\binom{n}{k}3^{-n}$ approximates a normal distribution with mean $\frac{2n}{3}$ and variance $\frac{2n}{9}$ (you should compute this for your teacher). $\Phi(n)$ corresponds to the probability of being more than $\frac{2n-6034.5}{\sqrt{2n}}$ standard deviations below the mean. For $n\ge3018$, this means $\Phi(n)\le\frac12$ (why?).
You can now probably guess what the lower and upper bounds are for
$$
\sum_{k=2012}^n2^k\binom{n}{k}=\Theta(3^n)
$$
when $n\ge3018$.
