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?

You note that the term you are omitting from the Newton binomial are all smaller than $\binom{n}{k}$ in growth (the $2^k$ are smaller than $2^{2012},$ so constant. And the binomial is at most a polynomial of degree $2012,$ so subexponential.
