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?

I want to thank Igor Rivin in advance.
My solution
Lemma: let $f,g$ be non negative functions such that $f=O(g)$, then $f+g=\Theta(g)$.
Proof: let $f\leq cg$.
$\Theta(g) =g \leq f+g \leq cg+g =(c+1)g=\Theta(g)$.
Now we will use this lemma to solve the question:
$\sum_{k=2012}^{n}2^k\binom{n}{k} = \sum_{k=0}^{n}2^k\binom{n}{k}-\sum_{k=0}^{2011}2^k\binom{2011}{k} = 3^n-\sum_{k=0}^{2011}2^k\binom{2011}{k}$
So:
$\sum_{k=2012}^{n}2^k\binom{n}{k} + \sum_{k=0}^{2011}2^k\binom{2011}{k} = 3^n =\Theta(\sum_{k=2012}^{n}2^k\binom{n}{k})$ (after invoking the lemma)
