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?
 A: 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.
A: 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)
A: 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$.
