La evaluación de $\sum_{k=0}^n \binom{n}{k} 2^{k^2}$

Question

Por favor alguien puede ayudarme simplificación de esta suma

$$\sum_{k=0}^n \binom{n}{k} 2^{k^2}$$

Wolframalpha falla (ver aquí).

Gracias de antemano.

La suma cuenta el número de (etiquetado) de los bigramas (con bucles) con conjunto de vértices $V \subseteq [n]$.

Answer 1

Estoy de acuerdo con J. M. del comentario anterior que esto no se va a resolver en algo simple. Asintóticamente, a pesar de que, el último término de la voluntad de dominar, y tal vez eso va a ser útil. Tenemos $$2^{n^2} \leq \sum_{k=0}^n \binom{n}{k} 2^{k^2} \leq 2^{n^2}\left(1 + \frac{2n^2}{4^n}\right).$$ La relativa resto término $R(n) = \frac{2n^2}{4^n}$ $0$ bastante rápidamente como $n \to \infty$, y por lo $\sum_{k=0}^n \binom{n}{k} 2^{k^2} \approx 2^{n^2}$.

Derivación: los términos de La suma son estrictamente creciente. Desde $n \geq k$ $k \geq 1$ tenemos $$\frac{\binom{n}{k} 2^{k^2}}{\binom{n}{k-1}2^{(k-1)^2}} = 2^{2k-1}\left(\frac{n}{k}-1+\frac{1}{k}\right) \geq 2^{2k-1}\left(1-1+\frac{1}{k}\right) = \frac{2^{2k}}{2k}> 1.$$

Por lo tanto, $$2^{n^2} \leq \sum_{k=0}^n \binom{n}{k} 2^{k^2} = 2^{n^2} + \sum_{k=0}^{n-1} \binom{n}{k} 2^{k^2} \leq 2^{n^2} + \sum_{k=0}^{n-1} \binom{n}{n-1} 2^{(n-1)^2} = 2^{n^2} + n^2 2^{n^2-2n+1}$$ $$= 2^{n^2}\left(1 + \frac{2n^2}{4^n}\right).$$