Show that $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Theta(3^n)$

Question

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?

Answer 1

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.

Answer 2

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)

Answer 3

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$.