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

Question

En esta pregunta se nos pide que demostremos que

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

Lo que hice:

$\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$ usando el binomio de Newton.

Así que, obviamente, $\sum_{k=2012}^{n} 2^k\binom{n}{k} = O(3^n)$

¿Cómo puedo demostrar que $\sum_{k=2012}^{n} 2^k\binom{n}{k} = \Omega(3^n)$ ? ¿Podría alguien indicarme la dirección correcta?

Answer 1

Observa que los términos que omites de la binomial de Newton son todos menores que $\binom{n}{k}$ en crecimiento (el $2^k$ son menores que $2^{2012},$ tan constante. Y el binomio es como mucho un polinomio de grado $2012,$ tan subexponencial.

Answer 2

Quiero dar las gracias de antemano a Igor Rivin.

Mi solución

Lema: sea $f,g$ sean funciones no negativas tales que $f=O(g)$ entonces $f+g=\Theta(g)$ .

Prueba: sea $f\leq cg$ .

$\Theta(g) =g \leq f+g \leq cg+g =(c+1)g=\Theta(g)$ .

Ahora utilizaremos este lema para resolver la pregunta:

$\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}$

Así que..:

$\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})$ (tras invocar el lema)

Answer 3

Desde $$ \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} $$ necesitamos estimar el tamaño de $\displaystyle \Phi(n)=\sum_{k=0}^{2011}2^k\binom{n}{k}3^{-n}$ .

$2^k\binom{n}{k}3^{-n}$ se aproxima a una distribución normal con media $\frac{2n}{3}$ y varianza $\frac{2n}{9}$ (debes calcularlo para tu profesor). $\Phi(n)$ corresponde a la probabilidad de ser más de $\frac{2n-6034.5}{\sqrt{2n}}$ desviaciones estándar por debajo de la media. En $n\ge3018$ Esto significa $\Phi(n)\le\frac12$ (¿por qué?).

Probablemente ahora puedas adivinar cuáles son los límites inferior y superior de $$ \sum_{k=2012}^n2^k\binom{n}{k}=\Theta(3^n) $$ cuando $n\ge3018$ .