<s>[INST] Evaluating $\sum_{k=0}^n \binom{n}{k} 2^{k^2}$ Can someone please help me simplifying this sum 
$$\sum_{k=0}^n \binom{n}{k} 2^{k^2}$$
Wolframalpha fails (see here).
Thanks in advance.
The sum counts the number of (labelled) digraphs (with loops) with vertex set $V \subseteq [n]$.
 [/INST] I agree with J.M.'s comment above that this is not going to resolve into something simple.  Asymptotically, though, the last term will dominate, and maybe that will be useful.  We have 
$$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).$$
The relative remainder term $R(n) = \frac{2n^2}{4^n}$ goes to $0$ fairly quickly as $n \to \infty$, and so $\sum_{k=0}^n \binom{n}{k} 2^{k^2} \approx 2^{n^2}$.
Derivation: The terms in the sum are strictly increasing.  Since $n \geq k$, for $k \geq 1$ we have $$\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.$$
Therefore,
$$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).$$
</s>